目录

一、二叉搜索树的概念

注意点：

二、二叉搜索树的实现

1、二叉搜索树的基础模板

2、插入

   3、查找

4、删除

---

一、二叉搜索树的概念

   

上图就是个二叉搜索树，所谓二叉搜索树必须满足以下条件：

   1、左子树的值在非空的情况下必须比根节点要小，右子树的值在非空的情况下必须比根节点要大。

   2、左右子树也都是二叉搜索树。

   3、二叉搜索树可以用来存储重复的数据，具体的使用要结合实际场景。

注意点：

二叉搜索树在普通场景下的查找效率比较高（logN），但需要注意极端场景：

   上图依旧符合二叉搜索树的定义，但是该极端情况下的查找效率增长为O(N)。

二、二叉搜索树的实现

1、二叉搜索树的基础模板

template<class T>
struct BSTNode
{
	BSTNode(const T& _key)//初始化节点
		:key(_key)
		, right(nullptr)
		, left(nullptr)
	{
	}

	T key;
	BSTNode* right;
	BSTNode* left;

};

  二叉搜索树中的每一个节点都需要包含节点存储的关键性息（key）以及分别指向左右子树的指针（right和left  命名方法不规范，但不想改代码了）

   我们对节点用类来封装，方便后期的调用和维护。在主干类中我们直接使用外部的BSTNode类。

template<class T>
class BST
{
public:
	typedef BSTNode<T> Node;


private: 
 	Node* root = nullptr; 
}；

2、插入

例如我们要在第一张图中插入4，很容易看出应该插在5的左孩子处：

   代码上的逻辑就是将要插入的数据从根节点开始逐步往下比较，如果插入数据比根节点要小则看根节点的左孩子，如果插入数据比根节点要大的话就看根节点的右孩子。如果碰上节点为空的话就插入，否则就一直这么比较下去直到插入。

代码实现：

	bool insert(const T& key)
	{
		if (root == nullptr)
		{
			root = new Node(key);
			return true;
		}
		Node* cur = root;
		Node* curparent = nullptr;
		while (cur)
		{
			if (cur->key > key)
			{
				curparent = cur;
				cur = cur->left;
			}
			else if (cur->key < key)
			{
				curparent = cur;
				cur = cur->right;
			}
			else return false;//遇到相同的值就返回false
		}
		cur = new Node(key);//调用BSTNode的构造
		if (curparent->key < key)
		{
			curparent->right = cur;
		}
		else
		{
			curparent->left = cur;
		}
		return true;
	}

   3、查找

   查找的逻辑跟插入的逻辑大差不差，从根节点开始逐步往下查找。

   代码实现：

	bool find(const T& 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;
	}

4、删除

   要删除二叉搜索树中的特定元素需要先找到该元素的位置，前面的代码可复用fin()的。

   删除操作在实现的过程中需要注意新树仍然符合二叉搜索树的规则。

   

   我们先试试分别删除上图红箭头指向的节点，尝试找找规律和注意事项。

   总结：

1、删除分左右孩子为空，左右孩子有一个为空以及左右孩子都不为空这三种情况。

2、对于被删除的节点如果右孩子为空我们需要用其左子树中的最大值来替换。

3、对于被删除的节点如果左孩子为空我们需要用其右子树中的最小值来替换。

4、左右孩子都不为空时，用其右子树中的最小值来替换。

   在实现删除操作的时候一定要留神小心以上场景，可不敢有所遗漏。

代码实现：

	bool erase(const T& key)
	{
		Node* cur = root;
		Node* curparent = nullptr;  //父亲节点
		while (cur)
		{
            //套用find部分代码查找删除对象的位置
			if (cur->key > key)
			{
				curparent = cur;
				cur = cur->left;
			}
			else if (cur->key < key)
			{
				curparent = cur;
				cur = cur->right;
			}
			else //开始删除
			{
				if (cur->left == nullptr)  //左为空
				{
					if (curparent == nullptr) //左为空情况1
					{
						root = cur->right;
					}
					else  
					{
						if (curparent->left == cur) //左为空情况2
						{
							curparent->left = cur->right;
						}
						else //左为空情况3
						{
							curparent->right = cur->right;
						}
					}
					delete cur;
					return true;
				}

				else if (cur->right == nullptr) //右为空
				{
					if (curparent == nullptr) //1
					{
						root = cur->left;
					}
					else
					{
						if (curparent->left == cur) //2
						{
							curparent->left = cur->left;
						}
						else //3
						{
							curparent->right = cur->left;
						}
					}
					delete cur;
					return true;
				}

				else //左右都不为空，要找到合适的替换节点
				{
					Node* ncur = cur->right;  //找到右子树
					Node* nparent = cur;
					while (ncur->left)
					{
						nparent = ncur;
						ncur = ncur->left;
					}

					cur->key = ncur->key;
					//替换节点，同样需要考虑被替换节点的父亲节点情况
					if (nparent->left == ncur)
						nparent->left = ncur->right;
					else
						nparent->right = ncur->right;

					delete ncur;
					return true;
				}
			}
		}
		return false;
	}

需要注意，容易遗漏的点：

   我们在实现删除操作的时候，先将要删除节点的情况分为孩子存在空节点以及孩子不存在空这两种情况。

   在孩子存在空的情况下又包含父亲节点是否存在？如果存在父亲节点另一个孩子是否为空？如何在不为空和为空这两种情况下寻找合适的替换节点。

   在重新构建二叉搜索树的时候也要注意被改变节点的父亲节点指向孩子的指针的指向更改问题。