二叉搜索树原理及底层实现

二叉搜索树BST

概念

二叉搜索树又称二叉排序树，它可以是一棵空树，或者是具有以下性质的二叉树：若它的左子树不为空，则左子树上所有节点的值都小于根节点的值；若它的右子树不为空，则右子树上所有节点的值都大于根节点的值；它的左右子树也分别为二叉搜索树。

即当我们按中序来遍历输出这棵树的节点时，是有序的，按从小到大的顺序。

实现的细节

搜索key的过程Find/FindR

a.从根开始查找，val比根节点值大则往右边走查找，比根节点值小则往左边走查找;
b.最多查找高度次，走到到空，还没找到，说明这个值不存在。

//普通版本--用循环解决
bool Find(const K& key)
{Node* cur = _root;while (cur){if (cur->_key < key){cur = cur->_right;}else if (cur->_key > key){cur = cur->_left;}else{return true;}}return false;
}//用递归来解决
public:
bool FindR(const K& key)
{return _FindR(_root, key);
}
private:
bool _FindR(Node* root, const K& key)
{if (root == nullptr)return false;if (key > root->_key)return _FindR(root->_right, key);else if (key < root->_key)return _FindR(root->_left, key);elsereturn true;
}

插入key的过程Insert/InsertR

需要考虑以下场景：

a.树为空，则直接新增节点new，赋值给root指针;
b.树不为空，按二叉搜索树性质查找插入位置，即与根节点比较，比根节点的值小，往左查找；比根节点的值大，往右查找，找到该位置后插入新节点。这个过程需要用到2个指针，一个为判断当前值与key孰大孰小的cur指针，一个是保存cur的父节点的parent指针，最终要把key值节点插入在parent的左/右节点。【注意：此处的二叉搜索树无相同值】

bool Insert(const K& key)
{//如果根节点为空，直接插入这个值if (_root == nullptr){_root = new Node(key);return true;}Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_key == key){//如果二叉搜索树中已经有一样的值了，插入失败return false;}else if (key > cur->_key){parent = cur;//与根节点比较，比根节点的值小，往左走；比根节点的值大，往右走cur = cur->_right;}else{parent = cur;cur = cur->_left;}}cur = new Node(key);//与根节点比较，比根节点的值大，就链接在右边if (key > parent->_key){parent->_right = cur;}else{parent->_left = cur;}return true;
}public:bool InsertR(const K& key){return _InsertR(_root, key);}
private:
bool _InsertR(Node*& root, const K& key){//方式1 bool _InsertR(Node* root, const K& key)//if (key > root->_key)//{//	if (root->_right == nullptr)//	{//		root->_right = new Node(key);//		return true;//	}//	else//		return _InsertR(root->_right, key);//}//else if (key < root->_key)//{//	if (root->_left == nullptr)//	{//		root->_left = new Node(key);//		return true;//	}//	else//		return _InsertR(root->_left, key);//}//else//	return false;//方式2 bool _InsertR(Node*& root, const K& key)if (root == nullptr){root = new Node(key);return true;}if (key > root->_key)return _InsertR(root->_right, key);else if (key < root->_key)return _InsertR(root->_left, key);elsereturn false;}

这里的二叉搜索树无法保证左右平衡。

删除的过程Erase/EraseR

首先查找元素是否在二叉搜索树中，如果不存在，则返回, 否则要删除的结点可能分下面四种情况：

1. 要删除的结点无孩子结点–直接删除，其父节点原来指向它的变成指向空
2. 要删除的结点只有左孩子结点–托孤，让该节点的父节点直接指向该节点的孩子节点
3. 要删除的结点只有右孩子结点–托孤，让该节点的父节点直接指向该节点的孩子节点
4. 要删除的结点有左、右孩子结点–替换，找左子树的最大和右子树的最小

看起来待删除节点的处理方式有4种情况，实际上情况1可以与情况2或者3合并起来，因此真正的删除过程如下：

1. 删除该结点且使被删除节点的父结点指向被删除节点的左孩子结点–直接删除
2. 删除该结点且使被删除节点的父结点指向被删除结点的右孩子结点–直接删除
3. 在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被删除节点中，再来处理该结点的删除问题–替换法删除

//普通版本
bool Erase(const K& key)
{Node* parent = nullptr;Node* cur = _root;while (cur){//与根节点比较，比根节点的值大，往右走；比根节点的值小，往左走if (key > cur->_key){parent = cur;cur = cur->_right;}else if (key < cur->_key){parent = cur;cur = cur->_left;}else{//能走到这，就说明找到了要删除的这个节点，要删除的节点为cur//情况1：左子节点为空，右子节点不为空if (cur->_left == nullptr){//需要特殊处理根节点，因为根节点无父节点if (cur == _root){_root = cur->_right;}else{//cur为parent的左子节点，cur的子节点就得继承parent的左子节点if (parent->_left == cur){parent->_left = cur->_right;}//cur为parent的右子节点，cur的子节点就得继承parent的右子节点else{parent->_right = cur->_right;}}delete cur;}//情况2：左子节点不为空，右子节点为空else if (cur->_right == nullptr){//需要特殊处理根节点，因为根节点无父节点if (cur == _root){_root = cur->_left;}else{//cur为parent的左子节点，cur的子节点就得继承parent的左子节点if (parent->_left == cur){parent->_left = cur->_left;}//cur为parent的右子节点，cur的子节点就得继承parent的右子节点else{parent->_right = cur->_left;}}delete cur;}//情况3：左右子节点均不为空else{//在cur的右子树中寻找中序的第一个结点Node* parent = cur;Node* minRight = cur->_right;//此处前置条件是cur的左右子树均不为空while (minRight->_left){parent = minRight;minRight = minRight->_left;}//交换cur和minRight的值cur->_key = minRight->_key;//删除minRightif (minRight == parent->_left)parent->_left = minRight->_right;elseparent->_right = minRight->_right;delete minRight;}return true;}}//走到这，说明没找到return false;
}//递归版本
public:bool EraseR(const K& key){return _EraseR(_root, key);}
private:bool _EraseR(Node*& root, const K& key){if (root == nullptr)return false;if (key > root->_key){return _EraseR(root->_right, key);}else if (key < root->_key){return _EraseR(root->_left, key);}else{Node* del = root;//相等就开始删除if (root->_left == nullptr){root = root->_right;}//情况2：左子节点不为空，右子节点为空else if (root->_right == nullptr){				root = root->_left;}//情况3：左右子节点均不为空else{Node* minRight = root->_right;while (minRight->left){minRight = minRight->left;}swap(root->_key, minRight->_key);// 转换成在子树中去删除节点return _EraseR(root->_right, key);}delete del;return true; }}

中序遍历InOrder

在不暴露根节点_root的情况下（比如写一个函数getroot()等让用户获取），套一层函数接口就直接在类内使用这个_root，实现中序遍历

void InOrder()
{_InOrder(_root);std::cout << std::endl;
}
private:
void _InOrder(Node* root)
{//中序：左根右if (root == nullptr) return;_InOrder(root->_left);std::cout << root->_key << " ";_InOrder(root->_right);
}

注意：二叉搜素树不支持改，对于二叉搜索树而言，仅仅修改对应节点的值，极有可能破坏原结构，所以改=删除+插入

构造函数、拷贝构造函数、赋值构造函数、析构函数

public:BSTree():_root(nullptr){}BSTree(const BSTree<K>& t){_root = Copy(t._root);}BSTree<K>& operator=(BSTree<K> t){swap(_root, t._root);return *this;}~BSTree(){Destory(_root);_root = nullptr;}
private:void Destory(Node* root){if (root == nullptr)return;//按后序来删除Destory(root->_left);Destory(root->_right);delete root;}Node* Copy(Node* root){if (root == nullptr)return nullptr;//前序遍历，再递归拷贝Node* newnode = new Node(root->_key);newnode->_left = Copy(root->_left);newnode->_right = Copy(root->_right);return newnode;}

应用场景

K模型–判断某个key在不在的场景；KV模型–通过key查找或修改value

1. K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。

比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。其他场景：检查单词拼写是否正确/车库出入系统/宿舍楼门禁系统

2. KV模型：每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。该种方式在现实生活中非常常见：

比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文<word, chinese>就构成一种键值对；再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是<word, count>就构成一种键值对。其他场景：英汉互译/学号学生对应

性能分析

插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。

对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。
但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：

• 最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其平均比较次数为：$lo{g}_{2}N$
• 最差情况下，二叉搜索树退化为单支树(或者类似单支)，其平均比较次数为：$\frac{N}{2}$

但是如果退化成单支树，二叉搜索树的性能就很差，后续引入红黑树和AVL树来解决。