C++进阶——二叉搜索树

在我写BinarySearchTree的拷贝构造时，发现 BSTree(const BSTree& t) { _root = Copy(t._root); // 访问 t 的私有成员 _root } 为什么，_root明明是私有的。 这种设计是为了支持类的封装性和实现细节的隐藏，同时允许类的成员函数在需要时访问其他同类对象的私有成员 。例如：

• 拷贝构造函数需要访问被拷贝对象的内部状态。
• 赋值运算符需要访问右操作数的内部状态。
• 比较运算符可能需要访问两个对象的内部状态。

1、二叉搜索树的概念

二叉搜索树 又称二叉排序树 ，它或者是一棵空树，或者是具有以下性质的二叉树: • 若它的左子树不为空，则左子树上所有结点的值 都 < = 根结点的值 。 • 若它的右子树不为空，则右子树上所有结点的值 都 > = 根结点的值 。 • 它的左右子树也 分别为二叉搜索树 。 • 二叉搜索树中可以支持插入相等的值，也可以不支持插入相等的值，本节实现的是不允许冗余 。 后续我们学习map/set/multimap/multiset系列容器底层就是二叉搜索树，其中map/set****不支持插入相等值 ，multimap/multiset****支持插入相等值 。

2、二叉搜索树的性能分析

最优 ：二叉搜索树为完全二叉树(或者接近完全二叉树)，高度 为：log₂N 最差 ：二叉搜索树退化为单支树(或者类似单支)，高度 为：N

• 最优情况 和平均情况 的时间复杂度是 O(log₂N) 。
• 最差情况 的时间复杂度是 O(N) 。 为了避免二叉搜索树退化为单支树 ，我们后续需要将二叉搜索树变形为 ，AVL树 和红黑树 等， 这些树在插入和删除时会自动调整结构 ，确保树的高度始终接近 log₂N ，从而保证操作的时间复杂度 为 O(log₂N) 。 注意：**二分查找 也可以实现 O(log₂N) 级别的查找** 效率，但是二分查找有两大缺陷 ： 1 需要 存储在支持下标随机访问 的结构中，并且有序 。 2 插入和删除数据效率很低 ，因为存储在下标随机访问的结构中。

3、二叉搜索树的插入

插⼊的具体过程如下： 1 树为空 ，则直接新增结点 ，赋值给 root指针。 2 树不空 ，按二叉搜索树性质，插入值比当前结点大 往右 走，插入值比当前结点小 往左 走，找到空位置，插入新结点。 3 如果支持插入相等的值，插入值跟当前结点相等的值可以都往右走，也可以都往左走，找到空位置，插入新结点。 bool Insert(const K& key) { if (_root == nullptr) { _root = new Node(key); return true; } Node* parent = nullptr; Node* cur = _root; while (cur) { if (key < cur->_key) { parent = cur; cur = cur->_left; } else if (key > cur->_key) { parent = cur; cur = cur->_right; } else { return false; // key不允许冗余 } } // cur就是放key的节点指针 cur = new Node(key); if (key < parent->_key) parent->_left = cur; else parent->_right = cur; return true; }

4、二叉搜索树的查找

1 从根开始比较，查找x，x比根的值大 则往右 边走查找，x比根值小 则往左 边走查找。 2 最多查找高度次，走到到空 ，还没找到 ，这个值不存在 。 3 如果不支持插入相等的值 ，找到x即可返回 。 4 如果支持插入相等的值 ，意味着有多个x存在，一般要求 查找中序 的第一个x。如下图，查找3，要找到1的右孩子的那个3返回。 Node* Find(const K& key) { Node* cur = _root; while (cur) { if (key > cur->_key) cur = cur->_right; else if (key < cur->_key) cur = cur->_left; else return cur; } return nullptr; }

5、二叉搜索树的删除

首先元素不存在 ，返回 false。 元素存在 则分以下四种情况：（假设要删除的结点为N） 1 要删除结点N左右孩子均为空 。 2 要删除的结点N左孩子为空 ，右孩子结点不为空 。 3 要删除的结点N右孩子为空 ，左孩子结点不为空 。 4 要删除的结点N左右孩子结点均不为空 。 对应以上四种情况的解决方案： 1 把N结点的父亲对应N的指针指向空，直接删除N结点（情况1可以当成2或者3处理 ，效果是一样的）。 2 把N结点的父亲对应N的指针 指向N的右孩子 ，直接删除N结点 。 3 把N结点的父亲对应N的指针 指向N的左孩子 ，直接删除N结点 。 4 无法直接删除N结点 ，因为N的两个孩子无处安放 ，只能用替换法删除 。找N左子树的值最大结点R(最右结点)或者N右子树的值最小结点R(最左结点)替代N(只是交换Node中的key) ，因为这两个结点中任意一个，放到N的位置，都满足二叉搜索树的规则。转而变成删除R结点 ，R结点符合情况2或情况3 ，可以直接删除。 代码采用交换N右子树的最左节点(即最小节点)。 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 break; } if (cur == nullptr) return false; if (cur->_left == nullptr) { if (parent == nullptr) // 当cur == _root时 _root = cur->_right; else if (parent->_left == cur) parent->_left = cur->_right; else parent->_right = cur->_right; delete cur; return true; } else if (cur->_right == nullptr) { if (parent == nullptr) // 当cur == _root时 _root = cur->_left; else if (parent->_left == cur) parent->_left = cur->_left; else parent->_right = cur->_left; delete cur; return true; } else { // parent带两个孩子带不过来，采用交换 Node* replaceParent = cur; Node* replace = cur->_right; while (replace->_left) // 跳出时，replace是右子树最左节点 { replaceParent = replace; replace = replace->_left; } swap(cur->_key, replace->_key); if (replace == replaceParent->_left) replaceParent->_left = replace->_right; else replaceParent->_right = replace->_right; delete replace; return true; } }

6、二叉搜索树的代码实现

BinarySearchTree.h #include #include using namespace std; namespace key { template struct BSTreeNode { typedef BSTreeNode Node; K _key; Node* _left; Node* _right; BSTreeNode(const K& key = K()) :_key(key) ,_left(nullptr) ,_right(nullptr) {} }; template class BSTree { typedef BSTreeNode Node; public: BSTree() {};// 默认构造 BSTree(const BSTree& t) { _root = Copy(t._root); } BSTree& operator=(const BSTree& t) { BSTree tmp(t); swap(_root,tmp._root); return this; } ~BSTree() { Destroy(_root); _root = nullptr; } bool Insert(const K& key) { if (_root == nullptr) { _root = new Node(key); return true; } Node parent = nullptr; Node* cur = _root; while (cur) { if (key < cur->_key) { parent = cur; cur = cur->_left; } else if (key > cur->_key) { parent = cur; cur = cur->_right; } else { return false; // key不允许冗余 } } // cur就是放key的节点指针 cur = new Node(key); if (key < parent->_key) parent->_left = cur; else parent->_right = cur; return true; } Node* Find(const K& key) { Node* cur = _root; while (cur) { if (key > cur->_key) cur = cur->_right; else if (key < cur->_key) cur = cur->_left; else return cur; } return nullptr; } 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 break; } if (cur == nullptr) return false; if (cur->_left == nullptr) { if (parent == nullptr) // 当cur == _root时 _root = cur->_right; else if (parent->_left == cur) parent->_left = cur->_right; else parent->_right = cur->_right; delete cur; return true; } else if (cur->_right == nullptr) { if (parent == nullptr) // 当cur == _root时 _root = cur->_left; else if (parent->_left == cur) parent->_left = cur->_left; else parent->_right = cur->_left; delete cur; return true; } else { // parent带两个孩子带不过来，采用交换 Node* replaceParent = cur; Node* replace = cur->_right; while (replace->_left) // 跳出时，replace是右子树最左节点 { replaceParent = replace; replace = replace->_left; } swap(cur->_key, replace->_key); if (replace == replaceParent->_left) replaceParent->_left = replace->_right; else replaceParent->_right = replace->_right; delete replace; return true; } } void InOrder() { _InOrder(_root); // 类内部可以访问_root cout « endl; } private: void _InOrder(Node* root) { if (root == nullptr) return; _InOrder(root->_left); cout « root->_key « " “; _InOrder(root->_right); } 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; } void Destroy(Node* root) // 后序 { if (root == nullptr) return; Destroy(root->_left); Destroy(root->_right); delete root; } Node* _root = nullptr; }; } Test.cpp #include “BinarySearchTree.h” int main() { key::BSTree BST; int a[] = { 8, 3, 1, 10, 1, 6, 4, 7, 14, 13}; for (auto& e : a) { BST.Insert(e); } BST.InOrder(); key::BSTree BST1 = BST; key::BSTree BST2; for (auto& e : a) { BST.Erase(e); } BST2 = BST1; return 0; }

7、二叉搜索树的key和key/value的使用场景

7.1 key搜索场景

只有key作为关键码，结构中只需要存储key 即可，搜索场景只需要判断key存不存在。 key的搜索场景实现的二叉树搜索树支持增删查 ，但是不支持修改 ，修改 key会破坏搜索树性质。 场景1：小区无人值守车库，小区车库买了车位的业主车才能进小区 ，那么物业会把买了车位的业主的车牌号录入后台系统，车辆进入时扫描车牌在不在系统中，在则抬杆，不在则提示非本小区车，无法进入。 场景2：检查一篇英文文章单词拼写是否正确 ，将词库中所有单词放入二叉搜索树，读取文章中的单词，查找是否在二叉搜索树中，不在则波浪线标红提示。

7.2 key/value搜索场景

树的结构中(结点)除了需要存储key还要存储对应的value ，增/删/查还是以key为关键字 走二叉搜索树的规则进行比较，可以快速查找到key对应的value。 key/value的搜索场景实现的二叉树搜索树，不支持修改 key，修改key破坏搜索树性质了，可以修改 value。 场景1：简单中英互译字典 ，树的结构中(结点)存储key(英文)和vlaue(中文)，搜索时输入英文，则同时查找到了英文对应的中文。 场景2：商场无人值守车库，入口进场时扫描车牌，记录车牌和入场时间 ，出口离场时，扫描车牌，查找入场时间，用当前时间- 入场时间计算出停车时长，计算出停车费用 ，缴费后抬杆，车辆离场。 场景3：统计一篇文章中单词出现的次数 ，读取一个单词，查找单词是否存在，不存在这个说明第一次出现，（单词，1），单词存在，则++单词对应的次数。

7.3 key/value二叉搜索树代码实现

BinarySearchTree.h #include #include using namespace std; namespace key_value // { template // struct BSTreeNode { typedef BSTreeNode Node; // K _key; V _value; // Node* _left; Node* _right; BSTreeNode(const K& key = K(),const V& value = V()) // :_key(key) ,_value(value) // , _left(nullptr) , _right(nullptr) { } }; template // class BSTree { typedef BSTreeNode Node; public: BSTree() {};// 默认构造 BSTree(const BSTree& t) { _root = Copy(t._root); } BSTree& operator=(const BSTree& t) { BSTree tmp(t); swap(_root, tmp._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 (key < cur->_key) { parent = cur; cur = cur->_left; } else if (key > cur->_key) { parent = cur; cur = cur->_right; } else { return false; // key不允许冗余 } } // cur就是放key的节点指针 cur = new Node(key,value); // if (key < parent->_key) parent->_left = cur; else parent->_right = cur; return true; } Node* Find(const K& key) { Node* cur = _root; while (cur) { if (key > cur->_key) cur = cur->_right; else if (key < cur->_key) cur = cur->_left; else return cur; } return nullptr; } 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 break; } if (cur == nullptr) // 没有找到key return false; if (cur->_left == nullptr) { if (parent == nullptr) // 当cur == _root时 _root = cur->_right; else if (parent->_left == cur) parent->_left = cur->_right; else parent->_right = cur->_right; delete cur; return true; } else if (cur->_right == nullptr) { if (parent == nullptr) // 当cur == _root时 _root = cur->_left; else if (parent->_left == cur) parent->_left = cur->_left; else parent->_right = cur->_left; delete cur; return true; } else { // parent带两个孩子带不过来，采用交换 Node* replaceParent = cur; Node* replace = cur->_right; while (replace->_left) // 跳出时，replace是右子树最左节点 { replaceParent = replace; replace = replace->_left; } swap(cur->_key, replace->_key); swap(cur->_value, replace->_value); // if (replace == replaceParent->_left) replaceParent->_left = replace->_right; else replaceParent->_right = replace->_right; delete replace; return true; } } void InOrder() { _InOrder(_root); // 类内部可以访问_root cout « endl; } private: void _InOrder(Node* root) { if (root == nullptr) return; _InOrder(root->_left); cout « root->_key « “:” « root->_value « endl; // _InOrder(root->_right); } Node* Copy(Node* root) // 后序 { if (root == nullptr) return nullptr; Node* newNode = new Node(root->_key,root->_value); // newNode->_left = Copy(root->_left); newNode->_right = Copy(root->_right); return newNode; } void Destroy(Node* root) // 后序 { if (root == nullptr) return; Destroy(root->_left); Destroy(root->_right); delete root; } Node* _root = nullptr; }; } Test.h #include “BinarySearchTree.h” int main() { key_value::BSTree dict; dict.Insert(“insert”, “插入”); dict.Insert(“erase”, “删除”); dict.Insert(“left”, “左边”); dict.Insert(“string”, “字符串”); string str; while (cin » str) { auto ret = dict.Find(str); if (ret) { cout « str « “:” « ret->_value « endl; } else { cout « “单词拼写错误” « endl; } } string strs[] = { “苹果”, “西瓜”, “苹果”, “樱桃”, “苹果”, “樱桃”, “苹果”, “樱桃”, “苹果” }; // 统计水果出现的次 key_value::BSTree countTree; for (auto str : strs) { auto ret = countTree.Find(str); if (ret == NULL) { countTree.Insert(str, 1); } else { ret->_value++; } } countTree.InOrder(); return 0; }