---

前言

这是全新的一个篇章呢，二叉搜索树是我们接下来学习set、map的前提
迈过它吧，关关难过关关过！

正文开始！

---

一、二叉搜索树的概念

定义

  二叉搜索树（Binary search tree）是基于二叉树的一种改进版本。因为 普通二叉树没有实际价值，无法进行插入、删除等操作（无意义），但二叉搜索树就不一样了，二叉搜索树对于数据的存储有严格要求：左节点比根小，右节点比根大

因此 二叉搜索树 的查找效率极高，具有一定的实际价值

  所以将数据存入 二叉搜索树 中进行查找时，理想情况下只需要花费 logN 的时间（二分思想）

  这就是 二叉搜索树 名字的由来，搜索（查找）速度很快

特点

  二叉树的基本特点：左比根小，右比根大

1. 若某个节点的 左 节点不为空，则 左 节点的值一定比当前节点的值 小，且其 左 子树的所有节点都比它 小
2. 若某个节点的 右 节点不为空，则 右 节点的值一定比当前节点的值 大，且其 右 子树的所有节点都比它 大
3. 二叉搜索树的每一个节点的 根、左 、右 都满足基本特点

另外，中序遍历的结果为升序

二、二叉树的实现

二叉搜索树的源代码

基本框架

  跟普通的二叉树一样，二叉搜索树也需要节点类，同时将节点指针作为二叉搜索树的成员变量

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

	BSTNode(const K& key = K())
		:_key(key)
		,_left(nullptr)
		,_right(nullptr)
	{}

};

template <class K>
class BSTree
{
	typedef BSTNode<K> Node;
public:
	BSTree()
		:_root(nullptr)
	{}
	
private:
	Node* _root;
};

查找

  得益于二叉搜索树的特性，我们可以比较插入数字和当前节点的值，当比当前节点大的时候的时候往右走，反之则往左，若 cur 为空，那么返回 false ，若找到，则返回 true

bool Find(const K& key)
{
	Node* cur = _root;

	while (cur) {
		if (key > cur->_key) 
			cur = cur->_right;

		else if (key < cur->_key) 
			cur = cur->_left;

		else return true;
	}

	return false;
}

插入

  插入其实过程和查找差不多，只不过如果中途找到了就返回 false 表示二叉搜索树中已经有该数字，如果成功走到空了就开始插入

  只不过我们需要注意，当搜索树为空树的时候，我们必须新建立一个节点，将指针赋给这个根节点，另外，我们需要申请一个指针变量 parent 来记录父节点，方便后续链接

bool Insert(const K& key)
{
	// 如果为空树，则直接建立一个节点
	// 将其地址存放在_root上
	if (_root == nullptr)
	{
		_root = new Node(key);
		return true;
	}

	Node* parent = nullptr;
	Node* cur = _root;

	// 一直循环到cur为空
	while (cur) {
		if (key > cur->_key) {
			parent = cur;
			cur = cur->_right;
		}
		else if (key < cur->_key) {
			parent = cur;
			cur = cur->_left;
		}
		else {
			// 如果中途发现BS树已有key，则插入失败
			// BS树中没有重复元素，依据定义
			return false;
		}
	}

	// 此时建立一个节点，将其地址赋值给cur
	cur = new Node(key);

	// 此时需要根据值的大小来判断parent左链还是右链
	if (key > parent->_key)
		parent->_right = cur;
	else parent->_left = cur;

	return true;
}

删除

  删除可就复杂了，要考虑很多情况！

  我们发现如果我们要删除一个节点，并且在二叉搜索树中已经确定找到了该节点，可能有三种情况：

1. 该节点没有孩子，即要删除的是叶子节点
2. 该节点只有一个孩子，可能是左孩子为空，也有可能是有孩子为空
3. 该节点有两个孩子，这种情况比较复杂，要考虑比较复杂的情况

当只有0 ~ 1个孩子的时候

  我们先来看第二种情况，当找到要删除的节点且该节点只有一个孩子后，此时显然父节点链上当前节点的子节点就可以了，这样不会破坏二叉搜索树的结构

二叉搜索树的右子树的值一定大于该节点的值，同样的，左子树的值一定小于该节点的值

  于是，我们就想着再销毁当前节点之前，先判断是父节点的左边链接还是右边链接，这很简单，我们检查一下 parent 左右指针哪个指向 cur 就行，同时，我们也要思考一下子节点与 cur 的链接关系，很简单，这也是直接判断一下就可以

其实，这种方法囊括了第一第二种情况，你可以思考一下为什么

// 如果左孩子为空
// 这时候就要parent就要链到cur的右边去
if (cur->_left == nullptr) {
	if (parent->_left == cur)
		parent->_left = cur->_right;
	else parent->_right = cur->_right;

	// 删除
	delete cur;
	cur = nullptr;

	return true;
}

// 如果右孩子为空
// 这时候就要parent就要链到cur的左边去
else if (cur->_right == nullptr) {
	if (parent->_left == cur)
		parent->_left = cur->_left;
	else parent->_right = cur->_left;

	// 删除
	delete cur;
	cur = nullptr;

	return true;
}

右子树为空

左子树为空

当有2个孩子的时候

  当左右孩子节点都不为空的时候，我们也要想想，万一把 cur 给删掉了，要换那一个替上来？

  关于这个问题，我们还是要把握二叉搜索树的一个核心特性，就是左子树所有节点的值一定比根节点小，右子树所有节点的值一定比根节点大

  那么只要将左子树最大的值和右子树最小的值找到，此时我们又要想，将两个其中之一的值替代父节点的值即可，然后再销毁节点，那么这样会不会破坏二叉树的结构呢？

  显然不会，只要能正确销毁并正确链接，那么就没关系，在这里我们选择找到右子树的最小值，这很简单，因为一个二叉搜索树的最小值就是最左边那个，那么我们同样用 rightMin 标记右子树的最小节点 ，用 rightMinP 标记其父节点，又为了防止 rightMinP 进不去循环，我们给 rightMinP 赋值 cur

Node* rightMinP = cur;
Node* rightMin = cur->_right;

// 找到右子树的最小节点
while (rightMin->_left) {
	rightMinP = rightMin;
	rightMin = rightMin->_left;
}

// 替代，这时候转换成就要删除rightMin这个节点了
// 这个时候就需要有它的父亲
cur->_key = rightMin->_key;

// 因为rightMin必然是最左节点
// 所以rightMinP必然是链接rightMin的右孩子
// 同时rightMinP是左链还是右链这不确定，需要判断一下
if (rightMinP->_left == rightMin)
	rightMinP->_left = rightMin->_right;
else rightMinP->_right = rightMin->_right;

delete rightMin;
rightMin = nullptr;

return true;

  但是但是！！我们发现写到这里后，当删到最后只剩几个节点之后，报错了！

  我们再回看代码，发现我们的逻辑是先找到删除节点，再用父亲节点去链接当前节点的子节点，关键是，有没有可能一开始我们就找到了要删除的节点，父亲节点没进循环，也就是说，没有父亲节点，这很不好，针对这种情况，我们就要移动根节点

if (parent == nullptr) {
	_root = _root->_right;

	delete cur;
	cur = nullptr;
	return true;
}

三、二叉树的应用

K模型

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

我们上述代码实现的也就是这种

  举个例子，给一个单词word，判断该单词是否拼写正确，具体方式如下：

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

KV模型

  每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对

  比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文<word, chinese>就构成一种键值对

  再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是<word, count>就构成一种键值对

KV模型也就是在K模型的基础上加上value的值，请试试吧！

四、二叉树的性能分析

  如果我问你二叉搜索树的查找时间复杂度为多少，你可能会不假思索的回答出是O(logN)，但是，假如我给一个递减数列呢，是不是就退化成单支树了？

  所以理想状态下是O(logN)，最坏情况下是O(N)

---

总结

  看了性能分析，你可能会想怎么让二叉树的性能达到最优？不急，AVL树和红黑树已经在路上了！~