C++：二叉搜索树

HZzzzzLu

发布于 2024-11-26 08:21:04

1190

文章被收录于专栏：coding

二叉搜索树

概念性质

二叉搜索树（Binary Search Tree，简称BST），也称为二叉排序树或者二叉查找树，是一种具有特殊性质的二叉树，可以用于数据的快速查找、插入和删除。

二叉搜索树中可以支持插入相等的值，也可以不支持，具体看使用场景定义。map/set/multimap/multiset系列容器底层就是二叉搜索树，其中map/set不支持插入相等值，multimap/multiset支持插入相等值。

性质

节点的键值大于左子树上任何节点的键值。
节点的键值小于右子树上任何节点的键值。
左右子树也必须分别为二叉搜索树。
左子树所有节点的键值比根节点的键值小，右子树所有节点的键值比根节点的键值大。

优点

有序性：易于实现有序相关操作，如查找最大最小值、元素排序等。
搜索效率：在平衡的情况下，搜索、插入和删除操作的时间复杂度为O(log N)。
动态性：可以动态插入和删除数据。

缺点

会退化：在最坏的情况下（输入数据有序或逆序），二叉搜索树会退化成单链表，操作的时间复杂度退化O(N)。
需要平衡：为了保持高效的操作，可能需要通过额外的算法（AVL树、红黑树）来保持树的平衡。

性能分析

最优情况下，二叉搜索树接近为完全二叉树，其高度为logN。

最差情况下，二叉搜索树退化成近似链或者链，其高度为N。

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

只有在平衡的情况下，二叉搜索树增删查改的时间复杂度为O(log N)。

二分查找也能实现O(log N)级别对的查找效率，但二分查找有两个缺点：

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

2.插入删除数据需要挪动数据，效率较低。

实现代码

我们来实现一棵没有冗余的二叉搜索树（不允许相同值的插入）。

前置准备

二叉搜索树的节点

template<class K>
struct BSTNode
{
	K _key;
	BSTNode* _left;
	BSTNode* _right;

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

二叉搜索树


template<class K>
class BSTree
{
	//typedef BSTNode<K> Node;
	using Node = BSTNode<K>;
public:
	BSTree() = default;

	BSTree(const BSTree& t)
	{
		_root = Copy(t._root);
	}

	BSTree& operator=(BSTree tmp)
	{
		swap(_root, tmp._root);
		return *this;
	}

	~BSTree()
	{
		Destroy(_root);
		_root = nullptr;
	}


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

private:

	void Destroy(Node* root)
	{
		if (root == nullptr)
			return;

		Destroy(root->_left);
		Destroy(root->_right);
		delete 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 _InOrder(Node* root)
	{
		if (root == nullptr)
			return;
		_InOrder(root->_left);
		cout << root->_key << " ";
		_InOrder(root->_right);
	}

private:
    Node * _root = nullptr;
};

要点

1.C++11可以使用using进行重定义。

2.我们写了拷贝构造函数后，就不会生成构造函数了，我们可以使用default强制生成构造函数。

3.拷贝构造需要用到前序遍历，析构、遍历二叉搜索树需要用到中序遍历（中序遍历得到有序的数据），而这都需要用到递归，但是递归需要传递root节点，这几个函数直接传递root节点都会出问题，以析构函数为例子，析构函数是无参的，传了参数就会出问题。所以类里写递归的方达是套多一层函数就行了。

4.对于赋值重载，传递一个普通的BSTree对象就行了，由于是传值传参，会发生拷贝构造，所以在函数里就有了一个临时的tmp对象，直接将_root与tmp._root的值交换就可以完成赋值重载的目的。（tmp对象在函数结束后就调用析构函数销毁了，也不用我们主动调用了）

5.写一个中序遍历遍历二叉搜索树，以便观察结果。

插入

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

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

	//树不为空，找到应该插入的位置
	while (cur)
	{
		//插入的key大于当前节点的key，cur往右走，小于往左走，相等返回flase
		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);
	//注意判断新节点连接在parent的左边还是右边
	if (key > parent->_key)
	{
		parent->_right = cur;
	}
	else
	{
		parent->_left = cur;
	}

	return true;
}

插入有以下几种情况：

1.树为空，新增节点，赋值给root指针。 2.树不为空，按照二叉树的性质，插入值比当前节点大往右走，插入值比当前节点小往左走，找到空位值，插入新节点。 3.如果支持插入相等的值，插入值跟当前节点的值相等，可以往右走也可以往左走，找到空位置插入就行，但要保持二叉搜索树的性质。我们这里实现的二叉搜索树不允许插入相等的值，返回false就行了。

注意插入的时候，因为cur走到空了，说明找到插入位置了，但具体的插入应该是当前节点的父亲节点连接新节点，所以我们还需要一个parent节点记录当前节点的父亲节点。

我们测试一下。

int main()
{
	BSTree<int> t;
	int arr[] = { 8, 3, 1, 7, 4, 15, 13 };
	for (auto e : arr)
	{
		t.Insert(e);
	}

	t.InOrder();
	return 0;
}

查找

在二叉搜索树查找某个值x就比较简单了，x比当前节点的值大往左走，比当前节点的值小往右走，最多查找高度次，走到空，那就说明没找到，返回false，找到了就返回true。

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

	return false;
}

删除（重点）

给定一个元素，删除与该元素相等的节点。

删除操作是二叉搜索树增删查中最为复杂的操作，我应该如下考虑。

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

如果元素存在则有以下情况：（假设删除节点为N）

N节点的左孩子为空或者右孩子为空（左右孩子为空的情况也属这类）。
N节点的左孩子和右孩子都不为空。

解决方案如下：

对于情况1，假如N节点的左孩子为空，把N节点的父亲对应孩子指针指向N的右孩子，删除N节点。（N节点的右孩子为空也类似这样处理）
对于情况2，无法直接删除N节点，因为N的两个孩子无处安放，只能用替代法删除。首先找N的左子树的最大节点或者右子树的最小节点（记为R节点），将其替代N节点，然后删除R节点。至于为什么这样做？是因为只有这两个特定节点中的一个去替代N节点才能继续满足二叉搜索树的性质。

删除操作还需思考以下的特殊情况：

1.在情况1的条件下，删除的节点是根节点要特殊处理；要找到N节点的对应孩子指针（判断N节点是父亲的左孩子还是右孩子），因为要把父亲节点和N节点的孩子连接，如果不知道N节点是父亲的左孩子还是右孩子就随便乱连，二叉树就会被破坏。

2.在情况2的条件下，假设找的R节点是右子树的最小节点，N节点的右子树的最小节点就是N节点的右孩子（右子树的第一个节点）的情况，这种情况的存在就导致了在删除R节点时无法确定R节点是其父亲的左孩子还是右孩子，要特殊处理。

该特殊情况如下图：

一般删除的情况：

下面看删除的具体代码

bool Erase(const K& 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 // key == cur->_key; 删除
		{
			
			if (cur->_left == nullptr) //左为空，连接cur->_right
			{
				if (cur == _root)
				{
					_root = cur->_right;
				}
				else
				{
					//判断要删除的cur节点是parent节点的左节点还是右节点
					if (parent->_left == cur)
					{
						parent->_left = cur->_right;
					}
					else
					{
						parent->_right = cur->_right;
					}
				}
				delete cur;
			}
			else if (cur->_right == nullptr) //右为空，连接cur->_left
			{
				if (cur == _root)
				{
					_root = cur->_left;
				}
				else
				{
					if (parent->_left == cur)
					{
						parent->_left = cur->_left;
					}
					else
					{
						parent->_right = cur->_left;
					}
				}
			}
			else //左右孩子都不为空
			{
				//找替代节点（右子树的最小节点）
				Node* ReplaceParent = cur; //这里R节点的父亲的初始值不能给成nullptr，不然在特殊情况下会出现解引用空指针的错误
				Node* Replace = cur->_right;

				while (Replace->_left)
				{
					ReplaceParent = Replace;
					Replace = Replace->_left;
				}

				//直接覆盖要删除的节点值
				cur->_key = Replace->_key;

				//判断R节点是其父亲的左孩子还是右孩子，连接R节点的右孩子（左为空的情况）
				if (ReplaceParent->_left == Replace)
				{
					ReplaceParent->_left = Replace->_right;
				}
				else
				{
					ReplaceParent->_right = Replace->_right;
				}
				delete Replace;
			}
			return true;
		}
	}

	return false;
}

测试

int main()
{
	BSTree<int> t;
	int arr[] = { 8, 3, 1, 7, 4, 15, 13 };
	for (auto e : arr)
	{
		t.Insert(e);
	}

	t.InOrder();
	
	for (auto e : arr)
	{
		t.Erase(e);
		t.InOrder();
	}
	return 0;
}

假如我们让R节点的父亲节点的初值给成空指针，编译器是会报警告的。

key和key/value的使用场景

key搜索场景

只有key作为关键码，结构中只需要存储key即可，关键码即为需要搜索到的值，搜索场景只需要判断key在不在。key的搜索场景实现的⼆叉树搜索树⽀持增删查，但是不⽀持修改，修改key破坏搜索树结构了。

场景1：小区无人值守车库，买了车位的业主车才能进小区，物业会把有车位的业主的车牌号录入后台系统，车辆进入扫描车辆在不在系统中，在则抬杠，不在则提示非小区车辆，无法进入。

场景2：检查⼀篇英文文章单词拼写是否正确，将词库中所有单词放入二叉搜索树，读取文章中的单词，查找是否在二叉搜索树中，不在则波浪线标红提示。

key/value搜索场景

每⼀个关键码key，都有与之对应的值value，value可以任意类型对象。树的结构中(结点)除了需要存储key还要存储对应的value，增/删/查还是以key为关键字走二叉搜索树的规则进行比较，可以查找到key对应的value。key/value的搜索场景实现的二叉树搜索树支持修改value，但是不支持修改key，会破坏搜索树结构。场景1：中英互译字典

场景2：商场无人值守车库，入口进场时扫描车牌，记录车牌和入场时间，出口离场时，扫描车牌，查找入场时间，用当前时间减去入场时间计算出停车时长，计算出停车费用，缴费后抬杆，车辆离场。

场景3：统计一篇文章单词出现的次数，读取一个单词，查找单词是否存在，不存在说明这个单词第一次出现，若存在，则单词对应的次数+1。

key/value二叉搜索树代码实现

只需要对上面代码做些许修改即可，不过多讲解。

template<class K, class V>
struct BSTNode
{
	K _key;
	V _value;
	BSTNode* _left;
	BSTNode* _right;

	BSTNode(const K& key, const V& value)
		:_key(key)
		,_value(value)
		, _left(nullptr)
		, _right(nullptr)
	{}
};

template<class K, class V>
class BSTree
{
	//typedef BSTNode<K> Node;
	using Node = BSTNode<K, V>;
public:
	BSTree() = default;

	BSTree(const BSTree& t)
	{
		_root = Copy(t._root);
	}

	BSTree& operator=(BSTree tmp)
	{
		swap(_root, tmp._root);
		return *this;
	}

	~BSTree()
	{
		Destroy(_root);
		_root = nullptr;
	}

	bool Insert(const K& key, const V& value)
	{
		//树为空
		if (_root == nullptr)
		{
			_root = new Node(key, value);
			return true;
		}

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

		//树不为空，找到应该插入的位置
		while (cur)
		{
			//插入的key大于当前节点的key，cur往右走，小于往左走，相等返回flase
			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, value);
		//注意判断新节点连接在parent的左边还是右边
		if (key > parent->_key)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}

		return true;
	}

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

		return nullptr;
	}

	bool Erase(const K& 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 // key == cur->_key; 删除
			{

				if (cur->_left == nullptr) //左为空，连接cur->_right
				{
					if (cur == _root)
					{
						_root = cur->_right;
					}
					else
					{
						//判断要删除的cur节点是parent节点的左节点还是右节点
						if (parent->_left == cur)
						{
							parent->_left = cur->_right;
						}
						else
						{
							parent->_right = cur->_right;
						}
					}
					delete cur;
				}
				else if (cur->_right == nullptr) //右为空，连接cur->_left
				{
					if (cur == _root)
					{
						_root = cur->_left;
					}
					else
					{
						if (parent->_left == cur)
						{
							parent->_left = cur->_left;
						}
						else
						{
							parent->_right = cur->_left;
						}
					}
				}
				else //左右孩子都不为空
				{
					//找替代节点（右子树的最小节点）
					Node* ReplaceParent = cur; //这里R节点的父亲的初始值不能给成nullptr，不然在特殊情况下会出现解引用空指针的错误
					Node* Replace = cur->_right;

					while (Replace->_left)
					{
						ReplaceParent = Replace;
						Replace = Replace->_left;
					}

					//直接覆盖要删除的节点值
					cur->_key = Replace->_key;

					//判断R节点是其父亲的左孩子还是右孩子，连接R节点的右孩子（左为空的情况）
					if (ReplaceParent->_left == Replace)
					{
						ReplaceParent->_left = Replace->_right;
					}
					else
					{
						ReplaceParent->_right = Replace->_right;
					}
					delete Replace;
				}
				return true;
			}
		}

		return false;
	}

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

private:

	void Destroy(Node* root)
	{
		if (root == nullptr)
			return;

		Destroy(root->_left);
		Destroy(root->_right);
		delete root;
	}

	Node* Copy(Node* root)
	{
		if (root == nullptr)
			return nullptr;

		Node* newRoot = new Node(root->_key, root->_value);
		newRoot->_left = Copy(root->_left);
		newRoot->_right = Copy(root->_right);
		return newRoot;
	}

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

private:
	Node* _root = nullptr;
};

测试

int main()
{
	string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
	"苹果", "香蕉", "苹果", "香蕉" };
	BSTree<string, int> countTree;

	for (const auto& str : arr)
	{
		// 先查找水果在不在搜索树中
		// 1、不在，说明水果第一次出现，则插入<水果, 1>
		// 2、在，则查找到的结点中水果对应的次数++
		//BSTreeNode<string, int>* ret = countTree.Find(str);
		auto ret = countTree.Find(str);
		if (ret == nullptr)
		{
			countTree.Insert(str, 1);
		}
		else
		{
			// 修改value
			ret->_value++;
		}
	}
	countTree.InOrder();


	BSTree<string, int> copy = countTree;
	copy.InOrder();

	return 0;
}