QuiteCoder

QuiteCoder

关注
发信
关注(28)粉丝(399)

【c++】二叉搜索树（BST）

【c++】二叉搜索树（BST）-LMLPHP

🔥个人主页：Quitecoder

🔥专栏：c++笔记仓

【c++】二叉搜索树（BST）-LMLPHP

1.二叉搜索树的介绍

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

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

它在动态数据集合中维护了一定的排序顺序，以便实现快速的数据查找、插入和删除操作

【c++】二叉搜索树（BST）-LMLPHP
左子树比根小，右子树比根大

比如我想查找13，就不需要暴力比较，按照大小往左边或者右边走

对于二叉搜索树，进行中序遍历为升序

2.二叉搜索树的操作与实现

首先我们构建节点：

template<class K>
struct BSTreeNode
{
	K _key;
	BSTreeNode<K>* _left;
	BSTreeNode<K>* _right;
	BSTreeNode()
		:_key(K())
		,_left(nullptr)
		,_right(nullptr)
	{}
	BSTreeNode(const K& key)
		: _key(key)
		, _left(nullptr)
		, _right(nullptr)
	{}
};

每个节点有两个指针，分别指向它的左子节点和右子节点。如果子节点不存在，则这些指针为nullptr

  1. 默认构造函数：
BSTreeNode()
	:_key(K())
	,_left(nullptr)
	,_right(nullptr)
{}

默认构造函数，它初始化键值为K类型的默认值（通过调用K的默认构造函数），并将左右子节点指针都设置为nullptr，表示节点没有子节点

  1. 参数化构造函数：
BSTreeNode(const K& key)
	: _key(key)
	, _left(nullptr)
	, _right(nullptr)
{}

采用键值作为参数的构造函数，它会创建一个节点，这个节点的键值为传入的key值，同时初始化左右子节点指针为nullptr

接着我们来完成主体部分：

template<class T>
class BSTree
{
public:
	typedef BSTreeNode<T> Node;
private:
	Node* _root = nullptr;
};

insert插入

【c++】二叉搜索树（BST）-LMLPHP
比如插入5，我们从根节点开始，比8小，往左走，比3大，往右走…：

【c++】二叉搜索树（BST）-LMLPHP

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

所以遇到相同的直接返回false，但是最后一步插入，我们还需要父亲位置的节点来完成左边插入或者右边插入，所以我们需要一个父亲节点来记录位置：

bool Insert(const T& 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
		{
			return false;
		}
	}
	cur = new Node(key);
	if (parent->_key < key)
	{
		parent->_right = cur;
	}
	else
	{
		parent->_left = cur;
	}
	return true;
}

由于我们是从根部开始向下遍历直到达到叶节点，parent->_key必定不等于key（因为有重复检查）。如果parent的键值小于插入的键值key，新节点被设置为父节点的右子树；否则设置为左子树

注意

这里如果起始为**空树*

Node* cur = _root;
while (cur)
{
    // ...
}

由于cur是从_root开始的，如果跳过判空且_root实际上为nullptr，这个循环不会执行任何操作，因为它的条件立即不满足（cur此时为nullptr），并且会跳到循环之后的代码，如下：

cur = new Node(key);
// ...

这里将创建一个新的节点，但此时变量parent仍然是nullptr。代码会接着尝试访问parent的_key成员：

if (parent->_key < key)
{
    // ...
}

因为parent是nullptr，这会导致未定义行为，最常见的是程序崩溃，因为你不能对nullptr解引用。另外，即使程序不崩溃，新的节点cur也没有父节点可以挂载到，这样二叉搜索树的结构就不完整了

所以完整代码如下：

bool Insert(const T& key)
{
	if (_root == nullptr)
	{
		_root = new Node(key);
		return true;
	}
	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
		{
			return false;
		}
	}
	cur = new Node(key);
	if (parent->_key < key)
	{
		parent->_right = cur;
	}
	else
	{
		parent->_left = cur;
	}
	return true;
}

Find查找

find这里思路很简单，就按照大小关系往下遍历即可：

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

InOrder中序遍历

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

这里我们需要传入根节点，为类成员，单独一个函数是无法实现的，所以我们先完成上面的子函数书写，再一个主函数传入_root即可

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

测试如下：

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

for (int e : a)
{
	b1.Insert(e);
}
b1.InOrder();

【c++】二叉搜索树（BST）-LMLPHP

Erase删除

二叉树的删除是这里的难点，因为它涉及到多种情况，针对不同的情况我们对应不同的方法：

  1. 要删除的结点无孩子结点
  2. 要删除的结点只有左孩子结点
  3. 要删除的结点只有右孩子结点
  4. 要删除的结点有左、右孩子结点

前三种情况可以结合起来：

情况2：删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点–直接删除

情况3：删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点–直接删除

情况4：替换法解决

对于一个节点，它的：

  • 中序前驱是它左子树中的最大节点，它小于该节点且最接近它。
  • 中序后继是它右子树中的最小节点，它大于该节点且最接近它。

替换法删除的思路分为以下步骤：

  1. 找到需要被删除的节点。
  2. 检查这个节点是否有两个子节点：
    • 如果不是，处理起来比较简单，可以直接删除。如果该节点只有一个子节点，则该子节点取代被删除节点的位置。如果是叶节点，可以直接移除。
    • 如果是，执行以下步骤。
  3. 选择使用中序前驱或中序后继来替换要删除的节点。我们通常默认使用中序后继，但两者均可。
  4. 找到中序后继节点：
    • 进入待删除节点的右子树，然后一直向左走，直到找到没有左子节点的节点；这是中序后继。
  5. 替换：
    • 复制中序后继节点的值到待删除节点中，覆盖原有值
    • 此时，待删除节点的值已更新为其中序后继节点的值，原来的中序后继节点可以被移除（因为它已经被复制了）。需要注意，这个中序后继节点不会有左子节点（因为它已经是某个子树中的最左侧节点），所以它要么是一个叶节点，要么只有一个右子节点
  6. 删除中序后继节点：
    • 通过调整指针，将中序后继节点的父节点指向其可能存在的右子节点（也可能为空），完成删除操作

进行这样的替换之后，二叉搜索树的特性依然得以保持。中序后继节点保证了替换后的节点值仍然比其左子节点的所有值大，且比其右子节点（除了被移除的中序后继节点外）的所有值小

替换法删除操作需要注意的关键点是，通过中序前驱或中序后继节点替换，

	bool Erase(const T& key)
{
	if (_root == nullptr)
		return false;
	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
		{
			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;
			}
			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;

			}
			else
			{
				//左右都不为空，替换法删除
				Node* rightminparent = cur;
				Node* rightmin = cur->_right;
				while (rightmin->_left)
				{
					rightminparent = rightmin;
					rightmin = rightmin->_left;
				}
				cur->_key = rightmin->_key;
				if (rightminparent->_left = rightmin)
				{
					rightminparent->_left = rightmin->_right;
				}
				else
				{
					rightminparent->_right = rightmin->_right;
				}
				delete rightmin;
			}

			return true;
		}
	}
	return false;
}

我们拆分来看这串代码：

  1. 检查树是否为空:
if (_root == nullptr)
    return false;

  1. 查找需删除的节点:
    代码通过while循环遍历树找到匹配key的节点。在循环中使用变量cur作为当前节点，变量parent作为cur的父节点

  2. 节点匹配:
    当找到与key匹配的节点后:

    • 如果该节点没有左子节点(cur->_left == nullptr), 那么它的右子节点直接替换它（也适用于它没有子节点的情况）
    • 如果该节点没有右子节点(cur->_right == nullptr), 那么它的左子节点直接替换它
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;
}

如果cur恰好是根节点，

如果cur不是根节点，我们需要更新它父节点的相应指针。我们。这样，在二叉搜索树中删除了cur节点，并保持了其右子树

    • 如果该节点既有左子节点也有右子节点, 那么需要找到该节点的中序后继节点来替代它。中序后继节点是在其右子树中值最小的节点。我们替换cur的键为中序后继节点的键，并将rightmin放在原来的位置上。
else
{
	//左右都不为空，替换法删除
	Node* rightminparent = cur;
	Node* rightmin = cur->_right;
	while (rightmin->_left)
	{
		rightminparent = rightmin;
		rightmin = rightmin->_left;
	}
	cur->_key = rightmin->_key;
	if (rightminparent->_left == rightmin)
	{
		rightminparent->_left = rightmin->_right;
	}
	else
	{
		rightminparent->_right = rightmin->_right;
	}
	delete rightmin;
}

注意，在替换完成后需要删除原始的中序后继节点。这时rightmin的右子节点（如果存在）会替换rightmin。

每次删除一个节点后，代码会释放该节点的内存。

  1. 维护父节点指针:
    删除过程中对父节点指针的适当维护是必须的，以确保删除节点后树的结构保持正确。比如，如果待删除节点是其父节点的左子节点，那么父节点的左指针应该指向待删除节点的相应子节点

最后，如果在树中找到并成功删除了key对应的节点，则函数返回true。如果没有找到，则函数返回false。

3.二叉搜索树的应用（K与KV模型）

  1. K模型：
    • K模型指的是二叉树的节点仅存储键Key）信息，而没有与键相关联的特定“值”（Value）。换句话说，节点中的数据只有一个维度，节点的排序和组织就是基于这些键
    • 在K模型的二叉树中，例如二叉搜索树（BST），节点的位置由其键的顺序决定。所有的节点操作，包括插入、查找和删除都是根据这个键来执行的。
  • 比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：
    • 以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树
    • 在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误
  1. KV模型：
    • KV模型指的是二叉树的节点存储“键值对”（Key-Value Pair）。这里“键”（Key）用于确定节点的位置跟顺序，“值”（Value）则是与键关联的数据。
    • 在KV模型的二叉树中，节点依然是根据键的顺序进行排列和组织的，但是与每个键都有一个相对应的值。这种模式适用于情况更为复杂的场景，如实现映射或字典结构。
    • KV模型的一个典型例子是映射（Map）或词典（Dictionary）

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

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

改造二叉树为KV结构

节点构建，加一个模版参数V

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

代码主题部分只需要进行简单的修改即可：

template<class K,class V>
class BSTree
{
public:
	typedef BSTreeNode<K,V> Node;
	bool Insert(const K& key,const V& value)
	{........
	cur = new Node(key,value);
     ........
	}
	Node* 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 cur;
		}
	}
	return nullptr;
    }
	........
};

其余部分不需要改变

简单示例如下：

void TestBSTree2()
	{
		BSTree<string, string> dict;
		dict.Insert("string", "字符串");
		dict.Insert("left", "左边");
		dict.Insert("insert", "插入");
		//...

		string str;
		while (cin >> str)
		{
			BSTreeNode<string, string>* ret = dict.Find(str);
			if (ret)
			{
				cout << ret->_value << endl;
			}
			else
			{
				cout << "无此单词，请重新输入" << endl;
			}
		}
	}

本节内容到此结束！ 感谢阅读！！

4.二叉搜索树性能分析

插入和删除操作都必须先查找，

但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：

最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其平均比较次数为O(log n)

【c++】二叉搜索树（BST）-LMLPHP
最差情况下，二叉搜索树退化为单支树(或者类似单支)，查找的时间复杂度为O(n)

【c++】二叉搜索树（BST）-LMLPHP
如果退化成单支树，二叉搜索树的性能就失去了。那能否进行改进，不论按照什么次序插入关键码，二叉搜索树的性能都能达到最优？

期待后续AVL树和红黑树的讲解

本节内容到此结束！！感谢阅读！！

05-13 23:21
Powered by LMLPHP ©2024 QuiteCoder 0.008765