C++ - 二叉搜索树讲解

二叉搜索树概念和定义

二叉搜索树是一个二叉树，其中每个节点的值都满足以下条件：

• 节点的左子树只包含小于当前节点值的节点。
• 节点的右子树只包含大于当前节点值的节点。
• 左右子树也必须是二叉搜索树。

二叉树搜索树性质

从上面的二叉搜索树定义中可以了解到, 二叉搜索树是有序的.

通过中序遍历, 会发现这是个有序的序列, 升序或降序 (自己决定)

二叉搜索树只支持增删查, 不支持该.
因为如果随意修改二叉搜索树节点的值, 那么就有可能会导致, 这棵树不再满足二叉搜索树的条件.

二叉搜索树的查找的时间复杂度: 
最好情况: O(log n)
最坏情况: O(N)

当二叉搜索树是以上的情况时, 就变成了链表, 那么时间复杂度就是 O(N).

二叉搜索树中是不能出现相同元素的.

二叉搜索树模拟实现

创建一个二叉搜索树节点类

template<class T>
struct SearchTreeNode
{
	T _data; // 存储数据
	SearchTreeNode<T>* _leftchile; // 指向左孩子
	SearchTreeNode<T>* _rightchild; // 指向右孩子

	SearchTreeNode(const T& data)
		:_data(data),
		_leftchile(nullptr),
		_rightchild(nullptr)
	{}
};

二叉搜索树类创建

template<class T>
class SearchTree
{
	typedef SearchTreeNode<T> SearchTreeNode;
public:
    bool insert(const T& data)
    {}
    bool erase(const T& data)
    {}
    bool find(const T& data)
    {}
private:
	SearchTreeNode* _root;
};

二叉搜索树的插入

二叉搜索树的插入非常简单.
从根节点开始, 如果插入的值小于节点值, 那么向左走,
如果插入的值大于节点值, 那么向右走,
如果值已存在, 那么直接返回 false.

bool insert(const T& data)
{
	SearchTreeNode* node = new SearchTreeNode(data);
	if (_root == nullptr) // 如果 _root 为空, 那么也就需要更新 _root 节点
	{
		_root = node;
		return true;
	}
	else
	{
		SearchTreeNode* prev = nullptr; // 记录插入位置的父节点
		SearchTreeNode* cur = _root; // 查找插入位置
		while (cur != nullptr)
		{
			if (cur->_data == data) // 如果要插入的数据已存在, 直接返回
			{
				return false;
			}
			if (data < cur->_data) // 要插入的数据小于节点数据, 向左走
			{
				prev = cur;
				cur = cur->_leftchile;
			}
			else // 要插入的数据大于节点数据, 向右走
			{
				prev = cur;
				cur = cur->_rightchild;
			}
		}
		if (data < prev->_data) // 判断要插入的位置是左边还是右边
		{
			prev->_leftchile = node;
		}
		else
		{
			prev->_rightchild = node;
		}
		return true;
	}
}

二叉搜索树的删除

1. 被删除的节点最多只有一个孩子

1) 被删除的节点是叶子节点, 没有孩子

这种情况下, 直接将这个节点删除即可

2) 被删除的节点只有左孩子

将本节点删除后, 将节点的左孩子连接到本节点的父节点上

3) 被删除的节点只有右孩子

和只有左孩子相同, 删除本节点, 右孩子连接到本节点的父节点上

void erase(const T& data)
{
	SearchTreeNode* prev = nullptr;
	SearchTreeNode* cur = _root;
	while (cur != nullptr) // 先查找是否存在这个值
	{
		if (data == cur->_data)
		{
			break;
		}
		prev = cur;
		if (data < cur->_data)
		{
			cur = cur->_leftchile;
		}
		else
		{
			cur = cur->_rightchild;
		}
	}
	if (cur == nullptr) // 不存在这个值, 直接返回
	{
		return;
	}
	if (cur->_leftchile == nullptr || cur->_rightchild == nullptr) // 存在这个节点, 这个节点没有孩子, 或者只有一个孩子
	{
		if (cur->_leftchile == nullptr) // 只有右孩子
		{
			if (_root == cur) // 如果要删除的节点就是 _root, 更新 _root
			{
				_root = cur->_rightchild;
			}
			else
			{
				if (prev->_leftchile = cur) // 判断要连接再父节点的哪边
				{
					prev->_leftchile = cur->_rightchild;
				}
				else
				{
					prev->_rightchild = cur->_rightchild;
				}
			}
		}
		else
		{
			if (_root == cur)
			{
				_root = cur->_leftchile;
			}
			else
			{
				if (prev->_leftchile = cur)
				{
					prev->_leftchile = cur->_leftchile;
				}
				else
				{
					prev->_rightchild = cur->_leftchile;
				}
			}
		}
		delete cur;
	}
}

2. 被删除的节点有两个孩子

我们不直接删除这个节点, 使用和 堆 删除节点差不多的方法.

我们将要删除的这个节点和一个最多只有一个孩子的节点进行交换

然后删除那个交换后的值.

那么这个交换的节点怎么选择.

1. 本节点右子树中的最小值的那个节点 (即右子树的最左节点)

2. 本节点左子树中的最大值的那个节点 (左子树的最右节点)

这两个选择方法, 选择出来的要交换的节点的值, 都是最接近 本节点值的 节点.

 找到这个节点之后, 交换 cur 和 child 的值, 然后删除 child 节点即可.

void erase(const T& data)
{
	SearchTreeNode* prev = nullptr;
	SearchTreeNode* cur = _root;
	while (cur != nullptr) // 先查找是否存在这个值
	{
		if (data == cur->_data)
		{
			break;
		}
		prev = cur;
		if (data < cur->_data)
		{
			cur = cur->_leftchile;
		}
		else
		{
			cur = cur->_rightchild;
		}
	}
	if (cur == nullptr) // 不存在这个值, 直接返回
	{
		return;
	}
	if (cur->_leftchile == nullptr || cur->_rightchild == nullptr) // 存在这个节点, 这个节点没有孩子, 或者只有一个孩子
	{
		if (cur->_leftchile == nullptr)
		{
			if (_root == cur)
			{
				_root = cur->_rightchild;
			}
			else
			{
				if (prev->_leftchile = cur)
				{
					prev->_leftchile = cur->_rightchild;
				}
				else
				{
					prev->_rightchild = cur->_rightchild;
				}
			}
		}
		else
		{
			if (_root == cur)
			{
				_root = cur->_leftchile;
			}
			else
			{
				if (prev->_leftchile = cur)
				{
					prev->_leftchile = cur->_leftchile;
				}
				else
				{
					prev->_rightchild = cur->_leftchile;
				}
			}
		}
		delete cur;
	}
	else // 这个节点有两个孩子, 上半部分代码 和 文章上面的代码是一样的
	{
		prev = cur;
		SearchTreeNode* child = cur->_rightchild; // 要删除的节点
		while (child->_leftchile != nullptr) // 查找符合要求的节点
		{
			prev = child;
			child = child->_leftchile;
		}
		cur->_data = child->_data; // 交换数据
		if (child->_rightchild == nullptr) // child 是叶子节点
		{
			if (prev == cur) // 可以看下图演示
			{
				prev->_rightchild = nullptr;
			}
			else
			{
				prev->_leftchile = nullptr;

			}
		}
		else // child 有右子树, 这不可能有左子树, 因为这里找的就是最左节点
		{
			if (prev == cur)
			{
				prev->_rightchild = cur->_rightchild;
			}
			else
			{
				prev->_leftchile = child->_rightchild;

			}
		}
		delete child;
	}
}

那么另一种方法, 和这种方法差不多, 会一种就会另一种. 
去本节点左子树中, 查找最右的节点.

至于查找功能, 无论是再插入还是删除中, 都有这部分操作.