【高阶数据结构】深度探索二叉树进阶：二叉搜索树概念及其高效实现

高阶数据结构	相关知识点	可以通过点击	以下链接进行学习	一起加油！

本章是高阶数据结构笔记的第一篇文章，将分享二叉搜索树的进阶概念及其高效实现的相关知识，欢迎大家阅读！

🌈个人主页：是店小二呀
🌈C语言专栏：C语言
🌈C++专栏： C++
🌈初阶数据结构专栏： 初阶数据结构
🌈高阶数据结构专栏： 高阶数据结构
🌈Linux专栏： Linux

🌈喜欢的诗句:无人扶我青云志 我自踏雪至山巅

一、二叉搜索树概念

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

• 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值

• 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值

• 它的左右子树也分别为二叉搜索树

• 现阶段二叉搜索树没有重复的数据

二、二叉搜索树的创建

2.1 二叉搜索树的基本单位

template<class K>struct  BSTreeNode{BSTreeNode(const K& key = K()):_left(nullptr), _right(nullptr), _key(key){}BSTreeNode<K>* _left;BSTreeNode<K>* _right;K _key;};

2.2 实现二叉搜索树的基本框架

template<class K>class  BSTree{public://类型名字太长，不方便typedef BSTreeNode<K> Node;private:Node* _root = nullptr;};

上面图示以物理结构数组int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13}创建出来的逻辑结构二叉搜索树的数据结构。

2.3 二叉搜索树的查找

二叉搜索树查找步骤:

• 规定一个关键值key
• 从根开始开始比较查找，key比根大则往右边走查找，key比根小则往左边走查找
• 最多查找高度次，走到到空，还没有找到，这值不存在
• 在插入接口中，虽然查找合适位置代码逻辑差不多，但是存在个别逻辑差异，注意识别

bool Find(const K& key)
{Node* cur = _root->_key;while (cur){if (key < cur->_key){cur = cur->_left;}else if(key > cur->_key){cur = cur->_right;}else{return true;}}return  false;
}

2.4 二叉搜索树的插入

插入具体过程:

• 树为空，则直接新增节点，赋值给root指针
• 树不为空，按二叉搜索树性质插入位置，插入新节点

bool Insert(const K& key)
{if (_root == nullptr){_root = new Node(key);return true;}Node* parent = nullptr;//这里cur是临时变量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 if (parent->_key > key){parent->_left = cur;}return true;
}

插入具体过程细节处理:

• 需要判断树是否为空树，如果为空，创建节点赋值给_root
• 创建两个指针parent和cur保证节点的连接
• 通过不同比较大小，直到cur找到为空的位置，创建节点
• 该节点需要满足二叉搜索树的特性，需要再次判断，选择连接

2.5 二叉搜索树的删除(难点)

2.5.1 删除该子树根节点情况分析

首先查找元素是否在二叉搜索树中，如果不存在则返回false，否则要删除的节点可能分为下面三种情况。先到需要被删除的节点，这里就不重复实现了。

删除节点情况划分：

1. 要删除的节点无孩子节点
2. 要删除的节点只有一个孩子节点
3. 要删除的节点有左、右孩子节点

2.5.2 删除第一、二情况节点

这里第一种和第一种情况可以归类为同一种情况。无论被删除节点是否有无真实存在的孩子节点，都可以看成要删除的节点只有一个孩子节点，将第一种情况看成第二种情况，被删除节点有空孩子节点。

if (cur->_left == nullptr)
{if (parent->_left == cur){parent->_left = cur->_right;}else if (parent->_right == cur){parent->_right = cur->_right;}delete cur;
}
else if (cur->_right == nullptr)
{if (parent->_left == cur){parent->_right = cur->_left;}else if (parent->_right == cur){parent->_left = cur->_left;}delete cur;
}

关于数据结构学习，我们需要借助具体的逻辑结构去实现"抽象"的物理结构。接下我也希望你们可以借助图和文字进行对代码的解读。

1. 第一个判断分支决定，parent指向另外一个可能为空的节点。

2. 第二个分支判断被删除节点相对parent节点的位置

判断结束后，parent节点进行连接操作进行删除操作。

3. 小总结：判断被删除节点位置与被删除节点可能不为空孩子位置，进行连接即可。

草稿说明，上面是优化版本说明:

有了上面两个信息的话，比如通过parent->_left == cur需要被删除的节点是左节点，并且cur->_left == nullptr该节点左孩子节点为空，那么parent->_left = cur->_right;。parent->_left 是根据第一个条件，该parent->_left需要重新连接新节点，那么新节点是谁？通过cur->_left == nullptr判断，该左孩子为空，肯定连接右孩子节点。

2.5.3 第三种情况（替换法）

使用替换法删除，简单回顾

• 左子树上所有节点的值都小于根节点的值
• 右子树上所有节点的值都大于根节点的值

被替换的节点需要满足左子树最大节点或者右字数的最小节点其中之一即可。比如满足左子树最大节点，进行交换，该节点满足比左子树都要大，比右子树都要小。

替换法删除的具体流程:

• 先找到需要被删除节点和被替换节点，进行swap交换数字
• 通过第一、二种情况进行删除操作
• 那么需要设置两个指针去需要被替换节点

Node* RightMinParent = cur;
Node* RightMin = cur->_right;//找到右子树最小的值
while (RightMin->_left)
{RightMinParent = RightMin;RightMin = RightMin->_left;
}
//找到
swap(cur->_key, RightMin->_key);if (RightMinParent->_left == RightMin)
{RightMinParent->_left = RightMin->_right;
}
else
{RightMinParent->_right = RightMin->_right;
}
delete RightMin;
}
return true;

实现该逻辑的具体细节:

• 这里我选择找到右子树的最小节点，那么只需要关注左边的情况就行了，这也是为什么是while (RightMin->_left)
• 首先就是第一、二种情况删除的做法
• RightMinParent不能设置为空指针当删除根节点就会有问题，直接设置为cur

以上三种情况都需要考虑需要被删除节点为根节点

2.6 采用中序遍历二叉搜索树

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

中序遍历能够按顺序输出树中所有节点的值。从根节点开始，中序遍历的顺序是【左子树 , 根节点 , 右子树】这一过程在BST中恰好能保证节点按从小到大的顺序排列。将内部实现放在private部分，可以避免外部代码错误地调用内部方法，导致程序行为不可预测或出错。通过控制访问权限。外部代码不应该直接操作树的节点，而应该通过公开的接口方法来访问和操作树。

三、改造二叉搜索树，进行实际应用

K模型:K模型即只有key作为关键码，结构种只需要存储key即可，关键码即为需要搜索到的值

使用场景:判断单词是否拼写正确

• 将词库中所有单词集合中的每个单词作为key，构建一颗二叉搜索树
• 在二叉搜索树中查找单词是否存在，存在则为正确，否则错误

KV模型:每一个关键码key，都有与之对应的值Value，即<K,Value>的键值对

使用场景：翻译语言(底层主要还是B树)

• 比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文<word, chinese>就构成一种键值对
• 再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是<word, count>就构成一种键值对

// 改造二叉搜索树为KV结构
template<class K, class V>struct BSTNode{BSTNode(const K& key = K(), const V& value = V()): _pLeft(nullptr) , _pRight(nullptr), _key(key), _Value(value){}BSTNode<T>* _pLeft;BSTNode<T>* _pRight;K _key;V _value};
template<class K, class V>class BSTree{typedef BSTNode<K, V> Node;typedef Node* PNode;public:BSTree(): _pRoot(nullptr){}PNode Find(const K& key);bool Insert(const K& key, const V& value)bool Erase(const K& key)private:PNode _pRoot;};
void TestBSTree3()
{// 输入单词，查找单词对应的中文翻译BSTree<string, string> dict;dict.Insert("string", "字符串");dict.Insert("tree", "树");dict.Insert("left", "左边、剩余");dict.Insert("right", "右边");dict.Insert("sort", "排序");// 插入词库中所有单词string str;while (cin>>str){BSTreeNode<string, string>* ret = dict.Find(str);if (ret == nullptr){cout << "单词拼写错误，词库中没有这个单词:" <<str <<endl;}else{cout << str << "中文翻译:" << ret->_value << endl;}}
}
void TestBSTree4()
{// 统计水果出现的次数string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜","苹果", "香蕉", "苹果", "香蕉" };BSTree<string, int> countTree;for (const auto& str : arr){// 先查找水果在不在搜索树中// 1、不在，说明水果第一次出现，则插入<水果, 1>// 2、在，则查找到的节点中水果对应的次数++//BSTreeNode<string, int>* ret = countTree.Find(str);auto ret = countTree.Find(str);if (ret == NULL){countTree.Insert(str, 1);}else{ret->_value++;}}countTree.InOrder();
}

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

插入和删除操作都必须先查找的，查找效率代表了二叉搜索树中各个操作的性能

对于对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。
但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜

• 最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)
• 最差情况下，二叉搜索树退化为单支树(或者类似单支)

如果退化成单支树，二叉搜索树的性能就失去了 ，我们后续章节学习的AVL树和红黑树就可以上场了

六、Binary_Search_Tree.h

#pragma once
#include <string>template<class K>struct  BSTreeNode{BSTreeNode(const K& key = K()):_left(nullptr), _right(nullptr), _key(key){}BSTreeNode<K>* _left;BSTreeNode<K>* _right;K _key;};template<class K>class  BSTree{public:typedef BSTreeNode<K> Node;//插入操作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 if (parent->_key > key){parent->_left = cur;}return true;}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 if (parent->_right == cur){parent->_right = cur->_right;}}delete cur;}else if (cur->_right == nullptr){if (cur == _root){_root = cur->_right;}else{if (parent->_left == cur){parent->_right = cur->_left;}else if (parent->_right == cur){parent->_left = cur->_left;}}delete cur;}//替换法实现else{Node* RightMinParent = cur;Node* RightMin = cur->_right;//找到右子树最大的值while (RightMin->_left){RightMinParent = RightMin;RightMin = RightMin->_left;}//找到swap(cur->_key, RightMin->_key);if (RightMinParent->_left == RightMin){RightMinParent->_left = RightMin->_right;}else{RightMinParent->_right = RightMin->_right;}delete RightMin;}return true;}}return false;}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 false;}}return true;}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;};

---

感谢大家的观看！以上就是本篇文章的全部内容。我是店小二，希望这些高阶数据结构笔记能为你在学习旅途中提供帮助！