二叉搜索树（图解）

文章目录

二叉搜索树的概念
插入
查找
二叉搜索树的删除操作
- 删除单孩子和叶子节点。
- `del`节点有两个孩子
- - 用左子树的最大节点替代
  - 用右子树的最小节点替代
弊端

二叉搜索树的概念

对于每颗子树，左子树 < 根，右子树 > 根。

二叉搜索树有以下操作：

插入
删除
查找

插入

插入很好理解，每次都要判断与当前位置的大小。

如果小于当前位置就往当前节点的左边插入
如果大于当前位置就往当前节点的右边插入。

等于的时候返回false，来表示插入失败。-> set的底层实现。这个其实就是set的插入原理，所以我们的set才有去重的功能。

在这里插入图片描述

如上图，如果我们对现在的二叉搜索树进行中序遍历会得到什么呢？

中序遍历结果： [2,3,6,8,9,10,11]

我们发现二叉搜索树的中序遍历就是一个有序序列。

代码实现：

bool insert(const K& key){if (_root == nullptr){_root = new Node(key);return true;}Node* cur = _root;Node* parent = nullptr;while (cur){if (key < cur->_data){parent = cur;cur = cur->_left;}else if (key > cur->_data){parent = cur;cur = cur->_right;}else //如果遇到重复的返回false。return false;}cur = new Node(key);//判断新增节点连接在此时的哪边if (key < parent->_data)parent->_left = cur;elseparent->_right = cur;return true;}///测试
void Test_BSTRee()
{bit::BSTree<int> Myset;//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };for (auto e : a){Myset.insert(e);}Myset.inorder();
}int main()
{Test_BSTRee();return 0;
}

在这里插入图片描述

查找

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

二叉搜索树的删除操作

删除主要分一下两种情况：

单孩子和没有孩子节点。
del节点有两个孩子

删除单孩子和叶子节点。

在这里插入图片描述

我们可以发现，这两种情况可以合并为一种情况，我们以 del 表示要删除节点。

首先判断我们的 del 是 parent 的哪个孩子节点。
只要 del 的左孩子为空，那么 parent 连接 del的右孩子指针。
只要 del 的右孩子为空，那么 parent 连接 del的左孩子指针。

这里需要特殊处理我们删除根节点的情况 ，

在这里插入图片描述

如果此时我们删除的节点是根节点，那么直接让根节点移动即可。

代码实现：

					//如果cur的左孩子为空   - 连接cur的右孩子if (cur->_left == nullptr){//特殊处理删除根节点的情况if (parent == nullptr){_root = _root->_right;}//判断cur为父节点的那个孩子else {if (parent->_left == cur)parent->_left = cur->_right;elseparent->_right = cur->_right;}delete cur;return true;}else if (cur->_right == nullptr)//如果cur的右孩子为空  - 连接cur的左孩子{//特殊处理删除根节点的情况if (parent == nullptr){_root = _root->_left;}else{//判断cur为父节点的哪个孩子if (parent->_left == cur)parent->_left = cur->_left;elseparent->_right = cur->_left;}delete cur;return true;}

`del`节点有两个孩子

当我们想要删除的节点左右孩子都有的时候，本质上是需要找到一个替代节点。这个节点要求：

大于del左子树的所有节点或者小于del右子树的节点

符合要求的节点有两个： 1. 左子树的最大节点 2. 右子树的最小节点

用左子树的最大节点替代

左子树最大节点存在情况：

在这里插入图片描述

左子树最大节点不存在情况（右子树为空）：

在这里插入图片描述

代码实现：

			//以左孩子的最大节点作为替换节点Node* LeftMaxP = cur;Node* LeftMax = cur->_left;//找到最大节点while (LeftMax && LeftMax->_right){LeftMaxP = LeftMax;LeftMax = LeftMax->_right;}//把替换节点的值拷贝给del（删除）节点.cur->_data = LeftMax->_data;//删除此时的替换节点。//无论LeftMax是LeftMaxP的哪个孩子，都是连接LeftMax的左子树if (LeftMaxP->_right == LeftMax) {LeftMaxP->_right = LeftMax->_left;}else                            {LeftMaxP->_left = LeftMax->_left;}delete LeftMax;return true;

用右子树的最小节点替代

这里也分为两种情况：

右子树最小节点存在

在这里插入图片描述

右子树最小节点不存在

代码实现：

						//以右孩子的最小节点作为替换节点Node* RightMinP = cur;Node* RightMin = cur->_right;//找到右子树的最小节点while (RightMin && RightMin->_left){RightMinP = RightMin;RightMin = RightMin->_left;}//把替换节点的值拷贝给del（删除）节点.cur->_data = RightMin->_data;//删除此时的替换节点。if (RightMinP->_right == RightMin){RightMinP->_right = RightMin->_right;}else                            {RightMinP->_left = RightMin->_right;}delete RightMin;return true;