微信公众号怎么做文章编辑_网站运营维护措施有哪些_网页设计学生作业模板_怎么在百度上推广

个人主页 ： zxctscl
如有转载请先通知

文章目录

1. 前言
2. 二叉搜索树概念
3. 二叉搜索树操作
4. 二叉搜索树的实现
- 4.1 插入
- 4.2 查找
- 4.3 ==删除==
- 4.4 实现代码
5. 二叉搜索树的应用
6. 二叉搜索树的性能分析

1. 前言

二叉树在前面C数据结构阶段已经讲过，了解二叉树进阶是因为：

map和set特性需要先铺垫二叉搜索树，而二叉搜索树也是一种树形结构
二叉搜索树的特性了解，有助于更好的理解map和set的特性
二叉树中部分面试题稍微有点难度，在前面讲解大家不容易接受，且时间长容易忘
有些OJ题使用C语言方式实现比较麻烦，比如有些地方要返回动态开辟的二维数组，非常麻烦。

2. 二叉搜索树概念

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

若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
它的左右子树也分别为二叉搜索树

3. 二叉搜索树操作

在这里插入图片描述

int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};

二叉搜索树的查找
a、从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。
b、最多查找高度次，走到到空，还没找到，这个值不存在。
二叉搜索树的插入
插入的具体过程如下：
a. 树为空，则直接新增节点，赋值给root指针
b. 树不空，按二叉搜索树性质查找插入位置，插入新节点
二叉搜索树的删除
首先查找元素是否在二叉搜索树中，如果不存在，则返回, 否则要删除的结点可能分下面四种情况：
a. 要删除的结点无孩子结点
b. 要删除的结点只有左孩子结点
c. 要删除的结点只有右孩子结点
d. 要删除的结点有左、右孩子结点

看起来有待删除节点有4中情况，实际情况a可以与情况b或者c合并起来，因此真正的删除过程如下：
情况b：删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点–直接删除
情况c：删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点–直接删除
情况d：在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被删除节点中，再来处理该结点的删除问题–替换法删除

在这里插入图片描述

4. 二叉搜索树的实现

4.1 插入

在这里插入图片描述

假设要插入的是5，那么就从根节点开始比较：5比8小，5比3大，5比6小，5比4大，就找到了插入的位置。

如果插入的值比cur小，就往左走；如果比cur的值大，就往右走；如果插入值和cur相同，但是默认定义，搜索树不允许冗余，这个值有了，再插入就没有意义了，有些地方是可以冗余的。在这里如果这个值已经有了，就直接返回false。

找到空位置之后，不能直接申请一个节点直接插入，局部变量出了作用域就销毁了。所以还得找到插入节点的父节点。为了方便找到parent，可以在cur往下走之前，先把它给parent。最后再形成链接。如果比父节点大就链接在父节点的右边，比父节点小就链接在左边。

如果给的节点为空，就会出现空指针的情况，先判断一下根节点是不是空。

	bool Insert(const k& key){if (_root == nullptr){_root = new Node(key);return true;}Node* cur = _root;Node* parent = nullptr;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;}

4.2 查找

值比cur小，就往左走；如果比cur的值大，就往右走；如果值和cur相同，就返回true。节点为空，就返回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 true;}}return false;}

4.3 删除

在这里插入图片描述
当删除的没有子节点，就直接删除就行。

在这里插入图片描述

在这里插入图片描述
当删除的节点有一个子节点时候，把它的子节点与它的父节点链接。

当删除的节点左为空时，分两种情况，如果像3这种，那么就让父节点的left指向cur的right；如果是像10这种情况，那么就让父节点8指向cur的右节点14。

代码这样写：

              if (cur->_left == nullptr)//左为空，父亲指向我的右{if (cur == parent->_left){parent->_left = cur->_right;}else{parent->_right = cur->_right;}delete cur;}

在这里插入图片描述
当删除的节点右为空时，分两种情况，如果像3这种，那么就让父节点的left指向cur的left；如果是像10这种情况，那么就让父节点8指向cur的左节点13。
代码如下：

               else if (cur->_right==nullptr)//右为空，父亲指向我的左{if (cur == parent->_left){parent->_left = cur->_left;}else{parent->_right = cur->_left;}delete cur;}

在这里插入图片描述

如果删除的节点有两个子节点，怎么办呢？
此时就不好直接与父节点链接，就采用替换法：找一个节点来替换删除的节点。而这个节点必须是这个节点左子树的最大节点或者是右子树的最小节点。

在这里插入图片描述
假设选择4去覆盖3，转化成删除4,4是右子树的最小节点。把3和4交换后，再删除3。但是要删除交换后的3，就得先记录交换3之后，3的父节点。

就得把交换后3的父节点rightMinParent的left指向rightMin的right。
代码如下：

                else//左右都不为空，替换删除法{Node* rightMin = cur->_right;Node* rightMinParent = nullptr;while (rightMin->_left)//右子树的最小节点替换删除的节点{rightMinParent = rightMin;rightMin = rightMin->_left;}swap(cur->_key, rightMin->_key);rightMinParent->_left = rightMin->_right;delete rightMin;}

在这里插入图片描述
但是如果删除的节点是根节点，那么按照上面的方法，找到右子树最小节点就是13,13比10大，那么显然这个树就不是搜索二叉树了。为了避免这样，就先记录下根节点作为rightMinParent，再进行后面的判断。如果rightMinParent的left是rightMin，那么就让rightMinParent的left指向rightMin的right。
最终的代码就是：

				else//左右都不为空，替换删除法{Node* rightMin = cur->_right;Node* rightMinParent = cur;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;}

在这里插入图片描述

删除的总代码：

bool Erase(const k& key){Node* cur = _root;Node* parent = nullptr;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 (cur == parent->_left){parent->_left = cur->_right;}else{parent->_right = cur->_right;}}delete cur;}else if (cur->_right==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* rightMin = cur->_right;Node* rightMinParent = cur;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;}

4.4 实现代码

template<class k>
//struct BinarySearchTreeNode 
struct BSTreeNode
{BSTreeNode<k>* _left;BSTreeNode<k>* _right;k _key;BSTreeNode(const k& key):_left(nullptr), _right(nullptr), _key(key){}
};template<class k>
//class BinarySearchTree
class BSTree
{typedef BSTreeNode<k> Node;
public:bool Insert(const k& key){if (_root == nullptr){_root = new Node(key);return true;}Node* cur = _root;Node* parent = nullptr;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* cur = _root;Node* parent = nullptr;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 (cur == parent->_left){parent->_left = cur->_right;}else{parent->_right = cur->_right;}}delete cur;}else if (cur->_right==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* rightMin = cur->_right;Node* rightMinParent = cur;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;}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;
};

5. 二叉搜索树的应用

K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。
比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：
（1）以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树
（2）在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。
KV模型：每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。该种方式在现实生活中非常常见：
（1）比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文<word, chinese>就构成一种键值对；
（2）再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是<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();
}

6. 二叉搜索树的性能分析

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

在这里插入图片描述

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

问题：如果退化成单支树，二叉搜索树的性能就失去了。那能否进行改进，不论按照什么次序插入关键码，二叉搜索树的性能都能达到最优？那么我们后续的AVL树和红黑树就可以上场了。