【C++】——高效构建与优化二叉搜索树

标签：高效 cur C++ 二叉 搜索 key root 节点

活着就意味必须要做点什么，请好好努力。

——村上春树 《地下》

---

目录

1、二叉搜索树 BST

1.1什么是二叉搜索树

1.2 BST的性能功能分析

2、二叉搜索树的实现

2.1 BST框架

2.2 BST插入

2.3 BST搜索

2.4 BST删除

2.5 BST细节问题

3、二叉搜索树遍历

3.1中序遍历

3.2前序遍历

3.3后序遍历

4、二叉搜索树的应用

4.1 key搜索场景

4.2 key/value搜索场景

Thanks谢谢阅读！！！

---

1、二叉搜索树 BST

在 C++ 进阶学习中，二叉搜索树是一个重要的知识点。它是基于二叉树的改进版本，相较于普通二叉树，它对数据存储有严格要求，即左节点比根小，右节点比根大，这使得它具有很高的查找效率。学习二叉搜索树是进一步理解更复杂的树结构如 AVL 树和红黑树的基础，最终我们会了解到这些树结构是如何被应用在 C++ 的标准库中的，例如set和map的实现。

因此我们可以回顾一下链式二叉树的结构：

1. 二叉树的度不超过 2
2. 二叉树可以通过数组或链表结构记录，这里我们采用链式结构

1.1什么是二叉搜索树

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

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

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

后续我们学习 map/set/multimap/multiset 系列容器底层就是二叉搜索树，其中map/set不支持持插入相等值，multimap/multiset 支持插入相等值

1.2 BST的性能功能分析

性能分析：

BST的性质使其成为一种高效的搜索工具。在大部分情况下，对于包含 n 个节点的二叉搜索树，搜索、插入和删除等操作的时间复杂度为 O(logn)。然而，在某些情况下，二叉搜索树可能会出现不平衡的情况，导致时间复杂度激增至 O(n)。

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

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

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

为了解决这个问题，出现了进阶版的 AVL 树和红黑树。

AVL 树和红黑树 都是在保持二叉搜索树基本性质的基础上，通过旋转和重新平衡等操作，确保树的高度保持在一个相对平衡的状态，从而保证了操作的时间复杂度始终为 O(logn)。它们的出现大大提高了二叉搜索树在实际应用中的性能和稳定性。
我们常常会选择使用 AVL 树或红黑树来解决搜索问题。

功能分析：

二叉搜索树（Binary Search Tree, BST）是一种非常实用的数据结构，用于存储具有可比较键的数据项。其功能和应用场景非常广泛，主要包括以下几点：

1. 搜索：提供高效的搜索功能，允许快速查找特定键值的数据项。如果树保持平衡，搜索的平均时间复杂度可以保持在 O(log n)。
2. 插入和删除：允许在保持树结构的前提下添加和移除节点。插入和删除操作也尽量维持树的平衡，以避免性能下降。
3. 排序：可以中序遍历二叉搜索树以获得有序的数据序列，这对于数据排序和报表生成等功能非常有用。

应用场景：

一、数据查找

1. 数据库索引：在数据库系统中，二叉搜索树可以作为索引结构，加快数据的查找速度。例如，当你在数据库中查询特定条件的数据时，索引结构可以快速定位到符合条件的数据所在的位置，减少磁盘 I/O 操作次数，提高查询效率。
2. 字典和拼写检查器：在字典软件或文本编辑中的拼写检查功能中，二叉搜索树可以存储单词及其相关信息。通过快速查找单词是否存在于树中，判断输入的单词是否正确拼写。

二、动态数据集合管理

1. 动态排序：当需要动态地维护一个有序的数据集合时，二叉搜索树很有用。每次插入或删除一个元素后，树的结构可以自动调整以保持有序性。比如在一个实时更新的排行榜系统中，二叉搜索树可以快速更新和查询排名信息。
2. 区间查询：可以方便地进行区间查询操作。例如，在一个存储时间序列数据的应用中，可以使用二叉搜索树快速查找特定时间区间内的数据点。

三、资源分配和调度

1. 内存管理：在操作系统的内存管理中，可以使用二叉搜索树来跟踪空闲内存块的大小和位置。当需要分配内存时，可以在树中快速找到合适大小的空闲块进行分配；当内存被释放时，可以将释放的内存块重新插入到树中。
2. 任务调度：在一些任务调度系统中，二叉搜索树可以根据任务的优先级或执行时间进行排序，以便高效地选择下一个要执行的任务。

2、二叉搜索树的实现

2.1 BST框架

整体框架具有节点的结构体，和BST类

节点结构体：

1. 包括左右指针
2. 键值记录节点值

而BST类中包含根节点即可！

namespace xc
{
	//节点结构体 
	template<class K>
	struct BSTreeNode
	{
		//左右指针
		BSTreeNode* _right;
		BSTreeNode* _left;
		//键值
		K _key;

		//构造函数
		BSTreeNode(const K& key)
			: _key(key),
			_right(nullptr),
			_left(nullptr)
		{}
		
	};
	//树的结构
	template<class K>
	class BSTree
	{
	public:
		//typedef BSTreeNode<K> Node;
		using Node = BSTreeNode<K>; //此处作用同上 

	private:
		Node* _root = nullptr;
	};

}

2.2 BST插入

根据二叉搜索树的性质来寻找到合适的位置即可

1. 需要一个当前节点指针和父节点指针，因为插入需要父节点来进行！！！
2. 如果根节点为空指针，那么直接赋值给根节点就可以
3. 小于当前键值就走左边，大于当前键值就走右边，直到找到合适位置

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

bool Insert(const K& key) //实现不支持插入相等值
{
	if (_root == nullptr) //树为空 插入节点直接赋值给根即可
	{
		_root = new Node(key);
		return 1;
	}
	Node* parent = nullptr;//定位cur
	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 return 0;
	}
	//遍历完后 cur为空 需要判断一下key值与parent的大小关系后连接起来
	cur = new Node(key);
	if (parent->_key < key)
	{
		parent->_right = cur;
	}
	else parent->_left = cur;
	
	return 1;
}

思考一下如何递归插入呢？？逻辑其实同理

	bool insertR(const K& key) {
		return InsertR(_root, key);
	}
protected:
	bool InsertR(Node*& root, const K& key) //递归实现插入 这里要理解 *& 
		//Node* &root 表示“指向Node的指针的引用”。
		//这意味着在函数内部对这个引用所做的任何修改，都会直接反映到函数外部调用该函数时所传入的那个指针变量上。
	{
		if (root == nullptr)
		{
			root = new Node(key);
			return 1;
		}
		if (root->_key < key)
		{
			InsertR(root->_right, key);
		}
		else if (root->_key > key)
		{
			InsertR(root->_left, key);
		}
		else return 0;
	}

在这个场景中使用Node*&（指向Node的指针的引用）主要有以下几个原因：

一、实现对外部指针的直接修改

当你想要在函数内部修改函数外部传入的指针时，单纯的指针参数（Node*）做不到这一点。因为在函数内部对指针参数进行赋值操作只会改变函数内部局部的指针副本，不会影响到函数外部实际传入的指针。

而使用引用（Node*&），在函数内部对这个引用所指向的指针进行修改，就会直接反映到函数外部调用该函数时所传入的那个指针变量上。这样就可以在插入新节点时，正确地更新树的根节点或子树的根节点指针，确保新节点被正确地插入到树中。

二、递归调用中的必要性

在递归插入的过程中，每次递归调用都需要能够修改上一层调用中相应的子树指针。如果不使用引用，那么在递归返回时，无法将新插入的节点正确地连接到上一层的树结构中。

例如，当在左子树中插入新节点后，需要更新当前节点的_left指针指向新插入的子树。如果没有引用，这个更新操作无法传播到上一层调用。

综上所述，使用Node*&在递归实现插入操作中是必要的，它确保了可以正确地修改树的结构并将新节点插入到合适的位置。

2.3 BST搜索

搜索逻辑与插入逻辑相似，根据二叉搜索树的性质来寻找到合适的位置即可，小于当前键值就走左边，大于当前键值就走右边，直到找到合适位置

如果不支持插入相等的值，找到key即可返回

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

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

尝试用递归逻辑实现一下查找

    // public:
    bool FindR(const K& key)
    {
    	return _FindR(key);
    }	
    
    //protected:
   	bool _FindR(Node* root, const K& key)
	{
		//递归到叶子节点也没找到
		if (root == nullptr)
			return 0;
		//key值小了 去左子树查找
		if (root->_key > key)
			return _FindR(root->_left, key);
		//key值大了 去右子树查找
		else if (root->_key < key)
			return _FindR(root->_right, key);
		else return 1;
	}

2.4 BST删除

BST的删除可以说是困难的一个函数了，删除逻辑较为复杂，先依照查找的逻辑判断目标值是否存在，如果存在，则进行删除，但是删除节点有多种可能，需要具体问题具体分析；如果不存在，则删除失败。

删除节点可能情况：

• 要删除的结点无孩子结点
• 要删除的结点只有左孩子结点
• 要删除的结点只有右孩子结点
• 要删除的结点有左、右孩子结点

那么就可以根据孩子个数简化一下（两个孩子的节点需要换根）

case A：

由于被删除的节点只有一边有节点，所以只需要把其父节点指向它的指针 指向它的子节点就可以！

但是需要注意一个特殊情况，那就是删除的节点是根节点，需要特殊处理一下：更新根节点

bool Erase(const K& key)
{
	Node* parent = nullptr;
	Node* cur = _root;
	//先查找逻辑
	while (cur)
	{
		if (cur->_key > key)
		{
			parent = cur;
			cur = cur->_left;
		}
		else if (cur->_key < key)
		{
			parent = cur;
			cur = cur->_right;
		}
		// 找到了 考虑节点孩子个数
		else
		{
			//左孩子为空 事实上也包括了 两个孩子为空情况 case A
			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;
				return 1;
			}
			//右孩子空 与左孩子逻辑一样 case A
			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;
				return 1;
			}
			else //两个孩子都不为空 case B
			{
				
			}

		}
	}

}

case B

因为需要删除的节点左右指针都有值，所以不能通过上述的办法来进行操作！！！

采取替换法：

找N左子树的值最大结点R(最右结点)或者N右子树的值最小结点R(最左结点)替代N，因为这两个节点任意一个，放到N的位置，都满足二叉搜索树的规则。替代N的意思就是N和R的两个结点的值交换，转而变成删除R结点，R结点符合 case A，可以直接删除。

这里采用删除结点右子树的最（小）左结点 替代 删除结点

由于 RightMin 是右子树的最小值，那么它就不会有左子树，所以这时候时将 rightMinparent 的指向它的指针指向它的子节点就可以。

else //两个孩子都不为空 case B  采用右子树最（小）左节点
{
				Node* replaceParent = cur; //将 cur值给 替代结点的父亲  防止 没有进入循环 replaceparent是空指针报错
				Node* replace = cur->_right;
				while (replace->_left) //找到 右子树最左节点即 replace  (最左节点那肯定其左孩子为空) 
				{
					replaceParent = replace;
					replace = replace->_left;
				}
				//将 replace值赋值给cur 然后删除 replace即可
				cur->_key = replace->_key;
				
				//case A的删除情况 判断replace 是父节点的左还是右孩子
				if (replace == replaceParent->_left)
					replaceParent->_left = replace->_right;
				else
					replaceParent->_right = replace->_right;
				
				delete replace;
				return 1;
}

这里有一个特殊情况 如果删除的是根呢？ 如果没有 Node* replaceParent = cur; 如下图可能导致删除8时候并没有进入循环 那么存在野指针 replaceParent 的问题

测试一下删除函数

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

t.InOrder();

for (auto e : a)
{
	t.Erase(e);
	t.InOrder();
}

最后实现一下递归版本的删除

//public:
bool EraseR(const K& key)
{
	return _EraseR(_root, key);
}
//protected:

	bool _EraseR(Node*& root, const K& key)
	{
		if (root == nullptr)
			return 0;
		//查找逻辑
		if (root->_key < key)
			return _EraseR(root->_right, key);
		else if (root->_key > key)
			return _EraseR(root->_left, key);
		// 找到要删除的节点，保存待删除节点的信息
		else
		{
			Node* del = root; // 保存待删除的节点

			// 如果右子树为空，直接将左子树覆盖
			if (root->_right == nullptr) {
				root = root->_left;
			}
			// 如果左子树为空，直接将右子树覆盖
			else if (root->_left == nullptr) {
				root = root->_right;
			}
			else
			{
				// 找到右子树的最左节点（替代节点）
				Node* minRight = root->_right;
				while (minRight->_left)
					minRight = minRight->_left;

				// 将当前节点的值替换为替代节点的值
				//root->_key = minRight->_key;
				
				//也可以直接交换值
				swap(root->_key, minRight->_key);
				// 递归删除替代节点 为什么赋值不传 key呢？ key是最初要删掉的值我们已经覆盖掉了 只需要将用来覆盖的节点删除即可
				//如果交换实现 可以传key

				return _EraseR(root->_right, key);
			}

			delete del; // 释放待删除节点的内存
			return true;
		}
	}

这里为什么还是传 root->_right 而不是 minRight 是有原因的：
1. 保持二叉搜索树的结构特性：
- 二叉搜索树的删除操作需要确保删除节点后树仍然满足其结构特性，即左子树的所有节点值小于根节点值，右子树的所有节点值大于根节点值。
- 当找到替代节点 minRight 后，将其值与待删除节点交换，此时要删除的节点实际上变成了 minRight 。
- 由于 minRight 是 root->_right 子树中的节点，为了确保在递归删除过程中能够正确地从右子树中删除这个节点，需要将 root->_right 作为参数传递给 _EraseR 函数。这样可以保证在递归过程中，始终从正确的子树中进行删除操作，从而维护二叉搜索树的结构。
2. 正确的递归路径：
- 如果传递 minRight 作为参数，那么在递归调用时，将从一个孤立的节点开始进行删除操作，而不是从正确的子树位置开始。这可能导致无法正确地遍历树以找到要删除的节点，并且可能破坏树的结构。
- 传递 root->_right 可以确保递归从正确的子树位置开始，继续按照二叉搜索树的规则进行查找和删除操作。

2.5 BST细节问题

• 拷贝赋值

如果使用系统默认的拷贝构造和赋值重载函数，会导致浅拷贝问题，多个指针可能指向同一块内存空间，从而在销毁时出现重复析构的错误。因此需要自己实现深拷贝的拷贝构造函数和赋值重载函数。

		// 强制生成构造
	BSTree() = default;
    
    BSTree(const BSTree& t)
	{
		_root = Copy(t._root);
	}

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

//protected
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;
}

递归太抽象了，来一个例子

     5
   /   \
  3     7
 / \   / \
2   4 6   8

一开始，函数调用Copy(root)，传入根节点 5。此时创建一个新节点，值为 5，然后开始处理左子树。

左子树处理过程：

• 进入左子树，处理节点 3。创建新节点，值为 3，接着处理其左子树，也就是节点 2。
• 创建节点 2 的副本，值为 2。然后回到节点 3，处理其右子树，即节点 4。
• 创建节点 4 的副本，值为 4。此时节点 3 的左右子树都处理完毕，返回节点 3 的副本。

回到根节点处理右子树：

• 进入右子树，处理节点 7。创建新节点，值为 7，接着处理其左子树，也就是节点 6。
• 创建节点 6 的副本，值为 6。然后处理其右子树，即节点 8。
• 创建节点 8 的副本，值为 8。此时节点 7 的左右子树都处理完毕，返回节点 7 的副本。

最后，根节点 5 的左右子树都有了副本，整个二叉树的拷贝完成。

• 树的销毁

由于二叉搜索树的节点是通过new创建在堆上的，所以在销毁二叉搜索树时需要递归地释放每个节点的内存。这里采用后序遍历的方式，先释放左右子树，再释放根节点。  

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



void Destroy(Node* _root)
{
	if (_root == nullptr)
		return;
	Destroy(_root->_left);
	Destroy(_root->_right);
	delete _root;
}

3、二叉搜索树遍历

3.1中序遍历

二叉搜索树的中序遍历是升序排列的，这个性质很重要

//pubilc

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

//protected

//左 根 右
void _InOrder(Node* cur)
{
	if (cur == nullptr)
		return;
	_InOrder(cur->_left);
	cout << cur->_key << ' ';
	_InOrder(cur->_right);
}

可以看到实现了一种升序 打印

3.2前序遍历

前序遍历顺序是根 -> 左 -> 右

// public
void PrevOrder()
{
	_PrevOrder(_root);
	cout << endl;
}

//protected

// 根 左 右
void _PrevOrder(Node* cur)
{
	if (cur == nullptr)
		return;
	cout << cur->_key << ' ';
	_PrevOrder(cur->_left);
	_PrevOrder(cur->_right);
}

3.3后序遍历

后序遍历顺序是左 -> 右 -> 根。实现方式与前序和中序遍历类似。

//public

void PostOrder()
{
	_PostOrder(_root);
	cout << endl;
}


//protected

// 左 右 根
void _PostOrder(Node* cur)
{
	if (cur == nullptr)
		return;
	_PostOrder(cur->_left);
	_PostOrder(cur->_right);
	cout << cur->_key << ' ';
}

4、二叉搜索树的应用

如何将二叉搜索树应用起来呢？

4.1 key搜索场景

K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。
比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：

• 以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树
• 在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。

xc::BSTree<string> t;

string dictionary[] = { "apple", "banana", "cherry", "date", "elderberry" };

for (string &word : dictionary) {
	t.	Insert(word);
}
string wordToCheck = "banana";
bool isCorrect = t.Find( wordToCheck);
if (isCorrect) {
	cout << wordToCheck << " is spelled correctly." << endl;
}
else {
	cout << wordToCheck << " is spelled incorrectly." << endl;
}

4.2 key/value搜索场景

key/value  我们就需要设置合适的 K V映射 (key-val)

namespace key_value
{
	template<class K,class V>
	struct BSTNode
	{
		K _key;
		V _value;
		BSTNode<K,V>* _left;
		BSTNode<K,V>* _right;
		BSTNode(const K& key,const V& value)
			:_key(key)
			,_value(value)
			, _left(nullptr)
			, _right(nullptr)
		{}
	};

KV模型：每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。该种方式在现实生活中非常常见：

• 比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文<word, chinese>就构成一种键值对；

key_value::BSTree<string, string> dict;
//BSTree<string, string> copy = dict;

dict.Insert("left", "左边");
dict.Insert("right", "右边");
dict.Insert("insert", "插入");
dict.Insert("string", "字符串");
string str;
while (cin >> str)// ctrl+z 和换行 结束
{
	auto ret = dict.Find(str);
	if (ret)
	{
		cout << "->" << ret->_value << endl;
	}
	else

	{
		cout << "无次单词，请重新输入" << endl;
	}
}

• 再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是<word, count>就构成一种键值对

	string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",

"苹果", "香蕉", "苹果", "香蕉" };
	key_value::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 == NULL)
		{
			countTree.Insert(str, 1);
		}
		else
		{
			ret->_value++;
		}
	}
	countTree.InOrder();

Thanks谢谢阅读！！！

标签：高效,cur,C++,二叉,搜索,key,root,节点
From： https://blog.csdn.net/2402_82668782/article/details/143326790