【进阶数据结构】二叉搜索树&经典习题讲解

一、概念

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

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

二、基本操作

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

2.1 查找

搜索二叉树的特性结构，使得它的查找效率十分快

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

✏️代码实现

//查找
bool Find(const K& key)
{
   
	Node* cur = _root;
	while (cur)
	{
   
		if (cur->_key < key)
		{
   
			cur = cur->_right;
		}
		else if (cur->_key > key)
		{
   
			cur = cur->_left;
		}
		else
			return true;
	}
	return false;
}

2.2 插入

插入的具体过程如下：

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

由于要严格遵循二叉搜索树的结构，所以在每次遍历或最后的插入时都需要比较新增节点与其父节点的值的大小♨️所以我们可以用一个parent指针，随时记录下父节点，便于插入时的大小判断💭

✏️代码实现

//插入
bool Insert(const K& key)
{
   
	if (_root == nullptr)
	{
   
		_root = new Node(key);
		return true;
	}

	//插入,小于就插左，大于就插右
	Node* parent = nullptr;
	Node* cur = _root;
	while (cur)
	{
   
		parent = cur;
		if (key < cur->_key)
			cur = cur->_left;
		else if (key > cur->_key)
			cur = cur->_right;
		else
			return false;
	}
	
	//到合适的空了，开始插入
	//要插在左还是右，还是需要比较
	cur = new Node(key);
	if (key < parent->_key)
		parent->_left = cur;
	if (key > parent->_key)
		parent->_right = cur;
	return true;
}

2.3 删除

二叉搜索树的删除较为复杂

首先查找元素是否在二叉搜索树中，如果不存在，则返回false, 否则要删除的结点可能分下面四种情况：

删除的情况有些许复杂，我们可以将其归成两类

1. 直接删除法
2. 替换法删除

⭕直接删除法

直接删除法适用于以上的情况1、2、3；其具体情况是删除的节点只有一个孩子或没有孩子节点
而当你删除节点后，其被删节点的孩子节点不能就任其飘荡呀，所以我们就需要对其进行“寄养”；而若删除节点没有孩子节点（左右孩子节点都为空）则删除后，被删节点的父节点所对应的孩子节点也需要指向空🔅

综上所述，根据搜索二叉树的结构可得：
在代码实现时，我们可以把情况1和情况2合为一种情况 —— 被删节点的左孩子节点为空 ——> 判断被删节点为其父节点的左or右孩子 ——> 将被删节点的右孩子与父节点链接起来（寄养）✅
情况3 —— 被删节点的右孩子节点为空 ——> 判断被删节点为其父节点的左or右孩子 ——> 将被删节点的左孩子与父节点链接起来（寄养）✅

🚩🚩直接删除法有一个bug需要留意 —— 当被删节点为根节点时，会出现空指针的问题；因此在代码实现时注意判断

⭕替换法删除

✏️代码实现

//删除
bool Erase(const K& key)
{
   
	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//值相等 - 找到了
		{
   
			//1.左为空
			//2.右为空
			//3.左右都不为空 - 替换删除
			if (cur->_left == nullptr)
			{
   
				if (cur == _root) //parent == nullptr
					_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) //parent == nullptr
					_root = cur->_left;
				else
				{
   
					if (cur == parent->_left)
						parent->_left = cur->_left;
					else
						parent->_right = cur->_left;
				}
				delete cur;
			}
			else
			{
   
				//替换删除
				Node* parent = cur;
				Node* minRight = cur->_right;
				while (minRight->_left)
				{
   
					parent = minRight;
					minRight = minRight->_left;
				}
                
				cur->_key = minRight->_key;
                
				if (minRight == parent->_left)
					parent->_left = minRight->_right;
				else
					parent->_right = minRight->_right;
                
				delete minRight;
			}
			return true;
		}
	}
	return false;
}

三、递归实现

3.1 递归查找 - Find

bool _FindR(Node* root, const K& key)
{
   
	if (root == nullptr)
		return false;

	if (key > root->_key)
		root = root->_right;
	else if (key < root->_key)
		root = root->_left;
	else
		return true;
}

3.2 递归插入 - Insert

在实现递归插入的过程中，最后会发现插入时需要调用到父指针，但是一步一步传父指针很麻烦💭于是这里用到了一个很巧妙的方法🚩🚩

✏️代码实现

bool _InsertR(Node*& root, const K& key