树：平衡搜索树

发表于 2024-03-06 分类于算法

二叉搜索树、二叉平衡树（AVL、红黑树）、B树、B+树

1 二叉查找树

左子节点的值均小于根节点的值
右子节点的值均大于根节点的值二叉查找树是一种基于比较的数据结构，它的每个节点都有一个键值，而且左子节点的键值小于父节点的键值，右子节点的键值大于父节点的键值。这样的结构可以方便地进行查找、插入和删除操作，因为只需要比较节点的键值就可以确定目标节点的位置。但是，二叉查找树有一个很大的问题，就是它的形状取决于节点插入的顺序。如果节点是按照升序或降序的方式插入的，那么二叉查找树就会退化成一个线性结构，也就是一个链表。这样的情况下，二叉查找树的性能就会大大降低，时间复杂度就会从 O(logn) 变为 O(n)。

插入或者删除节点可能导致不平衡选择离插入(或删除)结点最近的不平衡结点(其平衡因子为±2)开始调整。

LL型: 新结点插在A 的左子树的左子树中导致不平衡;
RR型: 新结点插在A 的右子树的右子树中导致不平衡;
LR型: 新结点插在A 的左子树的右子树中导致不平衡;
RL型: 新结点插在A 的右子树的左子树中导致不平衡.

将A的左子节点向上提

红黑树是一种自平衡的二叉查找树树中每个节点包含5个属性：color、key、left、right、p

1.节点是红色或黑色。
2.根节点是黑色。
3.每个叶子节点都是黑色的空节点（NIL节点）。
4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

AVL树

B-树,这里的 B 表示 balance( 平衡的意思),B-树是一种多路自平衡的搜索树（B树是一颗多路平衡查找树）
它类似普通的平衡二叉树，不同的一点是B-树允许每个节点有更多的子节点。

L：每一个节点可以有的最多元素个数
L=3的树称为2-3-4 tree或者2-4tree
2-3-4指的是一个节点可能有2个孩子、3个孩子或者是4个孩子
L=2的树称为2-3 tree

2-3树和LLLRB树具有一一对应关系

B+树所有数据域存放在叶子节点

在B+树中，叶结点包含信息，所有非叶结点仅起索引作用，非叶子结点中的每个索引项只是包含了对应子树最大关键字和指向该孩子树的指针，不含有该关键字对应记录的存储地址。
在B+树中，终端结点包含全部关键字及相应记录的指针，即非终端结点出现过的关键字也会在这重复出现一次。而B树是不重复的。
B 树的所有节点既存放键(key) 也存放数据(data)，而 B+树只有叶子节点存放 key 和 data，其他内节点只存放 key。
B 树的叶子节点都是独立的;B+树的叶子节点有一条引用链指向与它相邻的叶子节点。
B 树的检索的过程相当于对范围内的每个节点的关键字做二分查找，可能还没有到达叶子节点，检索就结束了。而 B+树的检索效率就很稳定了，任何查找都是从根节点到叶子节点的过程，叶子节点的顺序检索很明显。
在 B 树中进行范围查询时，首先找到要查找的下限，然后对 B 树进行中序遍历，直到找到查找的上限；而 B+树的范围查询，只需要对链表进行遍历即可。

综上，B+树与 B 树相比，具备更少的 IO 次数、更稳定的查询效率和更适于范围查询这些优势。