【C++进阶】详解二叉搜索树

从这里开始我们进入C++中难度比较大的部分了，希望我们都能认真的学习这部分的内容。掌握了后面难度比较大的内容后，我们对C++的认识就会更上一层楼。废话不多说我们直接开始。我们先来二叉搜索树，为后面的map和set打好基础。

一，二叉搜索树的概念

在前面数据结构我们学习了二叉树，那么二叉搜索树又是什么呢？
二叉搜索树（BST–Binary Search Tree）又叫二叉排序树或者二叉查找树。他要满足下面的特性：

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

空树也可以是二叉搜索树。

二，二叉搜索树的操作

二叉搜索树这种结构，当中序遍历时，是升序。比如下面这棵树：

中序遍历后，这棵树的顺序是

1 3 4 6 7 8 10 13 14

二叉搜索树只支持插入删除，不支持修改，因为如果可以修改的话，这个结构就不能满足二叉搜索树的要求！！

二叉搜索树的查找：

1. 从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。
2. 最多查找高度次，走到到空，还没找到，这个值不存在

插入
二叉搜索树中也不能有相同的节点，所以不能插入值相同的节点

一般插入的过程是：

1. 树为空，则直接新增节点，赋值给root指针
2. 树不空，按二叉搜索树性质查找插入位置，插入新节点

删除

二叉搜索树的删除比较复杂，因为删除节点后要保证二叉搜索树的完整性

删除分两种情况：

1. 要删除的节点没有孩子
2. 要删除的节点有一个孩子（左孩子或者右孩子）
3. 要删除的节点有左右孩子

这里实际上可以将第一种和第二种归为一种情况，因为删除时当删除节点有左孩子/右孩子或者无孩子时，直接将删除节点的左孩子/右孩子链接到删除结点的双亲结点的原来位置，再将删除节点删除即可。

而当删除节点有左右孩子时，则要用到替换删除法，具体我们在下面模拟实现的时候讲解。

三，二叉搜索树的模拟实现

1. 基本框架及接口

要模拟实现二叉搜索树，首先得有节点，所以我们先来写一个节点的类模板，存放的数据类型由给定的确定

//节点
template<class K>
struct BSTreeNode {
	typedef BSTreeNode<K> Node;

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

	K _key;
	Node* _left;
	Node* _right;
};

然后我们搭建BST的基本框架

template<class K>
class BSTree {
	typedef BSTreeNode<K> Node;

public:
	BSTree() = default;//强制生成默认构造函数
	
	//....
private:
	Node* _root = nullptr;

};

注：这里的构造函数加上default可以强制生成默认构造

其次我们可以实现中序遍历，打印出我们的升序
这里我们进行了一层封装，因为外部调用时不能直接访问二叉搜索树的根节点，但内部实现时要传入根节点

void InOrder() {//中序遍历打印
	_InOrder(_root);//这样封装可以不用访问私有成员_root
	cout << endl;
}

void _InOrder(Node* root) {//中序遍历打印
	if (root == nullptr) {
		return;
	}
	_InOrder(root->_left);
	cout << root->_key << " ";
	_InOrder(root->_right);	
}

拷贝构造和析构和中序遍历一样，进行一层封装

BSTree(const BSTree<K>& b) {
	_root = _Copy(b._root);//这里内部封装了私有函数，因为外部不能调用私有成员变量_root
}

~BSTree() {
	_Destory(_root);
}

Node* _Copy(Node* root) {//拷贝构造
	if (root == nullptr) {
		return nullptr;
	}
	Node* newroot = new Node(root->_key);
	newroot->_left = _Copy(root->_left);
	newroot->_right = _Copy(root->_right);
	return newroot;
}

void _Destory(Node* root) {//析构
	if (root == nullptr)
	{
		return ;
	}
	_Destory(root->_left);
	_Destory(root->_right);
	delete root;
}

其余的插入删除查找我们可以实现递归和非递归版本，在下面进行讲解：

2. 插入删除非递归版

我们先来实现非递归查找

实现起来比较容易，如果cur没有走到空，则将cur给到下一层继续找，找到则返回，找不到则返回false

bool Find(const K& key) {//非递归查找

	Node* cur = _root;
	while (cur) {
		if (cur->_key > key) {
			cur = cur->_left;
		}
		else if (cur->_key < key) {
			cur = cur->_right;
		}
		else {
			return true;
		}
		return false;
	}
}

插入

插入也比较简单，增加一个parent变量来记录要插入位置的双亲位置，查找要插入的位置，找到后，parent可以用来找到插入在上一级节点的左孩子还是右孩子

bool Insert(const K& key) {//非递归插入
	if (_root == nullptr) {//当根为空时
		_root = new Node(key);
		return true;
	}

	Node* parent = nullptr;
	Node* cur = _root;
	while (cur) {
		if (key > cur->_key) {
			parent = cur;//parent跟随cur找到要插入的位置
			cur = cur->_right;
		}
		else if (key < cur->_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 Erase(const K& key) {//非递归删除
	Node* parent = nullptr;//记录删除指定结点后，该结点的孩子结点要重新链接在原父节点的位置
	Node* cur = _root;
	while (cur) {
		if (cur->_key > key) {
			parent = cur;
			cur = cur->_left;
		}
		else if (cur->_key < key) {
			parent = cur;
			cur = cur->_right;
		}


	//....
	}	

对于这第一种情况，
因为我们将没有孩子节点和只有一个节点归为一个节点，所以当删除节点左孩子为空时也包含删除节点没有孩子这种情况。
当删除节点左孩子为空时，如果要删除的结点是根节点，则直接将右孩子设为根即可，再删除该节点。
右孩子为空时同理

bool Erase(const K& key) {//非递归删除
	Node* parent = nullptr;//记录删除指定结点后，该结点的孩子结点要重新链接在原父节点的位置
	Node* cur = _root;
	while (cur) {
		if (cur->_key > key) {
			parent = cur;
			cur = cur->_left;
		}
		else if (cur->_key < key) {
			parent = cur;
			cur = cur->_right;
		}
		else {//找到要删除的结点,这里要分情况
			//第一种情况
			if (cur->_left == nullptr) {//要删除的结点左孩子为空时
				if (cur == _root) {//要删除的结点为根
					_root = cur->_right;
				}
				else {
					if (cur == parent->_left) {//cur为parent左孩子时
						parent->_left = cur->_right;//直接链接cur的右孩子
					}
					else {
						parent->_right = cur->_right;
					}
						
				}
				delete cur;
				return true;
			}
			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;
				return true;
			}
			//..
}

当有两个孩子时要用到替换删除法

那么什么是替换删除法呢？

替换删除法就是将要删除的节点和左子树最右的节点或者和右子树最左的节点交换，再删除交换后的节点，这样删除后二叉搜索树的结构不会改变。

那么为什么要选择左子树最右的节点或者右子树最左的节点呢？

因为左子树的最右节点的值比删除节点的左子树中节点的值都大，比其右子树中节点的值都小。交换后还是二叉搜索树的结构。

右子树的最左节点同理，下图是删除过程：

完整代码：

bool Erase(const K& key) {//非递归删除
	Node* parent = nullptr;//记录删除指定结点后，该结点的孩子结点要重新链接在原父节点的位置
	Node* cur = _root;
	while (cur) {
		if (cur->_key > key) {
			parent = cur;
			cur = cur->_left;
		}
		else if (cur->_key < key) {
			parent = cur;
			cur = cur->_right;
		}
		else {//找到要删除的结点,这里要分情况
			//第一种情况
			if (cur->_left == nullptr) {//要删除的结点左孩子为空时
				if (cur == _root) {//要删除的结点为根
					_root = cur->_right;
				}
				else {
					if (cur == parent->_left) {//cur为parent左孩子时
						parent->_left = cur->_right;//直接链接cur的右孩子
					}
					else {
						parent->_right = cur->_right;
					}
						
				}
				delete cur;
				return true;
			}
			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;
				return true;
			}
			//第二种情况
			else {
				Node* rightMinparent = cur;//
				Node* rightMin = cur->_right;//这里用右子树最小结点交换

				while (rightMin->_left) {//当左子树为空时，该rightMin为右子树的最小结点
					rightMinparent = rightMin;
					rightMin = rightMin->_left;
				}
				cur->_key = rightMin->_key;
				if (rightMin == rightMinparent->_right) {//这里处理特殊情况,当rightMinparent为根时，rightMin为右子树的最小结点
					rightMinparent->_right = rightMin->_right;
				}
				else {//
					rightMinparent->_left = rightMin->_right;//
				}
				delete rightMin;
				return true;
			}
		}
	}

	//没有找到要删除的结点
	return false;

}

3. 插入删除递归版

递归版本也是进行一层封装，因为外部不能访问根节点

先来看递归查找：比较简单，直接看代码：

bool FindR(const K& key) {
	return _FindR(_root, key);
}

bool _FindR(Node* root, const K& key) {
	if (root == nullptr) {
		return false;
	}
	if (key > root->_key) {
		return _FindR(root->_right, key);
	}
	else if (key < root->_key) {
		return _FindR(root->_left, key);
	}
	else {
		return true;
	}
}

递归插入：

递归插入比较有意思，我们每次在递归时都要传入root指针，如果我们在这个指针前面加上引用，那么递归时传入的root指针就是上一次递归时的位置。那么当要在正确的位置插入时不用再判断插入到该位置的双亲结点的左孩子还是右孩子。

bool InsertR(const K& key) {
	return _InsertR(_root, key);
}

bool _InsertR(Node *& root, const K& key) {//这里在root加上&
	if (root == nullptr) {
		root = new Node(key);//这个root是上一次递归时找到的要插入位置本身
		return true;
	}

	if (key > root->_key) {
		return _InsertR(root->_right, key);
	}
	else if (key < root->_key) {
		return _InsertR(root->_left, key);
	}
	else {
		return false;
	}
}

递归删除

递归删除传入的root指针和插入时一样，加上引用
定义变量del 记录要删除的节点

第一种情况下找到后，将当前的左孩子或者右孩子直接连接到原来的位置就可以
第二种情况下，找到右子树的最左节点后交换删除这个节点和当前root的值，注意：这里交换后要删除右子树最左节点时，可以复用递归删除这个函数。

bool EraseR(const K& key) {
	return _EraseR(_root, key);
}

bool _EraseR(Node *& root, const K& key) {//这里加上引用
	if (root == nullptr) {
		return false;
	}
	if (key > root->_key) {
		return _EraseR(root->_right, key);
	}
	else if (key < root->_key) {
		return _EraseR(root->_left, key);
	}
	else {
		Node* del = root;
		//第一种情况
		if (root->_left == nullptr) {//要删除的结点的左节点为空
			root = root->_right;//直接将目标结点的孩子连接到原位置
		}
		else if(root->_right == nullptr){
			root = root->_left;
		}
		//第二种情况
		else {
			Node* rightMin = root->_right;
			while (rightMin->_left) {
				rightMin = rightMin->_left;
			}
			swap(root->_key, rightMin->_key);//替换删除法
			return _EraseR(root->_right, key);//这里复用，之间删除交换后的结点

		}
		delete del;
		return true;
	}
	
}

四，二叉搜索树的应用

在上面我们模拟实现了二叉搜索树的主要接口，我们主要的是了解其重要的底层。模拟实现也是为了更加深入的了解二叉搜索树

现在我们来看一看二叉搜索树的应用
二叉搜索树其实有两种模型，分别是K模型和KV模型，我们上述实现的是K模型，简单来说就是每个节点只有一个值Key，而KV模型的每个节点有两个值 <Key, Value> 。

对于K模型，我们可以用来检索
比如我们可以给定一个单词，来K模型存放的单词树中进行查找，来判断是否正确

而对于KV模型，每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。该种方式在现实生活中非常常见：我们可以用他来统计个数，或者用来像词典一样进行查找，给定Key来查找Value

KV模型的二叉搜索树其实只需要在K模型的二叉搜索树的基础上稍作修改即可
如果感兴趣的朋友可以查看： KV模型的二叉搜索树
里面也有如何统计个数的示例

五，性能分析

接下来我们来简单分析一下二叉搜索树的性能：

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

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

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

六，总结

当二叉搜索树退化为单支树时，其查找的优势就会失去，那么解决办法就是我们后面会讲的AVL树和红黑树了，所以我们要先掌握二叉搜索树，因为这些都是在此之上的知识。希望大家都能掌握并且可以持续关注，我会带来更多的C++知识。