一、理解二叉搜索树

1.1 二叉搜索树的概念

• 若它的左子树不为空，则左子树上所有结点的值都小于等于根结点的值；
• 若它的右子树不为空，则右子树上所有结点的值都大于等于根结点的值；
• 它的左右子树也分别为二叉搜索树；
• 二叉搜索树中可以支持插入相等的值，也可以不支持插入相等的值，具体看使用场景定义

如下图所示就是两个搜索二叉树

1.2 核心特性

1.2.1 多元化的结构： 灵活的数据结构

BST支持动态数据集合的高效操作，适合频繁插入、删除和查找的场景

1.2.2 天然的搜索优势：擅长搜索的数据结构

利用二叉树的分支特性，BST在平均情况下能实现O(logn)的搜索效率

---

二、二叉搜索树性能分析

2.1 时间复杂度分析

• 最优情况下，二叉搜索树为完全二叉树（或者接近完全二叉树），其高度为：logN；
• 最差情况下，二叉搜索树退化为单支树（或者类似单支），其高度为：N；

注意：时间复杂度指的是最差情况下，所以时间复杂度为O(N)

最差情况如图：

那么这样的效率显然是无法满足我们需求的，因此后面博主会介绍二叉搜索树的变形——平衡二叉搜索树AVL树和红黑树，才能适用于我们在内存中存储和搜索数据

2.2 二分查找的局限性

另外需要说明的是，二分查找也可以实现O(logN)级别的查找效率，但是二分查找有两大缺陷

1. 需要存储在支持下标随机访问的结构中，并且有序
2. 插入和删除数据效率很低，因为存储在下标随机访问的结构中，插入和删除数据一般需要挪动数据

如右图所示：数据越有序，插入结果越坏——高度高、递归深、效率低 如左图所示：插入越无序的数据，左右会平衡一点，结果反而越好

三、实现二叉搜索树的定义

3.1 命名规范

二叉搜索树常简写为BST，提高代码可读性（SBT不好听），二叉搜索树也叫搜索二叉树

3.2 定义节点

代码语言：javascript

AI代码解释

template<class K>
struct BSTreeNode
{
	BSTreeNode<K>* _left;
	BSTreeNode<K>* _right;
	K _key;

	BSTreeNode(const K& key)
		:_left(nullptr)
		, _right(nullptr)
		, _key(key)
	{
	}
};

3.3 实践：完整的类定义

提供插入、查找、删除等基本操作的接口设计如下：

---

四、二叉树搜索的插入操作详解

4.1 插入算法流程

从根节点开始，根据键值大小选择左子树或右子树，直到找到空位置插入新节点。

插入分成以下三种情况：

1. 树为空，则直接新增结点，赋值给root指针
2. 树不空，按二叉搜索树性质，插入值比当前结点大就往右走，插入值比当前结点小就往左走，找到空位置，插入新结点
3. 如果支持插入相等的值，插入值跟当前结点相等的值可以往右走，也可以往左走，找到空位置，插入新结点（要注意保持逻辑一致性，插入相等的值不要一会往右走，一会又往左走）

提示：我们就以下面这张图为搜素二叉树来进行实践

4.2 代码实践

4.2.1 代码演示

我们定义这样一个数组

代码语言：javascript

AI代码解释

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

代码如下（不允许相等的值输入）：

代码语言：javascript

AI代码解释

//不允许相等的值插入
template<class K>
class BSTree
{
	typedef BSTreeNode<K> Node;
public:
	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;
	}
}

4.2.2 测试用例设计

我们在Test.cpp文件里面包一下头文件，给一个数组，再定义出一棵树，因为数组也是支持范围for的，这里我们用范围for把数据插入进去

4.2.3 C++递归的麻烦之处

C++递归很麻烦，这里要传根，但是根是私有的

调的是不需要传根的，再去调用这个子函数，把根传过去，这样外面就不需要传了，也不需要提供get root，不过get root调用的时候也方便

4.3 InOrder：中序遍历验证

利用BST的中序遍历必然有序的特性验证插入正确性。

要写成这样套一层的结构，原因上面已经提到了，这里不再赘述

思考：这里为什么要使用中序遍历验证呢？

中序遍历的好处：

1. 中序遍历：最简单的递归
2. 中序遍历有序，并且数据都在，并且能够很好地验证功能
3. 验证搜索二叉树只需判断中序遍历是否为递增即可

4.4 运行演示

成功插入进去了，并且因为是中序遍历，结果是有序的

---

五、查找操作实现

5.1 查找算法

利用BST的排序特性，通过比较键值快速定位目标节点

• 从根开始比较，查找x，x比根的值大则往右边走查找，x比根值小则往左边走查找
• 最多查找高度次，走到到空，还没找到，这个值不存在
• 如果不支持插入相等的值，找到x即可返回
• 如果支持插入相等的值，意味着有多个x存在，一般要求查找中序的第一个x。如下图，查找3，要找到1的右孩子的那个3返回

5.2 代码实践

查找的代码也可以递归写，也可以不用

5.3 测试用例设计

我们就查找一下1这个数据

5.4 运行

---

六、删除操作深度解析

6.1 删除前的定位：要先查找一下

首先需要找到待删除节点及其父节点

6.1.1 查找元素存在分四种情况

首先查找元素是否在二又搜索树中，如果不存在，则返回false。

如果查找元素存在则分以下四种情况需要分别处理一下（假设要删除的结点为N）

1. 要删除结点N左右孩子均为空
2. 要删除的结点N左孩子位空，右孩子结点不为空
3. 要删除的结点N右孩子位空，左孩子结点不为空
4. 要删除的结点N左右孩子结点均不为空

6.1.2 对应以上四种情况的解决方案

1. 把N结点的父亲对应孩子指针指向空，直接删除N结点（情况1可以当成2或者3进行处理，效果是一样的）
2. 把N结点的父亲对应孩子指针指向N的右孩子，直接删除N结点
3. 把N结点的父亲对应孩子指针指向N的左孩子，直接删除N结点
4. 无法直接删除N结点，因为N的两个孩子无处安放，只能用替换法删除。找N左子树的值最大结点R（最右结点）或者N右子树的值最小结点R（最左结点）替代N，因为这两个结点中任意一个，放到N的位置，都满足二叉搜索树的规则。替代N的意思就是N和R的两个结点的值交换，转而变成删除R结点，R结点符合情况2或情况3，可以直接删除