详细介绍:【C++】二叉搜索树
1. 二叉搜索树的概念
二叉搜索树又称二叉排序树,它或者是⼀棵空树,或者是具有以下性质的二叉树:
- 若它的左子树不为空,则左子树上所有结点的值都小于等于根结点的值
- 若它的右子树不为空,则右子树上所有结点的值都大于等于根结点的值
- 它的左右子树也分别为二叉搜索树
- 二叉搜索树中可以支持插入相等的值,也可以不支持插入相等的值,具体看使用场景定义,后续我们学习map/set/multimap/multiset系列容器底层就是二叉搜索树,其中map/set不支持插入相等值,multimap/multiset支持插入相等值
2. 二叉搜索树的性能分析
最优情况下,二叉搜索树为完全二叉树(或者接近完全二叉树),其高度为:log2 N
最差情况下, 二叉搜索树退化为单支树(或者类似单支),其高度为: N
所以综合而言二叉搜索树增删查改时间复杂度为:O(N)
那么这样的效率显然是无法满足我们需求的,我们后续课程需要继续讲解二叉搜索树的变形,平衡二叉搜索树AVL树和红黑树,才能适用于我们在内存中存储和搜索数据。另外需要说明的是,二分查找也可以实现O(log2 N) 级别的查找效率,但是二分查找有两大缺陷:
需要存储在支持下标随机访问的结构中,并且有序。
插入和删除数据效率很低,因为存储在下标随机访问的结构中,插⼊和删除数据⼀般需要挪动数据。 这里也就体现出了平衡二叉搜索树的价值。
3. 二叉搜索树的实现
二叉树的本质是通过链表实现,所以先实现一个树节点
template
struct BSTNode
{K _key;BSTNode* _left;BSTNode* _right;BSTNode(const K& key):_key(key), _left(nullptr), _right(nullptr){}
};
3.1插入
- 树为空,则直接新增结点,赋值给root指针
- 树不空,按二叉搜索树性质,插入值比当前结点大往右走,插入值比当前结点小往左走,找到空位 置,插入新结点。
- 如果支持插入相等的值,插入值跟当前结点相等的值可以往右走,也可以往左走,找到空位置,插 入新结点。(要注意的是要保持逻辑⼀致性,插入相等的值不要⼀会往右走,一会往左走)
int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};
bool Insert(const K& key)
{if (_root == nullptr){_root = new Node(key);return true;}Node* parent = nullptr;Node* cur = _root;//寻找合适位置while (cur){if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else{return false;}}//插入cur = new Node(key);if (parent->_key < key){parent->_right = cur;}else{parent->_left = cur;}return true;
}
3.2. 二叉搜索树的查找
从根开始比较,查找x,x比根的值大则往右边走查找,x比根值小则往左边走查找。
最多查找高度次,走到到空,还没找到,这个值不存在。
如果不支持插入相等的值,找到x即可返回
如果支持插入相等的值,意味着有多个x存在,一般要求查找中序的第⼀个x。如下图,查找3,要 找到1的右孩子的那个3返回
void 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;
}
3.3二叉搜索树的删除
首先查找元素是否在二叉搜索树中,如果不存在,则返回false。
如果查找元素存在则分以下四种情况分别处理:(假设要删除的结点为N)
- 要删除结点N左右孩子均为空
- 要删除的结点N左孩子位空,右孩子结点不为空
- 要删除的结点N右孩子位空,左孩子结点不为空
- 要删除的结点N左右孩子结点均不为空
对应以上四种情况的解决方案
- 把N结点的父亲对应孩子指针指向空,直接删除N结点(情况1可以当成2或者3处理,效果是⼀样的)
- 把N结点的父亲对应孩子指针指向N的右孩子,直接删除N结点
- 把N结点的父亲对应孩子指针指向N的左孩子,直接删除N结点
- 无法直接删除N结点,因为N的两个孩子无处安放,只能用替换法删除。找N左子树的值最大结点 R(最右结点)或者N右子树的值最小结点R(最左结点)替代N,因为这两个结点中任意一个,放到N的位置,都满足二叉搜索树的规则。替代N的意思就是N和R的两个结点的值交换,转而变成删除R结点,R结点符合情况2或情况3,可以直接删除。
bool Erase(const K& key)
{Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else{//准备删除// 0-1个孩⼦的情况// 删除情况1 2 3均可以直接删除,改变⽗亲对应孩⼦指针指向即可if (cur->_left == nullptr){if (cur != _root){//左为空,父亲指向我的右if (cur == parent->_left){parent->_left = cur->_right;}else{parent->_right = cur->_right;}}else{_root = cur->_right;}delete cur;}else if (cur->_right == nullptr){if (cur != _root){//右为空,父亲指向我的左。if (cur == parent->_left){parent->_left = cur->_left;}else{parent->_right = cur->_left;}}else{_root = cur->_left;}delete cur;}else{//左右都不为空,找子树中适合的节点替代我// 2个孩⼦的情况// 删除情况4,替换法删除// 假设这⾥我们取右⼦树的最⼩结点作为替代结点去删除// 这⾥尤其要注意右⼦树的根就是最⼩情况的情况的处理,对应课件图中删除8的情况// ⼀定要把cur给rightMinP,否会报错。Node* minRightParent = cur;Node* minRight = cur->_right;while (minRight->_left){minRightParent = minRight;minRight = minRight->_left;}swap(cur->_key, minRight->_key);if (minRight == minRightParent->_left)minRightParent->_left = minRight->_right;elseminRightParent->_right = minRight->_right;delete minRight;}return false;}}return false;
}
3.4二叉搜索树的遍历
二叉搜索树的遍历采用的是中序遍历,利用递归很简单就可以实现。但在主函数调用时就会发现,根节点我们无法获取,所以这里再采用一种“套娃”的方式,
void InOrder(){_InOrder(_root);cout << endl;}
private:void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}
7. 二叉搜索树key和key/value使用场景
7.1 key搜索场景:
只有key作为关键码,结构中只需要存储key即可,关键码即为需要搜索到的值,搜索场景只需要判断 key在不在。key的搜索场景实现的二叉树搜索树支持增删查,但是不支持修改,修改key破坏搜索树结构了
场景:检查一篇英文章单词拼写是否正确,将词库中所有单词放入二叉搜索树,读取文章中的单 词,查找是否在二叉搜索树中,不在则波浪线标红提示。
7.2 key/value搜索场景:
每⼀个关键码key,都有与之对应的值value,value可以任意类型对象。树的结构中(结点)除了需要存储key还要存储对应的value,增/删/查还是以key为关键字走二叉搜索树的规则进行比较,可以快速查找到key对应的value。key/value的搜索场景实现的二叉树搜索树支持修改,但是不支持修改key,修改key破坏搜索树性质了,可以修改value。
场景1:简单中英互译字典,树的结构中(结点)存储key(英文)和vlaue(中文),搜索时输入英文,则同时查找到了英文对应的中文。
7.3 key/value二叉搜索树代码实现
#pragma once
#include
#include
using namespace std;
template
struct BSTNode
{// pair _kv;K _key;V _value;BSTNode* _left;BSTNode* _right;BSTNode(const K& key, const V& value):_key(key), _value(value), _left(nullptr), _right(nullptr){}
};
template
class BSTree
{typedef BSTNode Node;
public:BSTree() = default;BSTree(const BSTree& t){_root = Copy(t._root);}BSTree& operator=(BSTree t){swap(_root, t._root);return *this;}~BSTree(){Destroy(_root);_root = nullptr;}bool Insert(const K& key, const V& value){if (_root == nullptr){_root = new Node(key, value);return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(key, value);if (parent->_key < key){parent->_right = cur;}else{parent->_left = cur;}return true;}Node* 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 cur;}}return nullptr;}bool Erase(const K& key){Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else{if (cur->_left == nullptr){if (parent == nullptr){_root = cur->_right;}else{if (parent->_left == cur)parent->_left = cur->_right;elseparent->_right = cur->_right;}delete cur;return true;}else if (cur->_right == nullptr){if (parent == nullptr){_root = cur->_left;}else{if (parent->_left == cur)parent->_left = cur->_left;elseparent->_right = cur->_left;}delete cur;return true;}else{Node* rightMinP = cur;Node* rightMin = cur->_right;while (rightMin->_left){rightMinP = rightMin;rightMin = rightMin->_left;}cur->_key = rightMin->_key;if (rightMinP->_left == rightMin)rightMinP->_left = rightMin->_right;elserightMinP->_right = rightMin->_right;delete rightMin;return true;}}}return false;}void InOrder(){_InOrder(_root);cout << endl;}
private:void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_key << ":" << root->_value << endl;_InOrder(root->_right);}void Destroy(Node* root){if (root == nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;}Node* Copy(Node* root){if (root == nullptr)return nullptr;Node* newRoot = new Node(root->_key, root->_value);newRoot->_left = Copy(root->_left);newRoot->_right = Copy(root->_right);return newRoot;}
private:Node* _root = nullptr;
};