史上最全的二叉查找树（Black）设计

文章目录

1.树木的分类

根据树分支数量的限制，树结构可以分为两类：

根据树节点的顺序，树结构可以分为另外两类：

2.二叉树 2.1 AVL树

AVL树是一种自平衡二叉搜索树，其定义如下：

它的左子树和右子树都是AVL树。 左子树和右子树的高度差不能超过1。

AVL树中任意节点的两个子树之间的高度差最多为1，因此也称为高度平衡树。 为了保证平衡，AVL树中的每个节点都有一个平衡因子（用BF表示），它代表该节点左右子树的高度差，即左子树的高度减去右子树的高度。 高度的结果值。 AVL树中所有节点的BF值只能是-1、0、1。如果二叉树中某个节点的BF绝对值大于1，则该二叉树不是AVL树。

AVL树中节点的添加和删除可能需要多次旋转操作来重新平衡树结构，因此其添加和删除效率较低。 但平衡后，树的高度降低，搜索性能提高。

2.2 RB树

红黑树（简称RB Tree）是一种特殊的二叉搜索树。 同时，只需要部分平衡。 任何不平衡都会在三轮旋转内得到解决，因此与AVL相比，其添加和删除效率相对较高。 树越高，查询效率越低。

红黑树的每个节点都有一个存储位来表示该节点的颜色。 颜色为红色（Red）或黑色（Black）。 其特点如下：

每个节点要么是黑色，要么是红色。 根节点是黑色的。 每个叶节点都是黑色的。 如果一个节点是红色的，那么它的子节点必须是黑色的。 从一个节点到其左右子叶节点的所有路径都包含相同数量的黑色节点

就其特点而言，需要注意的是：

属性 (3) 中的叶节点是 NIL 或仅 null 的节点。 性质(5)保证没有一条路径的长度是任何其他路径的两倍。因此，红黑树是一种比较接近平衡二叉树。

红黑树的左转操作如下。 节点x的左转操作需要保证x有右子节点y。 过程就是以x作为旋转的顶部，将x向左移动到其左子节点的位置，将其右子节点y向上移动。 到 x 的原始位置

   /**
     * 对红黑树的节点(x)进行左旋转
     *
     * 左旋示意图(对节点x进行左旋)：
     *      px                              px
     *     /                               /
     *    x                               y
     *   /  \      --(左旋)----->        /  \              
     *  lx   y                          x   ry
     *     /   \                       / \
     *    ly   ry                     lx  ly
     *
     *
     */

红黑树的右手操作如下所示。 事实上，它与左手操作相反。

3.多树 3.1 B树

m阶B-Tree：m为一个节点的最大子节点数，请参考

m阶的B树是多路平衡搜索树，它要么是空树，要么是满足以下条件的树：

该节点最多有 m 个分支。 根节点至少有两个分支。 非根节点和非叶节点至少有 ceil(m/2) 个分支。 节点中的关键字按升序排序。 一个节点有n-1个关键字。 那么该节点有n个分支。 将关键词一一分开。 对于节点中的任意关键字，左分支的节点值小于该关键字，右分支的节点值大于该关键字叶子。 节点处于同一级别

3.2 B+树

B+树是B-树的变种，是应文件系统的需要而产生的。 m阶B+树和m阶B-树的区别是：

有n个子树节点包含n个关键字。 所有叶节点包含有关所有关键字的信息以及指向包含这些关键字的记录的指针，并且叶节点本身的大小根据关键字的大小而增加。 大序列链接的所有内部节点都可以视为索引部分，并且该节点只包含其子树（根节点）中最大（或最小）的关键字