【C++】—— 二叉搜索树

1 二叉搜索树的概念

二叉搜索树又称二叉排序树，它或者是一颗空树，或者是具有以下性质的二叉树：

• 若它的左子树不为空，则左子树上所有节点的值都小于等于根节点的值
• 若它的右子树不为空，则右子树上所有节点的值都大于等于根节点的值
• 它的左右子树也都是二叉搜索树
• 二叉搜索树种可以支持插入相等的值，也可以不支持插入相等的值，具体看使用场景定义，后续我们学习 $map$ / $set$ / $multimap$ / $multiset$ 系列容器底层就是二叉搜索树，其中 $map$ / $set$ 不支持插入相等值，$multiset$ / $multimap$ 支持插入相等值

  

  
  

2 二叉搜索树的性能分析

• 最优情况下，二叉搜索树为完全二叉树（或者接近完全二叉树），其高度为：O(log₂ N)
• 最差情况下，二叉搜索树退化为单支树（或者类似单支），其高度为：O($N/2$)
• 所以综合而言二叉搜索树增删查改时间复杂度为：O(N)
    

  
  这样的二叉搜索树并不稳定，树的形状与数据的插入顺序息息相关（插入的数据是有序或较为有序的，二叉搜索树就退化成链式结构），这样的效率显然是无法满足时间的需求的。因此后续我们还将学习二叉搜索树的变形：AVL树 和 红黑树，他们才能适用于我们在内存中存储和搜索数据
  

  另外需要说明的是，二分查找也可以实现 O(logN) 级别的查找效率，但是二分查找有两大缺陷：

• 需要存储在支持下标随机访问的结构中，并且有序
• 插入和删除数据效率很低，因为存储在下标随机访问的结构中，插入和删除数据一般需要挪动数据。（我们查找一个数据往往不是单纯的查找，还要对其进行增删查改等相关操作）

  
  这也就体现出了平衡二叉搜索树的价值
  
  

3 二叉搜索树的实现

  搜索二叉树分为两种：允许插入相等的值和不允许插入相等的值。
  一般我们会分开用，实现两份搜索二叉树。
  本文实现的是不容许数值冗余的搜索二叉树
  

3.1 基本结构

  首先我们要定义二叉树节点，及二叉搜索树的基本结构

template<class K>
struct BSTNode
{K _key;BSTNode<K, V>* _left;BSTNode<K, V>* _right;BSTNode(const K& key):_key(key),_left(nullptr),_right(nullptr){}
};template<class K>
class BSTree
{using Node = BSTNode<K>;
public:private:Node* _root = nullptr;
};

  注：关于类型重命名，C++11 给了一个新用法：$using$。$using$ 与 $typedef$ 的功能是一样的，只有一些细微的差别，现阶段可认为是一样的。

  搜索二叉树，模板参数我们就不用 T 了，而用 K
  因为一般搜索的时候，我们都要进行一个比较：比他大往右边走，比他小往左边走。我们一般把用来比较的这个值称为 Key，也就是关键字。所以我们一般用 K 来做末模版参数

  

3.2 insert

  实现插入要怎么实现呢？前面我们学习二叉树的时候都是用递归，那这里也要用递归吗？

  可以用
  递归的逻辑是这样的
  要插入的值比当前根大，递归到其右子树；若比它小递归到其左子树；遇到空就插进去

  但是这里没必要用递归

  我们直接用循环就能够搞定
  我们最开始定义一个 $cur$ 指针指向树的根，假设现在插入的是 16，$cur$ 指向 8；16 比 8 大，$cur$ 往右边走；若比 $cur$ 小，往左边走，直到遇到空位。
  既能用循环又能用递归的情况下，我们无脑用循环。因为递归有栈溢出的风险，却需要建立栈帧，消耗一般比循环大。
  但我们不能直接 $new$ 一个结点给 $cur$。因为 $cur$ 只是一个临时变量，只给 $cur$，树并没有将这个节点链接起来，所以我们还要有个指针 $parent$ 记录 $cur$ 的父节点

  当然，还有一种特殊的情况：空树。这时直接让 _$root$ 指向一个 $new$ 出的新节点即可。
  

bool insert(const K& key)
{if (nullptr == _root){_root = new Node(key);return true;}Node* cur = _root;Node* parent = nullptr;while (cur != nullptr){if (cur->_key > key){parent = cur;cur = cur->_left;}else if (cur->_key < key){parent = cur;cur = cur->_right;}elsereturn false;}if (parent->_key > key)parent->_left = new Node(key);elseparent->_right = new Node(key);return true;	
}

  如果支持插入相等的值，插入值跟当前结点相等的值可以往右走，也可以往左走，找到空位置，插入新结点。（要注意的是要保持逻辑一致性，插入相等的值不要一会往右走，一会往左走）
  

3.3 中序遍历

  搜索二叉树有一个性质：中序遍历时，是有序的。
  中序遍历我们前面学习普通二叉树时实现过了，这里就不再过多介绍

void InOrder(Node* root)
{if (root == nullptr)return;_InOrder(root->_left);	cout << root->_key << " ";_InOrder(root->_right);
}

  
  但是这个中序有一个问题：不好调用
  因为想要调用中序来遍历搜索二叉树，要传递一个根节点 $root$。但是根是私有的，无法外面无法访问。

解决方式如下：

• 友有元
• 提供 $Get()$ 函数

  
  但这些方法或多或少有些麻烦，C++ 解决这种问题时，一般选择 在外面套一层函数。

class BSTNode
{
public:void InOrder(){_InOrder(_root);cout << endl;}private:void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);	cout << root->_key << " ";_InOrder(root->_right);}
}；

  虽然我们在类外不能访问 _root，但是类里面可以啊。
  这样，对外公开的接口我们就可以不用传根了
  

3.4 find

• 从根开始比较，查找 $x$，$x$ 比根的值大则往右边走查找，$x$ 比根值小则往左边走查找
• 最多查找高度次，走到空，还没找到，这个值不存在
• 如果不支持插入相等的值，找到 $x$ 即可返回
• 如果支持插入相等的值，意味着有多个 $x$ 的存在，一般要求查找中序的第一个 $x$。如下图，查找 3，要找到 1 的右孩子的那个 3 返回

  
  怎样才能找到中序第一个 3 呢？按中序遍历一遍吗？这样太慢了
  这里讲一下大致思路，感兴趣的小伙伴可自行实现：查找方式与上述步骤一致，有些许不同。我们知道中序遍历是：左子树、根、右子树，中序往往是先遍历左子树。因此我们按上述方式找到了 8 左节点的 3，还要进入这个 3 的左子树查找；若其左子树中有 3，再进入这个 3 的左子树；若左子树中无 3，则回退，表明这个左子树的根是中序第一个3。
  

Node* find(const K& key)
{Node* cur = _root;while (cur != nullptr){if (key > cur->_key){cur = cur->_right;}else if (key < cur->_key){cur = cur->_left;}elsereturn cur;}return nullptr;
}

  

3.5 erase

3.5.1 情况分析

二叉搜索树的删除比较麻烦，需分情况讨论

• 要删除的解决点 $N$ 左右节点都为空，即叶子节点
• 要删除的结点 $N$ 左孩子为空，右孩子结点不为空
• 要删除的结点 $N$ 右孩子为空，左孩子结点不为空
• 要删除的节点 $N$ 左右子树都不为空

  

对应以上四种解决方案

• 第一种情况：这种情况最好解决，将 N 节点的父亲对应孩子指针指向空，直接删除 N 节点（情况一可以当成情况二、三来处理，效果是一样的）
• 第二种情况：把 N 结点的父亲对应孩子指针指向 N 的右孩子，直接删除 N 结点
• 第三种情况：把 N 结点的父亲对应孩子指针指向 N 的左孩子⼦，直接删除 N 结点
• 第四种情况：无法直接删除 N 节点，因为 N 的两个孩子无处安放，我们可以用替换法删除。找到 N 左子树的值最大节点 R（最右节点）或者 N 右子树的最小节点 R（最左节点）替代 N，因为这两个节点中任意一个，放到 N 的位置，都满足二叉搜索树的规则。替代的意思就是 N 和 R 的两个节点的值交换，转而变成删除 R 节点，R 结点符合情况 2 或情况 3，可以直接删除

  

3.5.2 代码实现

  首先是查找，代码逻辑与 $find$ 的实现相似。
  不同的是，当找到相等的值（走到 $else$ 时），$erase$ 是进行删除；$find$ 是直接退出，当走出循环，表示没有找到要删除的值，$return$ $false$

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{// 删除}return false;
}

  
左为空：
  虽然要删除的节点 $N$ 左为空，但是并不知道 $N$ 节点是父节点 $R$ 的左节点还是右节点，因此需要先进行判断

// 左树为空
if (cur->_left == nullptr)
{if (parent->_left == cur){parent->_left = cur->_right;}else{parent->_right = cur->_right;}delete cur;
}

  
右为空：
  右为空的判断逻辑与左为空时一样的

// 右树为空
else if (cur->_right == nullptr)
{if (parent->_left == cur){parent->_left = cur->_left;}else{parent->_right = cur->_left;}delete cur;
}

  
  但是上述情况还有一种坑的情况，如图：

  假设现在我们要删除的是 8。
  这时就需要特殊处理，需要更新 _$root$ 了

// 左树为空
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->_left == cur){parent->_left = cur->_left;}else{parent->_right = cur->_left;}}delete cur;
}

  
左右都不为空
  这里我们假设找右树的最小节点（最左节点）来替代

else
{// 左右都不为空// 右子树最左节点Node* replaceParent = nullptr;Node* replace = cur->_right;//replace不断往右边走while (replace->_left){replaceParent = replace;replace = replace->_left;}//将替代节点replace的val值赋值给本来要删除的节点curcur->_key = replace->_key;//再删除replace节点，此时的replace只可能是前三种情况replaceParent->_left = replace->_right;delete replace;
}

  
  删除 $replace$ 还有一种很坑的情况：$cur$ 的右孩子就是最左节点。假设我们现在要删除 8

  因为 $cur$ 的右孩子就是最左节点，此时并没有进入循环，$replaceParent$ 还是空，执行 replaceParent->_left = replace->_right; 语句就会报错
  解决办法就是 $replaceParent$ 初值不要给 $nullptr$，而是给 $cur$
  最后删除 $replace$ 节点时，因为 $replace$ 是 $replaceParent$ 的右节点，所以应是将 $replace$ 的孩子给 $replaceParent$ 的右孩子，而不是左孩子。
  所以最后删除 $replace$ 节点时，要判断 $replace$ 是 $replaceParent$ 的左孩子还是右孩子
  

else
{Node* replaceParent = cur;Node* replace = cur->_right;while (replace->_left){replaceParent = replace;replace = replace->_left;}cur->_key = replace->_key;if (replaceParent->_left == replace)replaceParent->_left = replace->_right;elsereplaceParent->_right = replace->_right;delete replace;
}

  
  

3.5 默认成员函数

3.5.1 拷贝构造

  二叉树的拷贝构造一定要自己实现深拷贝，如果是编译器默认生成的浅拷贝，将是一个大坑。
  我们使用前序的方式来拷贝：

BSTree(const BSTree& t)
{_root = Copy(t._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;
}

  注：这里不能用一个一个插入的方式进行拷贝，因为这样的话树的形状就变了

  这里拷贝构造我们在外面套一层壳
  

3.5.2 构造函数

  这里编译器默认生成的构造函数就能满足我们的需求，但是我们已经实现了拷贝构造，拷贝构造本身也是一种构造，因此编译器就不会再生成构造函数。
  我们可以用 $default$ 强制编译器生成构造函数

// 强制生成构造
BSTree() = default;

  

3.5.3 赋值重载

  赋值重载我们直接用现代写法，让拷贝构造去干活

BSTree& operator=(BSTree tmp)
{swap(_root, tmp._root);return *this;
}

  

3.5.4 析构函数

  析构函数，我们一次通过后序的方式遍历所有节点，并将他们释放

~BSTree()
{Destroy(_root);_root = nullptr;
}
void Destroy(Node* root)
{if (root == nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;
}

  同理，析构函数我们在外面套一层外壳
  
  

4 二叉搜索树的应用

  搜索二叉树的使用场景分为两个：$key$ 搜索场景和 $key/value$ 搜索场景
  

4.1 key 搜索场景

  $key$ 搜索场景：即只有 $key$ 作为关键值，结构中只需要存储 $key$ 即可，关键值即为需要搜索到的值，搜索场景只需要判断 $key$ 在不在。$key$ 的搜索场景实现的二叉搜索树支持增删查，但是不支持修改，修改 $key$ 破坏搜索树结构了。

  一句话来说 $key$ 搜索场景就是用来判断在不在

  场景一：校区无人值守车库，小区车库只有买了车位的业主车才能进小区，那么物业会把买了车位的业主的车牌号录入后台系统（后台系统可以用搜索二叉树的结果来存储车牌号），车辆进入时扫描车牌在不在系统中，在则抬杆，不在则提示非本小区车辆，无法进入

  场景二：检查一篇英文文章单词拼写是否正确，将词库中所有单词放入二叉搜索树，读取文章中的单词，查找是否在二叉搜索树中，不在则波浪线标红提示
  

4.2 key/value 搜索场景

  $key$/$value$ 搜索场景：每一个关键值 $key$，都有与之对应的值 $value$，$value$ 可以任意类型对象。树结构中（节点）除了需要存储 $key$ 还要存储对应的 $value$，增/删/查还是以 $key$ 为关键字走二叉搜索树的规则进行比较，可以快速查找到 $key$ 对应的 $value$。$key$/$value$ 的搜索场景实现的二叉搜索树支持修改，那时 不支持修改 $key$，修改 $key$ 破坏搜索树结构了，可以修改 $value$

  场景1：简单中英互译字典。树的结构中（节点）存储key（英文）和value（中文），搜索黑丝输入英文，则同时查找到了引文对应的中文。

  场景2：商场无人值守车库，入口进场时扫描车牌，记录车牌（key）和入场时间（value）；出口离场时，扫描车牌，查找入场时间，用当前时间 - 入场时间计算出停车时长，计算出听出费用，缴费后抬杆，车辆离场

  场景3：统计一篇文章中单词出现的次数，读取一个单词，查找单词是否存在，不存在说明这个单词第一次出现，存在则++单词对应的次数
  
key/value模型的应用：
  输入单词，查找单词对应的中文翻译

void TestBSTree1()
{BSTree<string, string> dict;dict.Insert("string", "字符串");dict.Insert("left", "左边");dict.Insert("insert", "插入");string str;while (cin >> str){// 搜索二叉树结点的地址BSTreeNode<string, string>* cur = dict.Find(str);if (cur){cout << cur->_value << endl;}else{cout << "没有此单词" << endl;}}
}

  
统计水果个数：

void TestBSTree2()
{// 统计水果的个数string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
"苹果", "香蕉", "苹果", "香蕉","苹果","草莓", "苹果","草莓" };BSTree<string, int> countTree;for (const auto& str : arr){//BSTreeNode<string, int>* cur = countTree.Find(str);auto cur = countTree.Find(str);// 没有该水果则插入if (cur == nullptr){countTree.Insert(str, 1);}// 有该水果则将value值++else{cur->_value++;}}countTree.InOrder();
}

  

5 key 模型代码实现

namespace key
{template<class K>struct BSTNode{K _key;BSTNode<K>* _left;BSTNode<K>* _right;BSTNode(const K& key):_key(key), _left(nullptr), _right(nullptr){}};// Binary Search Tree// Keytemplate<class K>class BSTree{//typedef BSTNode<K> Node;using Node = BSTNode<K>;public: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;}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;}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->_left == cur){parent->_left = cur->_left;}else{parent->_right = cur->_left;}}delete cur;}else{// 左右都不为空// 右子树最左节点Node* replaceParent = cur;Node* replace = cur->_right;while (replace->_left){replaceParent = replace;replace = replace->_left;}cur->_key = replace->_key;if (replaceParent->_left == replace)replaceParent->_left = replace->_right;elsereplaceParent->_right = replace->_right;delete replace;}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 << " ";_InOrder(root->_right);}private:Node* _root = nullptr;};
}

6 key/value模型代码实现

namespace key_value
{template<class K, class V>struct BSTNode{const K _key;V _value;BSTNode<K, V>* _left;BSTNode<K, V>* _right;BSTNode(const K& key, const V& value):_key(key), _value(value), _left(nullptr), _right(nullptr){}};// Binary Search Tree// Key/valuetemplate<class K, class V>class BSTree{//typedef BSTNode<K> Node;using Node = BSTNode<K, V>;public:// 强制生成构造BSTree() = default;BSTree(const BSTree& t){_root = Copy(t._root);}BSTree& operator=(BSTree tmp){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 (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 (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->_left == cur){parent->_left = cur->_left;}else{parent->_right = cur->_left;}}delete cur;}else{// 左右都不为空// 右子树最左节点Node* replaceParent = cur;Node* replace = cur->_right;while (replace->_left){replaceParent = replace;replace = replace->_left;}cur->_key = replace->_key;if (replaceParent->_left == replace)replaceParent->_left = replace->_right;elsereplaceParent->_right = replace->_right;delete replace;}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;};
}

  
  
  
  
  

---

  好啦，本期关于二叉树的知识就介绍到这里啦，希望本期博客能对你有所帮助。同时，如果有错误的地方请多多指正，让我们在 C++ 的学习路上一起进步！