数据结构与算法：树形查找-Toy模板网

这篇具有很好参考价值的文章主要介绍了数据结构与算法：树形查找。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一.二叉排序树（BST）

1.个人理解

左子树结点值 < 根结点值 < 右子树结点值
对二叉排序树进行中序遍历，可以得到一个递增的有序数列

2.二叉树查找

原理：

对于一个给定的二叉排序树，如果要查找一个节点，可以按照以下步骤进行：

从根节点开始比较。

如果要查找的值等于当前节点的值，则找到了目标节点，返回该节点。

如果要查找的值小于当前节点的值，则在左子树中继续查找。

如果要查找的值大于当前节点的值，则在右子树中继续查找。

如果在整棵树中都没有找到目标节点，则返回空指针或者抛出异常表示未找到。

时间复杂度为O(log n)，其中n为树中节点的数量，因为每次查找都会将搜索范围缩小一半。

3.查找算法实现

//在二叉排序树中查找值为key的结点
BSTNode *BST_ _Search(BSTree T,int key){
	while(T!=NULL&&key!=T->key){ 
	//若树空或等 于根结点值，则结束循环
	if(key<T->key) 
		T=T->lchild;                  //小于，则在左子树上查找
	else 
		T=T->rchild;                  //大于，则在右子树上查找
	}
	return T;
}

这个过程显然是一个递归的过程，可以使用递归来完成查找，这里并没有使用递归，递归算法编写请参考【递归算法】

4.二叉排序树插入

原理：

若原二叉排序树为空，则直接插入结点:否则，若关键字k小于根结点值，则插入到左子树，若关键字k大于根结点值，则插入到右子树。

算法实现：

//在二叉排序树插入关键字为k的新结点(递归实现)
int BST_ Insert(BSTree &T, int k){
	if(T==NULL){                        //原树为空， 新插入的结点为根结点
		T=(BSTree)malloc(sizeof(BSTNode));
		T->key=k;
		T->lchild=T->rchild=NULL
		return 1;                      //返回1，插入成功
	}
	else if(k==T->key)                  //树中存在相同关键字的结点，插入失败
		return 0;
	else if(k<T->key)                   //插入到T的左子树
	return BST_ Insert(T->lchild,k);
else                                    //插入到T的右子树
	return BST_ Insert(T->rchild,k);
}

5.二叉排序树删除

二叉排序树的删除操作需要分为以下几个步骤：

查找待删除节点：从根节点开始，比较待删除节点的关键字和当前节点的关键字，如果相等，则找到了待删除节点；否则，继续在左子树或右子树中查找。
分情况讨论：

a. 待删除节点没有左右子树：直接删除该节点即可；

b. 待删除节点只有左子树或右子树：将待删除节点的左子树或右子树挂在其父节点的相应位置上，并删除待删除节点；

c. 待删除节点既有左子树又有右子树：找到待删除节点的中序遍历的前驱或后继节点（即比待删除节点小的最大节点或比待删除节点大的最小节点），用前驱或后继节点的值替换待删除节点的值，然后将问题转化成删除前驱或后继节点。
如果删除的是根节点，则需要将新的根节点返回。

原理图：

数据结构与算法：树形查找

代码可以参考数据结构专栏之树这一篇博客，我以后会写的。

二.平衡二叉树（AVL树）

1.平衡二叉树

平衡二叉树（Balanced Binary Tree），简称平衡树，是一种特殊的二叉查找树。它的特点是：任意节点的左右子树高度差不超过1，即每个节点的左右子树高度之差的绝对值都不超过1。这样可以保证查找、插入和删除等操作的时间复杂度为O(log n)，提高了树的性能。

平衡二叉树的常见实现有AVL树、红黑树、B树等，其中AVL树是最早被发明的平衡树之一。AVL树要求每个节点的左右子树高度差的绝对值不超过1，并在插入或删除节点后通过旋转操作来自动调整树的结构以满足平衡条件。

平衡二叉树的优点是在保证基本的查找、插入、删除操作的时间复杂度为O(log n)的同时，还具有较好的空间利用率和较小的树高，适合存储大量数据的情况。缺点是相比于普通二叉查找树，平衡树的实现较为复杂，且维护平衡状态增加了插入、删除节点的开销。

2.平衡二叉树的插入

平衡二叉树的插入操作分为以下几步：

如果树为空，将要插入的节点作为根节点。
如果插入的元素小于当前节点的值，则在左子树上递归插入；如果插入的元素大于当前节点的值，则在右子树上递归插入。
在递归返回的过程中，检查当前节点是否失衡。如果当前节点失衡了，需要进行相应的旋转操作来恢复平衡。

对于平衡二叉树的旋转操作，有以下两种：

左旋转：对于节点 A，如果它的右子树比左子树高出 1 或者 2 层，那么进行左旋转。具体操作是，把 A 的右子节点作为新的根节点，A 变成新根节点的左子树，新根节点的原左子树变成 A 的新右子树。
右旋转：与左旋转类似，对于节点 A，如果它的左子树比右子树高出 1 或者 2 层，那么进行右旋转。具体操作是，把 A 的左子节点作为新的根节点，A 变成新根节点的右子树，新根节点的原右子树变成 A 的新左子树。

针对这一点，博主建议前往B站看一个五分钟的视频即可理解。

这里博主推荐一个视频，供大家参考：平衡二叉树的插入

3.平衡二叉树的删除

平衡二叉树的删除操作与普通二叉搜索树的删除操作相似，但需要在删除节点之后重新平衡树结构，以保证树的高度始终为 logn。

具体的删除操作可以分为以下三个步骤：

定位待删除节点，并进行删除。如果待删除节点是叶子节点，则直接删除；如果待删除节点只有一个子节点，则将其子节点替换为自己即可；如果待删除节点有两个子节点，则找到其右子树的最小节点（或者左子树的最大节点），将其值赋给当前节点，然后删除这个右子树的最小节点（或左子树的最大节点）。
从删除节点的父节点开始向上回溯，更新祖先节点的平衡因子。如果发现某个祖先节点的平衡因子的绝对值大于1，则需要进行旋转操作使其重新平衡。
对于任何因为删除而导致失衡的子树，都要进行旋转操作，以恢复平衡。

具体的旋转操作包括左旋、右旋、左右旋和右左旋四种情况，不同的情况需要选择不同的旋转方式来达到平衡。其中左旋将左子树上移一层，右旋将右子树上移一层，左右旋将左子树先右旋再上移，右左旋将右子树先左旋再上移。

三.红黑树（RBT）

1.定义与性质

红黑树是一种自平衡二叉搜索树，它保证在最坏情况下基本动态集合操作的时间复杂度为 O(log n)。

红黑树的性质如下：

每个节点要么是红色，要么是黑色。
根节点是黑色的。
每个叶子节点（NIL节点）是黑色的。
如果一个节点是红色的，则它的两个子节点都是黑色的。
对于任意一个节点，从该节点到其所有后代叶子节点的简单路径上，均包含相同数目的黑色节点（即黑高相等）。

其中，性质 4 是红黑树与普通二叉搜索树的区别所在。这个性质保证了红黑树的黑高不会超过红高的两倍，从而保证了树的平衡性。

口诀：“左右根、根叶黑、不红红、黑路同。”

2.RBT插入

红黑树是一种自平衡的二叉搜索树，它保证了在最坏情况下基本动态操作（插入、删除、查找）的时间复杂度为 O(log n)。

红黑树的插入操作可以分为以下几个步骤：

将新节点插入到红黑树中，使用二叉搜索树基本插入操作。
将新节点标记为红色。
进行颜色调整，确保不破坏红黑树的五个性质。
1. 父节点和子节点不能同时为红色。
2. 根节点必须为黑色。
3. 所有叶子节点都是黑色的空节点（NIL节点）。
4. 从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点。
5. 每个红色节点必须有两个黑色子节点。

颜色调整包括三种情况：

第一种情况：新节点的父节点是黑色。这种情况下没有任何问题，直接返回即可。

第二种情况：新节点的父节点是红色，而且新节点的叔叔节点也是红色。这种情况下需要进行重新着色，将父节点和叔叔节点都变为黑色，祖父节点变为红色，然后把祖父节点作为新节点继续进行调整。

第三种情况：新节点的父节点是红色，而且新节点的叔叔节点是黑色或者空节点。这种情况下需要进行旋转操作，将当前节点和其父节点左旋或右旋，然后重新着色。

通过以上步骤，就可以完成红黑树的插入操作，并保证了红黑树的五个性质。

数据结构与算法：树形查找