算法：树搜索

站内链接:

二叉树

定义和图解

二叉查找树（二叉排序树）是先对待查找的数据进行生成树，确保树的左分支的值小于右分支的值，然后在就行和每个节点的父节点比较大小，查找最适合的范围。

1）若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
2）若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
3）任意节点的左、右子树也分别为二叉查找树。

下面是掘金文章上一个简单的二叉树查找图解示例：

使用场景

二叉树在一般情况下可以极大的提高搜索效率，但它本身有如下缺点，从而导致搜索效率降低：

a. 不平衡性：如果插入的数据是有序的或者近似有序的，二叉查找树可能会退化成一个链表，导致树的高度接近 n，使得查找、插入和删除的平均时间复杂度变为 O(n)，失去了平衡查找树的优势。
b. 对有重复数据的处理：二叉查找树通常只能存储唯一的键值，对于有重复数据的情况，需要进行额外的处理。一种处理方式是在节点中存储计数值，但这会增加空间复杂度。另一种方式是使用平衡查找树的变种，如红黑树或 AVL 树，来处理重复数据。
c. 效率不稳定：二叉查找树的性能取决于树的形状，如果出现极端情况下的不平衡，例如最小或最大值的频繁插入或删除，树的形状将导致查找、插入和删除操作的效率下降。
d. 不支持范围查询：二叉查找树的查询操作只能找到等于给定键的节点，无法高效地支持范围查询，即查找在某个范围内的节点。
e. 对输入数据敏感：二叉查找树对于输入数据的顺序敏感，如果数据的顺序不是随机的或者近似有序的，可能导致树的不平衡，进而影响性能。

为了解决这些问题，基于二叉查找树进行优化，进而可以得到其他的树表查找算法，如平衡树、红黑树等高效算法

平衡二叉树

组成要素

平衡二叉树包括如下的组成要素：

根节点：平衡二叉树的顶层节点，用于表示树的起始位置。
节点：树中的每个元素都表示一个节点，每个节点可以存储一个键值和相关的数据。
左子节点：位于当前节点左侧的子节点，其键值小于当前节点的键值。
右子节点：位于当前节点右侧的子节点，其键值大于当前节点的键值。
父节点：当前节点的上一级节点，用于连接当前节点与其子节点。
平衡因子：用于衡量节点的平衡状态，表示当前节点的左子树高度与右子树高度之差。
平衡调整：通过旋转操作来调整树的结构，以保持树的平衡性。
高度：节点到叶子节点的最长路径（边数）称为节点的高度，树的高度是根节点的高度。

其中平衡因子是指每个节点的左子树高度与右子树高度之差。平衡因子用于衡量节点的平衡状态，每个节点的平衡因子可以取三个值：-1、0、1，其含义如下：

平衡因子为-1：表示该节点的左子树比右子树高度低 1。
平衡因子为 0：表示该节点的左子树和右子树高度相等。
平衡因子为 1：表示该节点的左子树比右子树高度高 1。

通过维护每个节点的平衡因子，可以判断树的平衡状态，并在插入或删除节点时进行相应的旋转操作来调整树的结构，以保持平衡，后面常见的 AVL 树和红黑树都是通过使用平衡因子来判断节点的平衡状态，并通过旋转操作来调整树的结构。

最小失衡子树

最小失衡子树（Minimum Imbalance Subtree）是指在一个平衡二叉树中，具有最小平衡因子绝对值的子树。也就是说，最小失衡子树是树中平衡因子绝对值最小的子树。当平衡二叉树的某个节点的平衡因子绝对值超过 1 时，说明该节点所在的子树失去平衡。此时需要对该子树进行平衡调整，使其重新达到平衡状态。

为了保证调整的高效性，我们需要找到具有最小平衡因子绝对值的子树作为调整的目标，此即最小失衡子树。例如

插入：在新插入的结点向上查找，以第一个平衡因子的绝对值超过 1 的结点为根的子树称为最小不平衡子树
删除：从被删除节点的父节点开始向上查找，以第一个平衡因子的绝对值超过 1 的结点为根的子树称为最小不平衡子树

通过对最小失衡子树进行旋转等操作，可以使其重新平衡，并逐级向上调整，最终使整棵树恢复平衡。

定义和图解

AVL平衡二叉查找树有如下两个特质：

可以是空树
任何一个结点的左子树与右子树都是平衡二叉树，并且高度之差的绝对值不超过 1

其中平衡因子就是用来判断并解决高度差的绝对值不超过 1 的判断标准。那么我们怎么将一个二叉查找树变为平衡二叉树呢？

插入一个新节点后的失衡和调整
删除一个新节点后的失衡和调整

另外，一个二叉树不平衡也分为不同的情况（重要），我们使用两个字母来表示平衡因子，并用此种表达式方式来表述这些情况，其格式为两个字母[第一个字母表示最小不平衡子树根结点的平衡因子][第二个字母表示最小不平衡子树较高子树的根结点的平衡因子]

对三种不平衡树（L 表示左子树较高、R 表示右子树较高、E 表示左右子树等高）：LL，LE，

2-3 查找树

红黑树

B 树

2-3 查找树是一种自平衡的树型数据结构（B 树的一种特殊情况，看成 B 树的简化版本）。2-3 查找树的结构使得它能够高效地支持插入、删除和查找操作，并保持树的平衡。在插入或删除操作时，树会根据一定的规则进行调整，以保持平衡性。通过保持平衡，2-3 查找树能够保证在最坏情况下，查找操作的时间复杂度为 O(log n)，其中 n 是树中节点的数量。

那么，为何 2-3 查找树相比二叉查找查找效率更高呢？这实际上是一种基于平衡查找树的思想，从而解决普通二叉树可能存在的不平衡和性能下降的问题。通过引入多键节点和自动平衡的机制，2-3 树在数据结构中取得了较好的性能和平衡性，进一步推动了平衡查找树的发展。其优点如下：