【C++指南】一文总结C++二叉搜索树
🌟 各位看官好，我是egoist2023！
🌍 种一棵树最好是十年前，其次是现在！
🚀 今天来学习C++二叉搜索树的实现。
👍 如果觉得这篇文章有帮助，欢迎您一键三连，分享给更多人哦
目录
何为二叉搜索树
二叉搜索(排序)树具有如下特征：
若它的左子树不为空，则左子树上所有结点的值都小于等于根结点的值；若它的右⼦树不为空，则右子树上所有结点的值都大于等于根结点的值；它的左右⼦树也分别为二叉搜索树；二叉搜索树的中序遍历是有序的；了解二叉搜索树是为了之后为map/set/multimap/multiset的关联式容器打下基础。特别地，二叉搜索树分为冗余和不冗余版本。(冗余即有相等值也可插入)
在冗余版本的二叉搜索树中，会出现如下两种情况，那这两都是正确的吗？
是的，并不影响搜索二叉树的性质。
性能分析
可以发现在该二叉搜索树较为平衡的情况下
即在最优情况下，找到指定结点的情况下，只需要访问高度k次，即高度为： log2 N；
但在最差情况下，高度会达到N。（在红黑树章节会有详解如何平衡高度差）
综合来讲，二叉搜索树增删查改时间复杂度为： O(N)。
二分查找也能达到 log2 N 级别的查找效率，为何不使用二分查找呢？二分查找有以下缺陷：需要存储在⽀持下标随机访问的结构中，并且有序。插入和删除数据效率很低，因为存储在下标随机访问的结构中，插入和删除数据一般需要挪动数据。二叉搜索树在最差情况下能达到O(N)级别，那它能起到什么作用呢？二叉搜索树的引入是为了后续为平衡二叉树AVL树和红⿊树作铺垫，之后引入了旋转的概念，能够好维持二叉树的结构。
搜索树的结构
template<class K> struct BSTreeNode { K _key; BSTreeNode<K>* _left; BSTreeNode<K>* _right; BSTreeNode(const K& key) :_key(key) ,_left(nullptr) ,_right(nullptr) {} };插入和查找(非冗余版本)
插入时分为以下情况：
- 树为空时，申请一个新结点赋值给根结点_root;
- 树不为空时，插⼊值⽐当前结点⼤往右⾛，插⼊值⽐当前结点⼩往左⾛，找到空位置，插⼊新结点。(如若支持冗余，则可往左走，也可往右走，确保逻辑一致性)
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->_left = cur; } else { parent->_right = cur; } return true; }- 查找指定结点时，和插入结点的逻辑是类似的，新插入结点的值比当前结点大则往右走，反之往左走，找到后返回即可 。
- 那如果是冗余版本的二叉搜索树呢？意味着存在多个相等的值，而我们一般要查找中序遍历后的第一个相等的值(疑惑1),如何解决呢？(疑惑2)
疑惑1：找到第一个相等的值，可以方便我们知道有多少个相等的值，也能从头到尾打印。迭代器也可以确认其相等的值的范围等等。
疑惑2：
非冗余版本
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; }中序遍历
这样设计的目的是让我们调用InOrder的时候不需要传_root根节点(根本原因是在类外不能访问private私有的_root，只能在类里访问)
void InOrder() { _InOrder(_root); cout << endl; } void _InOrder(Node* root) { if (root == nullptr) { return; } _InOrder(root->_left); cout << root->_key << " "; _InOrder(root->_right); }删除
在二叉搜索树中删除的逻辑最为致命，它分为多种情况，需要考虑很多细节问题。
- 删除结点无左右孩子
- 删除结点有右孩子
- 删除结点有左孩子
- 删除结点有左右孩子
在情况1当中，把该结点的⽗亲对应孩⼦指针指向空，直接删除该结点，并不需要考虑删除结点是在左在右的情况。(情况1其实可以归类为情况2或情况3之中，本章节归类为情况2)
在情况2中：把N结点的⽗亲对应孩⼦指针指向N的右孩⼦，直接删除N结点
需要额外判断parent是左指针还是右指针指向cur的右孩子。
在情况3中： 把N结点的⽗亲对应孩⼦指针指向N的左孩⼦，直接删除N结点，依旧处理parent指向的问题。
在情况4中： 不能直接删除该结点且parent会不道指向cur的左还是右，这种情况需要找另一个结点来替代。为了保持二叉搜索树的性质，因此替代的结点必须是当前结点左子树的最大结点或者右子树的最小结点，交换值后，释放替代的结点资源。(本章节以找右子树最小结点为例)
这里埋下了一个坑，如果删除的是根结点，不能让parentreplace开始置为nullptr，否则会出现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 (cur == _root) { _root = cur->_right; } else { if (parent->_left == cur) { parent->_left = cur->_right; } else { parent->_right = cur->_right; } } delete cur; } //右节点为空 else if (cur->_right == nullptr) { if (cur == _root) { _root = cur->_left; } else { if (parent->_right == cur) { parent->_right = cur->_left; } else { parent->_left = cur->_left; } } delete cur; } //有双亲节点 else { Node* parentreplace = cur; Node* replace = cur->_right; while (replace->_left) { parentreplace = replace; replace = replace->_left; } swap(replace->_key, cur->_key); if (parentreplace->_left == replace) { parentreplace->_left = replace->_right; } else { parentreplace->_right = replace->_right; } delete replace; } return true; } } return false; }key/value
使用场景
在现实生活中会遇到很多key/value场景。
如：1.简单中英互译字典，树的结构中(结点)存储key(英⽂)和vlaue(中⽂)，搜索时输⼊英⽂，则同时 查找到了英⽂对应的中⽂。
2.统计⼀篇⽂章中单词出现的次数，读取⼀个单词，查找单词是否存在，不存在这个说明第⼀次出现，（单词，1），单词存在，则++单词对应的次数。
代码实现
其实key/value的实现和key时类似的，需要注意的是key/value场景下的value是可以冗余的，因为是以key为主体进行的。（注意：std库中key和value放在了pair的结构体当中，是为了达到返回多个值的目的）
template<class K,class V> struct BSTreeNode { K _key; V _value; BSTreeNode<K,V>* _left; BSTreeNode<K,V>* _right; BSTreeNode(const K& key,const V& value) :_key(key) ,_value(value) , _left(nullptr) , _right(nullptr) {} }; template<class K,class V> class BSTree { typedef BSTreeNode<K,V> Node; public: 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->_left = cur; } else { parent->_right = cur; } return true; } BSTreeNode<K,V>* 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 (cur == _root) { _root = cur->_right; } else { if (parent->_left == cur) { parent->_left = cur->_right; } else { parent->_right = cur->_right; } } delete cur; } //右节点为空 else if (cur->_right == nullptr) { if (cur == _root) { _root = cur->_left; } else { if (parent->_right == cur) { parent->_right = cur->_left; } else { parent->_left = cur->_left; } } delete cur; } //有双亲节点 else { Node* parentreplace = cur; Node* replace = cur->_right; while (replace->_left) { parentreplace = replace; replace = replace->_left; } swap(replace->_key, cur->_key); swap(replace->_value, cur->_value); if (parentreplace->_left == replace) { parentreplace->_left = replace->_right; } else { parentreplace->_right = replace->_right; } delete replace; } return true; } } return false; } //析构函数 ~BSTree() { Destroy(_root); _root = nullptr; } void Destroy(Node* root) { if (root == nullptr) { return; } Destroy(root->_left); Destroy(root->_right); delete root; } private: Node* _root = nullptr; };
