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

目录

一、基本概念

二、性能分析

三、模拟实现

四、使用场景

1.key搜索场景

2.key/value搜索场景

---

一、基本概念

二叉搜索树（Binary Search Tree），看名字就知道,是可以用来搜索数据的一种二叉树。

它可以是空树（一个数据都没有的二叉搜索树），也可以只有一个根结点，这都是比较特殊的情况。但其实二叉搜索树都是从一个根节点开始构建的，然后一个结点一个结点的插入，就会形成一个比较大型的二叉搜索树。

像这样：

仔细观察就可以发现，对于每一个结点，它的左孩子结点数据比它小，右孩子结点数据比它大。

其实，对于每一个结点，它的左子树所有结点的数据都会比它小，右子树所有结点的数据都会比它大，它的左子树和右子树又分别也是一颗二叉搜索树。

另外，看一下它的中序遍历序列：[1,3,4,6,7,8,10,13,14]，可以发现是升序的，这是因为：二叉搜索树的最小单元（一父+二子）的中序遍历是升序的，那么递归下来，自然整个二叉搜索树的中序遍历序列也是升序的了。 

肯定有人会疑惑，左子树的结点数据也可能比根结点的数据大吧？！

这是不会的，因为在二叉搜索树构建的过程中，结点的插入是靠循环，如果比当前结点数据大，就往右走，小，就往左走。就像上面的图中，根结点的左子树中最大数字位7，如果是9，那么9必然会在插入的时候就插入到根结点的右子树上。

二叉搜索树可以实现出两个版本：支持插入相同数据/不支持插入相同数据，两者要看应用场景来看具体使用哪一种情况。

到后面，我们会学习map/set、multimap/multiset，它们的底层就是二叉搜索树，前一组不支持插入相等值，二后一组支持。

二、性能分析

二叉搜索树，听名字就知道是为查找而生。

以我们之前学习的经验，查找效率取决于该二叉搜素树的高度。（最坏情况下要进行最大高度次查找）

如果该二叉搜索树是满二叉树，那么就是比较理想的情况，查找效率为O（logN）；

但是如果极端情况下，像下图这样，查找效率就会变成O（N）。

想要解决这种情况当然是有办法的，也就是建立平衡二叉搜索树，不过这个知识不是本博客的重点，到后面的博客会详细说。

三、模拟实现

先说明，我们的模拟实现对于增删查改只实现了增删查，不实现改的操作，很好理解，如果把二叉搜索树某个结点的数据修改了，那么这个二叉搜索树的结构也就可能被破坏掉了，在后续需要进行的搜索操作中很容易出现错误。

如果你非得想实现改，建议直接删除+插入。

---

先搭建出整体框架：

// BinarySearch.h
#pragma once
#include <iostream>
using namespace std;// K : key
template<class K>
struct BSTNode
{K _key;BSTNode<K>* _left;BSTNode<K>* _right;BSTNode(K key):_key(key),_left(nullptr),_right(nullptr){}
};template<class K>
class BSTree
{using Node = BSTNode<K>;public:private:Node* _root;
};

下面这里是中序遍历以及增查（删除后面重点说）：

// BinarySearch.h
#pragma once
#include <iostream>
using namespace std;// K : key
template<class K>
struct BSTNode
{K _key;BSTNode<K>* _left;BSTNode<K>* _right;BSTNode(K key):_key(key),_left(nullptr),_right(nullptr){}
};template<class K>
class BSTree
{using Node = BSTNode<K>;
public:// 查找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 Insert(const K& key){if (_root == nullptr){_root = new Node(key);return true;}// Node* newnode = new Node(key);// 在下面直接让cur变成新结点，就省去这一步了// 注意                    *parentNode* cur = _root, *parent = _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;}// 删除bool Erase(const K& key){}// 中序遍历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;
};// Test.cpp
#include "BinarySearch.h"int main()
{BSTree<int> bst;int a[] = { 8, 3, 1, 10, 1, 6, 4, 7, 14, 13 };for (auto e : a){bst.Insert(e);}bst.InOrder();return 0;
}

二叉搜索树的删除：

二叉搜索树的删除，所需要删除的结点类型有种：

1.叶子结点：直接删就行，父结点对应位置置空

2.只有一个孩子的父结点：把唯一一个孩子给该父结点的父结点，再删除该结点即可

3.有两个孩子的父结点：这就有点麻烦了......

之前学过堆，有可能能想出这种方法：

让需要删除的结点和某个结点交换数据，然后删除该结点，再把交换上来的结点向下调整，这种方法看起来确实可行，那么就不妨一试。

选择的结点为哪个？为了保证删除效率我们尽量减少交换后向下调整的次数，所以尽量就是让它不需要向下调整即可。那么我们就可以达到：交换+删除结点（搜索二叉树结构不被破坏），即可成功删除指定结点。

结合这张图，我们要删除3，关于交换结点的选取，我们可以这样想：

1. 3的父结点是8，以3为根结点的搜索二叉树（后面叫3树）的值都是小于8的，所以无论交换3树上面的哪个结点，都不会影响交换上来的结点与8的关系。

2. 3树中3把左右子树分成了小于和大于3的两部分值，如果我们把3删去，那么充当分界值的数字只能是紧挨3的数字，在这里是1或4（3树的中序遍历：13467，紧挨3的是1和4），所以用1或4与3交换都可以(不会破坏二叉搜索树的结构)。

3.紧接着2，我们仔细观察搜索二叉树不难发现，1是3左子树的最大数据，4是3右子树的最小数据，也就是说，我们可以使要删除的结点与它左子树的最大数据结点或者右子树的最小数据结点交换，然后再删除交换到左子树最大/右子树最小结点的待删除结点。

4.左子树的最大数据在左子树的最右侧，右子树的最大数据在右子树的最左侧，它们肯定至多只有一个孩子，所以可以按照只有一个孩子的情况删除。

综合这4点，有左右孩子的结点的删除就很简单了。

理解了原理，代码就简单了，不过还是有不少细节问题需要注意的，大家看我的注释就ok了

// BinarySearch.h
#pragma once
#include <iostream>
using namespace std;// K : key
template<class K>
struct BSTNode
{K _key;BSTNode<K>* _left;BSTNode<K>* _right;BSTNode(K key):_key(key),_left(nullptr),_right(nullptr){}
};template<class K>
class BSTree
{using Node = BSTNode<K>;
public:// 删除bool Erase(const K& key){// 这个判断其实无所谓，因为_root是空的话也进不去查找结点的循环，直接返回false了//if (_root == nullptr)	return false;// 要删除结点，先查找这个结点，如果没有找到，cur最终会是nullptr，随后会跳出循环返回falseNode* cur = _root, * parent = _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{// 链接parent和右孩子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{// 链接parent和左孩子，然后再delete掉curif (parent->_left == cur)	parent->_left = cur->_left;else parent->_right = cur->_left;}// 删除结点delete cur;}// 左右孩子都有else{// 这里如果把replaceParent初始化为nullptr，那么就可能会出现没有进入循环，后面nullptr->_right的尴尬情况Node* replaceParent = cur;// 先右Node* replace = cur->_right;// 左左左左找右子树最小数据while (replace->_left){replaceParent = replace;replace = replace->_left;}// 把找到的结点数据给给curcur->_key = replace->_key;// 链接一下再删除// 这里的判断是必要的，因为看似我们向cur的右之后一直左左左左，那么应该一定是replaceParent->_left = replace->_right// 但其实如果刚开始replaceParent = cur，replace = cur->_right，压根就没进入循环，也就是cur的右孩子没有左孩子了，那么就应该replaceParent->_right = replace->_rightif (replaceParent->_right == replace)	replaceParent->_right = replace->_right;else replaceParent->_left = replace->_right;// 删除“cur”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;
};// Test.cpp
#include "BinarySearch.h"int main()
{BSTree<int> bst;int a[] = { 8, 3, 1, 10, 1, 6, 4, 7, 14, 13 };for (auto e : a){bst.Insert(e);}bst.InOrder();for (auto e : a){bst.Erase(e);bst.InOrder();}return 0;
}

四、使用场景

1.key搜索场景

这个很好理解，就是在二叉搜索树中搜索有没有需要查找的K值，这里的K是指在二叉搜索树建立过程中比较大小用的key值。

比如小区的车库管理系统，系统识别出车的车牌号，并在存储此小区所有车主车牌号的二叉搜索树中搜索，如果找到了该车牌号，那么就抬杆，可以通过。如果没有找到，那么就不抬杆，不允许进入。这里的代表车牌号的字符串就是key，我们上面模拟实现的也是key搜索场景的二叉搜索树。

这是刚刚实现过的key搜索场景的整体代码，我把它用命名空间封装了一下，以便和key/value场景的区分： 

// BinarySearch.h
#pragma once
#include <iostream>
using namespace std;namespace key
{// K : keytemplate<class K>struct BSTNode{K _key;BSTNode<K>* _left;BSTNode<K>* _right;BSTNode(K key):_key(key), _left(nullptr), _right(nullptr){}};template<class K>class BSTree{using Node = BSTNode<K>;public:// 查找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 Insert(const K& key){if (_root == nullptr){_root = new Node(key);return true;}// Node* newnode = new Node(key);// 在下面直接让cur变成新结点，就省去这一步了// 注意                    *parentNode* cur = _root, * parent = _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;}// 删除bool Erase(const K& key){// 这个判断其实无所谓，因为_root是空的话也进不去查找结点的循环，直接返回false了//if (_root == nullptr)	return false;// 要删除结点，先查找这个结点，如果没有找到，cur最终会是nullptr，随后会跳出循环返回falseNode* cur = _root, * parent = _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{// 链接parent和右孩子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{// 链接parent和左孩子，然后再delete掉curif (parent->_left == cur)	parent->_left = cur->_left;else parent->_right = cur->_left;}// 删除结点delete cur;}// 左右孩子都有else{// 这里如果把replaceParent初始化为nullptr，那么就可能会出现没有进入循环，后面nullptr->_right的尴尬情况Node* replaceParent = cur;// 先右Node* replace = cur->_right;// 左左左左找右子树最小数据while (replace->_left){replaceParent = replace;replace = replace->_left;}// 把找到的结点数据给给curcur->_key = replace->_key;// 链接一下再删除// 这里的判断是必要的，因为看似我们向cur的右之后一直左左左左，那么应该一定是replaceParent->_left = replace->_right// 但其实如果刚开始replaceParent = cur，replace = cur->_right，压根就没进入循环，也就是cur的右孩子没有左孩子了，那么就应该replaceParent->_right = replace->_rightif (replaceParent->_right == replace)	replaceParent->_right = replace->_right;else replaceParent->_left = replace->_right;// 删除“cur”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;};
}// Test.cpp
#include "BinarySearch.h"int main()
{key::BSTree<int> bst;int a[] = { 8, 3, 1, 10, 1, 6, 4, 7, 14, 13 };for (auto e : a){bst.Insert(e);}bst.InOrder();for (auto e : a){bst.Erase(e);bst.InOrder();}return 0;
}

2.key/value搜索场景

这个也比较好理解，二叉搜索树建立过程中比较用的key值进行比较，而每一个结点中除了key值还有与key值相对应的value值，这个值可以是任何类型，一般来说都是表示和key相关联的属性。

就比如：

1.要统计一篇英语课文内出现的一些特定单词的出现次数，那么此时代表特定单词的字符串就是string，代表特定单词出现次数的就是value。建立一棵存储了这些特定单词的二叉搜索树，value都置为0，然后开始遍历这篇课文，把出现的每个单词都在该二叉搜索树中查找，如果找到了就value++，如果没有找到就不动。这样遍历下来，就会得到一个存储了特定单词在课文中出现次数的二叉搜索树，以后我们需要获取，只需要在这个二叉搜索树中搜索此单词，就能得到它在课文中出现的次数了。

2.商场地下停车场系统：key是车牌号，value是进入停车场的时间，车出停车场的时候，在树中搜索到该车牌号，然后用当前的时间减去value存的进入时间，计算得到需要支付的钱，然后付费成功后，再删除该车牌号的结点。

..............................

下面是key/value的代码，只需要在key的基础上略做修改即可，然后由于只有增删查的二叉搜索树还不是很完善，所以增添了拷贝构造和赋值重载以及析构函数。

// BinarySearch.h#pragma once
#include <iostream>
#include <algorithm>
using namespace std;namespace key_value
{// K : key, V:valuetemplate<class K, class V>struct BSTNode{K _key;V _value;BSTNode<K, V>* _left;BSTNode<K, V>* _right;BSTNode(K key, V value):_key(key),_value(value), _left(nullptr), _right(nullptr){}};template<class K, class V>class BSTree{using Node = BSTNode<K, V>;public:// 因为写拷贝构造了，这里强制生成一下其它构造BSTree() = default;// default，C++11,强制生成构造（所有）// 拷贝构造BSTree(const BSTree& bst){_root = Copy(bst._root);}// 析构~BSTree(){Destroy(_root);_root = nullptr;}// 赋值运算符重载// （现代写法）// 不能传const，传了就寄（bst._root）BSTree& operator=(BSTree bst){swap(_root, bst._root);return *this;}// 查找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 Insert(const K& key, const V& value){if (_root == nullptr){_root = new Node(key, value);return true;}Node* cur = _root, * parent = _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;}// 删除bool Erase(const K& key){Node* cur = _root, * parent = _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{// 链接parent和右孩子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{// 链接parent和左孩子，然后再delete掉curif (parent->_left == cur)	parent->_left = cur->_left;else parent->_right = cur->_left;}// 删除结点delete cur;}// 左右孩子都有else{// 这里如果把replaceParent初始化为nullptr，那么就可能会出现没有进入循环，后面nullptr->_right的尴尬情况Node* replaceParent = cur;// 先右Node* replace = cur->_right;// 左左左左找右子树最小数据while (replace->_left){replaceParent = replace;replace = replace->_left;}// 把找到的结点数据给给curcur->_key = replace->_key;// 链接一下再删除// 这里的判断是必要的，因为看似我们向cur的右之后一直左左左左，那么应该一定是replaceParent->_left = replace->_right// 但其实如果刚开始replaceParent = cur，replace = cur->_right，压根就没进入循环，也就是cur的右孩子没有左孩子了，那么就应该replaceParent->_right = replace->_rightif (replaceParent->_right == replace)	replaceParent->_right = replace->_right;else replaceParent->_left = replace->_right;// 删除“cur”delete replace;}return true;}}return false;}// 中序遍历void InOrder(){_InOrder(_root);cout << endl;}private:// 要封装嘛所以返回新根节点给给public的拷贝构造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;}// 销毁void Destroy(Node* root){if (root == nullptr)	return;// 先毁孩子再毁根，合理Destroy(root->_left);Destroy(root->_right);delete root;}void _InOrder(Node* root){// 空指针不能->，判一下空if (root == nullptr)	return;_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}private:Node* _root = nullptr;};
}// Test.cpp
#include <string>
#include <vector>
using namespace std;#include "BinarySearch.h"int main()
{key_value::BSTree<string, int> kvbst;vector<string> v = { "apple","banana","wohaoshuai","youxiaxieyige","haha","haha","apple","banana","wohaoshuai","haha" };for (auto e : v){auto retNode = kvbst.Find(e);if (retNode)	++retNode->_value;else kvbst.Insert(e, 1);}string s;cin >> s;cout << s << "出现了" << kvbst.Find(s)->_value << "次" << endl;key_value::BSTree<string, int> copy(kvbst);key_value::BSTree<string, int> ass;ass = kvbst;copy.InOrder();ass.InOrder();copy.Erase("apple");ass.Erase("haha");kvbst.InOrder();copy.InOrder();ass.InOrder();return 0;
}

---

完结撒花~~~~~~~

say顾拜~~~~~~~~~~~~~~~~~

“ψ(｀∇´)ψ