二叉搜索树讲解

1. 二叉搜索树的概念

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

1. 若它的左子树不为空，则左子树上的所有结点的值都小于等于根节点的值。

2. 若它的右子树不为空，则右子树上的所有结点的值都大于等于根节点的值。

3. 它的左右子树也分别为二叉搜索树。

4. 二叉搜索树中可以支持插入相等的值，也可以不支持插入相等的值，具体看使用场景定义。

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

最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其高度为：log2 N。

最差情况下，二叉搜索树退化为单支树(或者类似单支)，其高度为：N。

所以综合而言二叉搜索树增删查改时间复杂度为O(N)。

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

1. 需要存储在支持下标随机访问的结构中，并且有序。

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

这里也就体现出了平衡二叉搜索树的价值。

3. 二叉搜索树的插入

插入的具体过程如下：

1. 树为空，则直接新增结点，赋值给root指针。

2. 树不空，按二叉搜索树的性质，插入值比当前结点大往右走，插入值比当前结点小往左走，找到空位置，插入新结点。

3. 如果支持插入相等的值，插入值跟当前结点相等的值可以往右走也可以往左走，找到空位置，插入新结点。（要注意的是要保持逻辑一致性，插入相等的值不要一会往右走，一会往左走）。

我给出的示例代码是不支持插入相等的值的。

bool Insert(const T& key)
{
	if (_root == nullptr)
	{
		_root = new Node(key);
		return true;
	}

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

	while (cur)
	{
		if (key > cur->_key)
		{
			parent = cur;
			cur = cur->_right;
		}
		else if (key < cur->_key)
		{
			parent = cur;
			cur = cur->_left;
		}
		else
		{
			return false;
		}
	}

	cur = new Node(key);
	if (key > parent->_key)
	{
		parent->_right = cur;
	}
	else
	{
		parent->_left = cur;
	}

	return true;
}

4. 二叉搜索树的查找

1. 从根开始比较，查找x，x比根的值大则往右边走查找，比根的值小则往左边走查找。

2. 最多查找高度次，走到空，还没找到，那么就说明这个值不存在。

3. 如果不支持插入相等的值，找到x即可返回。

4. 如果支持插入相等的值，意味着有多个x存在，一般是要求查找中序的第一个x。如下图，查找3，要找到1的右孩子的那个3返回。

bool Find(const T& x)
{
	Node* cur = _root;
	while (cur)
	{
		if (x > cur->_key)
		{
			cur = cur->_right;
		}
		else if (x < cur->_key)
		{
			cur = cur->_left;
		}
		else
		{
			return true;
		}
	}
	return false;
}

5. 二叉搜索树的删除

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

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

1. N的左右孩子均为空。

2. N左孩子为空，右孩子不为空。

3. N右孩子为空，左孩子不为空。

4. N的左右孩子均不为空

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

1. 把N结点的父亲对应孩子指针指向空，直接删除N结点。（情况1可以当成情况2或者情况3处理，效果是一样的）

2. 把N结点的父亲对应孩子指针指向右孩子，直接删除N结点。

3. 把N结点的父亲对应孩子指针指向左孩子，直接删除N结点。

4. 无法直接删除N结点，因为N的两个孩子无处安放，只能用替换法删除。找N左子树的值最大结点R(最右结点)或者N右子树的值最小结点R(最左结点)替代N，因为这两个结点中任意一个，放到N的位置，都满足二叉搜索树的规则。替代N的意思就是N和R的两个结点的值交换，转而变成删除R结点，R结点符合情况2和情况3，可以直接删除。

bool Erase(const T& key)
{
	Node* cur = _root;
	Node* parent = nullptr;
	
	while (cur)
	{
		if (key > cur->_key)
		{
			parent = cur;
			cur = cur->_right;
		}
		else if (key < cur->_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* replace_parent = cur;
				Node* replace = cur->_right;
				while (replace->_left)
				{
					replace_parent = replace;
					replace = replace->_left;
				}
				swap(cur->_key, replace->_key);
				if (replace == replace_parent->_left)
				{
					replace_parent->_left = replace->_right;
				}
				else
				{
					replace_parent->_right = replace->_right;
				}
				delete replace;
			}
			return true;
		}
	}
	return false;
}

6. 完整的实现代码

#include<iostream>

using namespace std;

template<class T>
struct BinarySearchTreeNode
{
	T _key;
	BinarySearchTreeNode<T>* _left;
	BinarySearchTreeNode<T>* _right;

	BinarySearchTreeNode(const T& key)
		:_key(key)
		,_left(nullptr)
		,_right(nullptr)
	{ }
};

template<class T>
class BSTree
{
	typedef BinarySearchTreeNode<T> Node;
public:
	bool Insert(const T& key)
	{
		if (_root == nullptr)
		{
			_root = new Node(key);
			return true;
		}

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

		while (cur)
		{
			if (key > cur->_key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (key < cur->_key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}

		cur = new Node(key);
		if (key > parent->_key)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}

		return true;
	}

	bool Find(const T& x)
	{
		Node* cur = _root;
		while (cur)
		{
			if (x > cur->_key)
			{
				cur = cur->_right;
			}
			else if (x < cur->_key)
			{
				cur = cur->_left;
			}
			else
			{
				return true;
			}
		}
		return false;
	}

	bool Erase(const T& key)
	{
		Node* cur = _root;
		Node* parent = nullptr;
		
		while (cur)
		{
			if (key > cur->_key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (key < cur->_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* replace_parent = cur;
					Node* replace = cur->_right;
					while (replace->_left)
					{
						replace_parent = replace;
						replace = replace->_left;
					}
					swap(cur->_key, replace->_key);
					if (replace == replace_parent->_left)
					{
						replace_parent->_left = replace->_right;
					}
					else
					{
						replace_parent->_right = replace->_right;
					}
					delete replace;
				}
				return true;
			}
		}
		return false;
	}

	void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		_InOrder(root->_left);
		cout << root->_key << ' ';
		_InOrder(root->_right);
	}

	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}

private:
	Node* _root = nullptr; 
};

int main()
{
	BSTree<int> tree;
	int arr[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
	for (auto& e : arr)
	{
		tree.Insert(e);
	}
	tree.InOrder();

	cout << tree.Find(10) << endl;
	cout << tree.Find(100) << endl;

	tree.Erase(10);
	tree.Erase(6);
	tree.InOrder();

	return 0;
}