数据结构进阶：二叉搜索树_C++

目录

前言：

一、二叉搜索树

1.1二叉搜索树概念

2.2 二叉搜索树操作

1. 二叉搜索树的插入

1.1、插入过程

1.2、代码实现

2、二叉树的删除

2.1、结点删除情况

2.2、替换删除法

1、替换思路

2、代码实现：

3、二叉搜索树的查找

3.1、查找规则

3.2、代码实现

 二、二叉搜索树的应用

1. K模型

2、KV模型

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

---

前言：

1. map和set特性需要先铺垫二叉搜索树，而二叉搜索树也是一种树形结构

2. 二叉搜索树的特性了解，有助于更好的理解map和set的特性

3. 二叉树中部分面试题稍微有点难度，在前面讲解大家不容易接受，且时间长容易忘

4. 有些OJ题使用C语言方式实现比较麻烦，比如有些地方要返回动态开辟的二维数组，非常麻 烦。

一、二叉搜索树

1.1二叉搜索树概念

• 二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:
• 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
• 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
• 它的左右子树也分别为二叉搜索树

2.2 二叉搜索树操作

树的框架：

//结点
template<class K>
struct BSTreeNode
{BSTreeNode<K>* _left;BSTreeNode<K>* _right;K _key;BSTreeNode(const K& key):_left(nullptr), _right(nullptr), _key(key){}
};
//二叉搜索树的操作
template<class K>
class BSTree
{typedef BSTreeNode<K> Node;
private:Node* _root = nullptr;
};

1. 二叉搜索树的插入

1.1、插入过程

插入的具体过程如下：

a. 树为空，则直接新增节点，赋值给root指针

b. 树不空，按二叉搜索树性质查找插入位置，插入新节点

解释：假设我们要插入16、0，那我们就要根据二叉搜索树的特点来进行判断，想要插入16，从根节点开始，如果比根节点大，那么就走右子树，继续比较。如果比根节点小，那么就走左子树继续比较

所以我们的插入功能应该如何写呢?

1.2、代码实现

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;
}

细节解释：

1、我们最开始需要判断二叉树是否为空，如果不判断，cur就为空，就不会进入循环判断的同时，之后parent指向结点为野指针，不安全

2、在我们循环判断时，需要记录cur的父节点，cur最终找到的是插入位置，如果我们想成功插入，那么就需要由该位置的父节点进行链接

2、二叉树的删除

2.1、结点删除情况

  首先查找元素是否在二叉搜索树中，如果不存在，则返回, 否则要删除的结点可能分下面四种情 况：

a. 要删除的结点无孩子结点

b. 要删除的结点只有左孩子结点

c. 要删除的结点只有右孩子结点

d. 要删除的结点有左、右孩子结点

看起来有待删除节点有4中情况，实际情况a可以与情况b或者c合并起来，因此真正的删除过程如下：

情况a：直接删除

情况b：删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点--直接删除

情况c：删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点--直接删除

情况d：在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被删除节点 中，再来处理该结点的删除问题--替换法删除

情况a、b、c都好理解，情况a直接删除即可，情况bc是让被删除结点的孩子去顶替它的位置即可

难的是情况d,当它有两个孩子时应该怎么去选择，我们所用到的替换法删除又是什么呢？

2.2、替换删除法

1、替换思路

  我们所找的去替换被删除结点的值最重要的是能在该位置站得住脚---就是要比左孩子大，又要比右孩子小

  那哪些结点能站得住脚呢？

  是被删除结点的左子树的最大结点（右结点）或者右子树的最小结点（左结点）

  怎么理解？我们知道，父结点的左子树上的值，都要比父结点小，父结点的右子树上的值，都要比父结点大。我们再拿父结点的左孩子来说，同理比它小的值也同样会走到它的左子树上，比它大的值也同样会走到它的右子树上。

  那么我们就可以明白：被删除结点的左子树的最大右节或者右子树的最小左结点一定会比被删除结点的左孩子大，又比其右孩子小

  这也是搜索二叉数的特征：一棵树的左子树的最右节点是左子树的最大结点，一棵树的右子树的最左结点是右子树的最小结点

  另外需要注意的是，我们被删除结点的左子树的最大结点（右结点）或者右子树的最小结点（左结点是可以直接删除的，我们在上面已经分析过删除情况。

2、代码实现：

情况b、c再删除时又会遇到的情况：

1、被删除结点的左子树为空

  假如我们要删除结点3，且被删除结点的左子树为空，我们被删除结点的父结点就要链接被删除结点的右子树

2、被删除结点的右子树为空

 假如我们要删除结点3，且被删除结点的右子树为空，我们被删除结点的父结点就要链接被删除结点的左子树

情况d:

我们知道：

1、找被删除结点的左子树的最大右结点或者右子树的最左小结点（这个在后面的理解很重要！）

2、一棵树的左子树的最右节点是左子树的最大结点，一棵树的右子树的最左结点是右子树的最小结点

  所以我们需要先找到一个能站得住脚的结点，我们就拿右子树的最小结点举例，将它命名为rightMin

  我们找到rightMin再去将被删除结点与rightMin结点的值key交换，并且在找rightMin时再用一个中间变量rightMinParent去记录rightMin的父结点，最终在交换完key后我们需要删除交换后的rightMin就需要由父结点来链接。

  此时又会遇到两种情况：

1、rightMin如果是父结点rightMinParent的左结点，我们就需要让rightMinParent去链接rightMin的右节点（如果存在即链接，不存在即为空）

2、1、rightMin如果是父结点rightMinParent的右结点，我们就需要让rightMinParent去链接rightMin的右节点（如果存在即链接，不存在即为空）

删除函数代码：

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(parent == nullptr)if (cur == _root){_root = cur->_right;}else{if (cur == parent->_left){parent->_left = cur->_right;}else{parent->_right = cur->_right;}}delete cur;}else if (cur->_right == nullptr){//if(parent == nullptr)if (cur == _root){_root = cur->_left;}else{// 右为空，父亲指向我的左if (cur == parent->_left){parent->_left = cur->_left;}else{parent->_right = 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;elserightMinParent->_right = rightMin->_right;delete rightMin;}return true;}}return false;}

3、二叉搜索树的查找

3.1、查找规则

a、从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。

b、最多查找高度次，走到空，还没找到，这个值不存在

3.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;
}

 二、二叉搜索树的应用

1. K模型

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

  比如：给一个单词word，判断该单词是否拼写正确。

  具体方式如下：

• 以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树
• 在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。

这个我们需要一个词库，所以我们在这里先不做这个实现，我们用KV模型来实现

2、KV模型

每一个关键码key，都有与之对应的值Value，即的键值对。该种方 式在现实生活中非常常见：

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

我们先将KV模型代码写出来：

namespace key_value
{template<class K, class V>struct BSTreeNode{BSTreeNode<K, V>* _left;BSTreeNode<K, V>* _right;K _key;V _value;// pair<K, V> _kv;BSTreeNode(const K& key, const V& value):_left(nullptr), _right(nullptr), _key(key), _value(value){}};template<class K, class V>class BSTree{typedef BSTreeNode<K, V> Node;public:// logNbool 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 cur;}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(parent == nullptr)if (cur == _root){_root = cur->_right;}else{if (cur == parent->_left){parent->_left = cur->_right;}else{parent->_right = cur->_right;}}delete cur;}else if (cur->_right == nullptr){//if(parent == nullptr)if (cur == _root){_root = cur->_left;}else{// 右为空，父亲指向我的左if (cur == parent->_left){parent->_left = cur->_left;}else{parent->_right = 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;elserightMinParent->_right = rightMin->_right;delete rightMin;}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);}private:Node* _root = nullptr;};

这也只是在我们原先实现的基础上做改动。 

示例一：翻译单词

void TestBSTree2()
{BSTree<string, string> dict;dict.Insert("string", "字符串");dict.Insert("left", "左边");dict.Insert("insert", "插入");//...string str;while (cin >> str){BSTreeNode<string, string>* ret = dict.Find(str);if (ret){cout << ret->_value << endl;}else{cout << "无此单词，请重新输入" << endl;}}
}

示例二：计数

void TestBSTree3(){// 统计次数string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
"苹果", "香蕉", "苹果", "香蕉","苹果","草莓", "苹果","草莓"};BSTree<string, int> countTree;for (const auto& str : arr){auto ret = countTree.Find(str);if (ret == nullptr){countTree.Insert(str, 1);}else{ret->_value++;}}countTree.InOrder();}
}

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

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

对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二 叉搜索树的深度的函数，即结点越深，则比较次数越多。

但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：

最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其平均比较次数为：$log_2 N$

最差情况下，二叉搜索树退化为单支树(或者类似单支)，其平均比较次数为：$\frac{N}{2}$