数据布局之树体系：二叉树、均衡二叉树、红黑树、AVL树、B树、B+树、最小生 ...

概述

数据布局与算法

二叉树

其中每个结点都不能有多于两个子结点：

• 满二叉树：若设二叉树的高度为                                        h                                  h                     h，除第                                        h                                  h                     h层外，其它各层(1～h-1) 的结点数都达到最大个数，末了一层都是叶子结点，且叶子结点都是从左到右依次排布，结点总数为                                                   2                               n                                      −                            1                                  2^n-1                     2n−1
  
• 完全二叉树：全部叶子结点都在末了一层或倒数第二层，且末了一层的叶子结点在左边连续，倒数第二层的叶子结点在右边连续。和堆联系比较紧密
  
• 均衡二叉树：AVL树（区别于AVL算法），是一棵二叉排序树，且具有以下性子：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，且左右两个子树都是一棵均衡二叉树。
  

满二叉树

完全二叉树

关于二叉树的一些基础算法题，可参考面试+算法之二叉树(Java)。
二叉搜刮树

Binary Search Tree，BST，又称为二叉查找树、二叉排序树。
特点：任何一个结点的值都大于其左子树的全部结点的值，任何一个结点的值都小于其右子树的全部结点的值。
二叉搜刮树匀称时间复杂度可以认为是树的高度                                   O                         (                         h                         )                              O(h)                  O(h)。理论上，二叉搜刮树的查询、插入和删除操纵的时间复杂度均为                                   O                         (                         l                         o                         g                         N                         )                              O(logN)                  O(logN)。极端环境下，高度达到最大时，二叉搜刮树退化成链表，此时查询、插入和删除元素，时间复杂度变成                                   O                         (                         N                         )                              O(N)                  O(N)。
均衡二叉搜刮树

为了办理极端环境下二叉搜刮树退化成链表的问题，引入旋转操纵维护树的均衡。
Balanced Binary Search Tree（BBST，均衡二叉搜刮树），也叫Balanced Binary Tree（BBT，均衡二叉树），包罗AVL树和红黑树。
定义：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，而且左右两个子树都是一棵均衡二叉树。当时间复杂度为                                   O                         (                         l                         o                         g                         N                         )                              O(logN)                  O(logN)；
均衡，Balance，即当结点数量固定时，左右子树的高度越靠近，这棵二叉树越均衡，即高度越低。最理想的均衡就是完全二叉树/满二叉树，高度最小的二叉树。
遍历

二叉树的遍历有两种：按照结点遍历与层次遍历
结点遍历，一般递归实现：

• 前序遍历：遍历到一个结点后，马上输出该结点的值，并继续遍历其左右子树(根左右)
  
• 中序遍历：遍历一个结点后，将其暂存，遍历完左子树后，再输出该结点的值，然后遍历右子树(左根右)
  
• 后序遍历：遍历到一个结点后，将其暂存，遍历完左右子树后，再输出该结点的值(左右根)。
  

层次遍历

• 深度优先遍历：实际上就是上面的前序、中序和后序遍历，也就是尽大概去遍历二叉树的深度。
  
• 广度优先遍历：实际上就是一层一层的遍历，按照层次输出二叉树的各个结点。
  

二叉堆

二叉堆是一棵完全二叉树或是近似完全二叉树，还满足堆的特性：父结点的键值总是保持固定的序关系于任何一个子结点的键值，且每个结点的左子树和右子树都是一个二叉堆。常常被用来构造优先队列(Priority Queue),当你需要找到队列中最高优先级或者最低优先级的元素时，使用堆布局可以帮助你快速的定位元素。
布局性子：堆是一棵被完全填满的二叉树，有大概的例外是在底层，底层上的元素从左到右填入。如许的树称为完全二叉树。
分类

• 最大堆：父结点的键值总是大于或即是任何一个子结点的键值
  
• 最小堆：父结点的键值总是小于或即是任何一个子结点的键值
  

二叉堆可以用数组实现也可以用链表实现，观察上述的完全二叉树可以发现，是比较有规律的，以是完全可以使用一个数组而不需要使用链。下面用数组来表现上图所对应的堆结。
对于数组中恣意位置i的元素，其左儿子在位置2i上，右儿子在左儿子后的单位(2i+1)中，它的父亲则在位置[i/2上面]
红黑树

Red Black Tree，一种自均衡的二叉搜刮树（Self Balancing Binary Search Tree），又叫均衡二叉B树（Symmetric Binary B-tree）。
定义：红黑树是一种含有红黑结点，并能自均衡的二叉查找树。插入，删除，查找的复杂度都是                                   O                         (                         l                         o                         g                         N                         )                              O(logN)                  O(logN)
满足二叉搜刮树的性子外，还要满足如下性子：

• 每个结点要么是玄色，要么是红色
  
• 根结点是玄色
  
• 每个叶子结点（NIL）是玄色
  
• 每个红色结点的两个子结点肯定都是玄色
  
• 恣意一结点到每个叶子结点的路径都包罗数量雷同的黑结点
  
• 从根结点到叶子结点的最长路径不多于最短路径的长度的两倍
  

左倾红黑树，即红色结点都是父结点的左子树
右倾红黑树，
均衡

维持均衡的三种操纵：变色、左旋、右旋。
左旋指的是以某个结点作为支点（旋转结点），其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变。不考虑结点颜色，可以看到左旋只影响旋转结点和其右子树的布局，把右子树的结点往左子树移动。
右旋指的是以某个结点作为支点（旋转结点），其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变。不考虑结点颜色，可以看到右旋只影响旋转结点和其左子树的布局，把左子树的结点往右子树移动。
变色指的是结点的颜色由红变黑或由黑变红。
将左旋、右旋和变色结合起来，得到一套变更规则。
变色：如果当前结点的父结点和叔父结点是红色，那么：

• 把父结点和叔父结点变为玄色
  
• 把祖父结点变为红色
  
• 把指针定义到祖父结点
  

左旋：当前结点是右子树，且父结点是红色，叔父结点是玄色，对它的父结点左旋。
右旋：当前结点是左子树，且父结点是红色，叔父结点是玄色，那么：

• 把父结点变为玄色
  
• 把祖父结点变为红色
  
• 对祖父结点右旋
  

搜刮

由于红黑树本来就是均衡二叉搜刮树，而且搜刮也不会破坏树的均衡，以是搜刮算法也与均衡二叉搜刮树一致：

详细步骤：

• 从根结点开始检索，把根结点设置为当前结点
  
• 若当前结点为空，返回nil
  
• 若当前结点不为空，比较当前结点Key与搜刮Key的大小
  
• 若当前结点Key即是搜刮Key，则该Key是搜刮目标，返回当前结点
  
• 若当前结点Key大于搜刮Key，把当前结点的左子结点设置为当前结点，重复步骤2
  
• 若当前结点Key小于搜刮Key，把当前结点的右子结点设置为当前结点，重复步骤2
  

插入

删除

AA树

AA树是一种用于高效存储和检索有序数据的均衡树形布局，Arne Andersson教授于1993年在其论文Balanced Search Trees Made Simple中介绍，筹划的目标是减少红黑树考虑的差别环境。AA树的查找，插入和删除等操纵的时间复杂度都是                                   O                         (                         l                         o                         g                         N                         )                              O(logN)                  O(logN)。
AA树是红黑树的一种变体，与红黑树差别，AA树上的红色结点只能作为右子结点。AA树模仿2-3树，从而极大地简化维护操纵。红黑树的维护算法需要考虑七种差别的环境来精确均衡树。因为红色结点只能作为右子结点，AA树只需要考虑两种环境。
AVL树

不均衡的二叉树性能差，需要在插入、删除结点时保证其均衡，即减小树的高度，引入AVL树。AVL Tree，缩写取自G.M. Adelson-Velsky和E.M. Landis两位教授的名字。
AVL树，首先是一棵二叉搜刮树，每个结点的左右子树的高度之差的绝对值最多为1。这个高度差就叫均衡因子，Balance Factor，某结点的左右子树的高度差；显然，叶子结点的均衡因子是0。
AVL树的特点：

• 每个结点的均衡因子只大概是-1、0、1（如果绝对值超过1则是失衡）
  
• 每个结点的左右子树高度差不超过1
  
• 搜刮、插入、删除等操纵在匀称和最坏环境下的时间复杂度都是                                        O                            (                            l                            o                            g                            N                            )                                  O(logN)                     O(logN)
  

如上图是一个AVL树。如下图，往这颗树里插入一个结点T：

从T往上找，它的父结点是U，U的两颗子树的高度差为1，满足AVL树的规则。再往上查找，父结点是S，S的两颗子树的高度差为1，满足AVL树的均衡规则。再往上，S的父结点是V，V的两颗子树的高度差为2，不满足规则。此时，需要一个自均衡的过程。
维持树的均衡的一种大概的旋转过程如下，其中红色结点表现旋转的轴，经过两次旋转，再次变成AVL树：

由此可总结出AVL树的缺点：

• 插入、删除元素时维持均衡比较复杂且代价高，树越大，写操纵占比越高（操纵无外乎读或写，写包罗插入和删除），性能影响越大
  
• 需要存储每个结点的均衡因子，增加额外的内存斲丧
  
• 结点数很多时，不够直观（还能接收）
  

因为这些缺点，大家们又提出各种经过优化的均衡树。
AVL算法

AVL树使用的算法，即树的自均衡旋转方式，目标是用只管少的调解次数达到适度均衡。
多叉树

也叫多路树，用于搜刮场景的树，叫做多路搜刮树，简单分类：

• 平常多路搜刮树
  
• 均衡多路搜刮树
  

B树

磁盘IO操纵的服从很低。当在大量数据存储中，查询时不能一下子将全部数据加载到内存中，只能逐一加载磁盘页，每个磁盘页对应树的结点。造成大量磁盘IO操纵（最坏环境下为树的高度）。均衡二叉树由于树深度过大而造成磁盘IO读写过于频繁，进而导致服从低下。
为减少磁盘IO次数，必须降低树的深度：

• 每个结点存储多个元素
  
• 摒弃二叉树布局，采用多叉树
  

引出一个新的查找树布局：多路查找树，一颗均衡多路查找树，可使得数据的查找服从保证在                                   O                         (                         l                         o                         g                         N                         )                              O(logN)                  O(logN)时间复杂度。
Balanced Tree，一种均衡的多路搜刮（查找，排序）树，多用于文件系统、数据库的实现。有些资料也叫B-树（对应的英文是B-Tree），实际上是同一种数据布局。
B树的阶：全部结点的孩子结点的最大值。
一个                                   m                              m                  m阶（                                   m                         ≥                         2                              m≥2                  m≥2）的B树特点如下：

• 全部叶子结点都在同一层级；
  
• 每一个结点最多有                                        m                                  m                     m个子结点；
  
• 如果根结点不是叶子结点，则它至少有两个子结点；
  
• 有                                        k                                  k                     k个子结点的非叶子结点拥有                                        k                            −                            1                                  k−1                     k−1个键；
  
• 每一个非叶子结点（除根结点）最少有                                        ⌈                            m                            /                            2                            ⌉                                  ⌈m/2⌉                     ⌈m/2⌉个子结点，也就是中间结点最少有                                        ⌈                            m                            /                            2                            ⌉                                  ⌈m/2⌉                     ⌈m/2⌉个子结点。
  

两个取整：

• Ceiling：向上取整，指的是取比自己大的最小整数，用数学符号                                        ⌈                            ⌉                                  ⌈⌉                     ⌈⌉表现；
  
• Floor：向下取整，指的是取比自己小的最大整数，用数学符号                                        ⌊                            ⌋                                  ⌊⌋                     ⌊⌋表现。
  

假设一个结点存储的元素个数为                                   x                              x                  x，则如果这个结点是：

• 根结点：                                        1                            ≤                            x                            ≤                            m                            −                            1                                  1≤x≤m-1                     1≤x≤m−1
  
• 非根结点：                                        ⌈                            m                            /                            2                            ⌉                            −                            1                            ≤                            x                            ≤                            m                            −                            1                                  ⌈m/2⌉-1≤x≤m-1                     ⌈m/2⌉−1≤x≤m−1
  

如果有子结点，子结点个数为                                   y                         =                         x                         +                         1                              y=x+1                  y=x+1，则如果这个结点是：

• 根结点：                                        2                            ≤                            y                            ≤                            m                                  2≤y≤m                     2≤y≤m
  
• 非根结点：                                        ⌈                            m                            /                            2                            ⌉                            ≤                            y                            ≤                            m                                  ⌈m/2⌉≤y≤m                     ⌈m/2⌉≤y≤m
  

m取值差别时：

• m=3，叶子结点个数                                        2                            ≤                            y                            ≤                            3                                  2≤y≤3                     2≤y≤3，可称为                                        (                            2                            ,                            3                            )                                  (2,3)                     (2,3)树、2-3树、3阶B树。
  
• m=4，叶子结点个数                                        2                            ≤                            y                            ≤                            4                                  2≤y≤4                     2≤y≤4，可称为                                        (                            2                            ,                            4                            )                                  (2,4)                     (2,4)树、2-3-4树、4阶B树。
  
• m=5，叶子结点个数                                        3                            ≤                            y                            ≤                            5                                  3≤y≤5                     3≤y≤5，可称为                                        (                            3                            ,                            5                            )                                  (3,5)                     (3,5)树、3-4-5树、5阶B树。
  

同样地，另有2-3-4-5-6树、3-4-5-6树，无穷无尽，统一都叫B树。
结论：

• B树和二叉搜刮树，在逻辑上是等价的
  
• 多代结点归并，可以得到一个超等结点，且n代归并的超等结点，最多拥有                                                   2                               n                                            2^n                     2n个子结点（至少是                                                   2                               n                                            2^n                     2n阶B树）
  

应用场景：

• B树重要用于文件系统及部分数据库索引，如MongoDB。而大部分关系数据库则使用B+树做索引，如MySQL；
  
• 从查找服从考虑一般要求B树的阶数                                        m                            >                            =                            3                                  m>=3                     m>=3；
  
• B树算法的实行时间重要由读、写磁盘的次数来决定，故一次I/O操纵应读写尽大概多的信息。因此B-树的结点规模一般以一个磁盘页为单位。一个结点包罗的关键字及其孩子个数取决于磁盘页的大小。
  

操纵

B树的操纵，无非查询、插入、删除三种。
查询
插入
删除
2-3树

2-3树，是指每个具有子结点的结点（内部结点，Internal Node），要么有2个子结点和1个数据元素，要么有3个子结点和2个数据元素的自均衡的树，全部叶子结点都具有雷同的高度。即，2-3树的非叶子结点都具有两或三个分支。
空间复杂度为                                   O                         (                         N                         )                              O(N)                  O(N)，搜刮、插入、删除等操纵的时间复杂度都是                                   O                         (                         l                         o                         g                         N                         )                              O(logN)                  O(logN)。
2-3树把数据存储在叫做元素的单独单位中，元素组合成结点。有2结点和3结点两种。
2结点：包罗1个元素和2个子结点

3结点：包罗2个元素和3个子结点

2–3树和AA树是等距同构的，意味着它们是同一种数据布局。对于每个2–3树，都至少存在1种AA树和它的元素排列是雷同的。2–3树是均衡树，意味着右边，左边，中间的子树的元素数量都是雷同或靠近的。
一棵树T为2–3树的三种环境：

• T为空：即T不包罗任何结点；
  
• T为拥有数据元素a的2结点。若T的左子结点为L、右子结点为R，则：
  
  
  
  • L和R是等高的2–3树；
    
  • a大于L中的全部数据元素；
    
  • a小于即是R中的全部数据元素。
    
  
  
• T为拥有数据元素a和b的3结点，且                                        a                            <                            b                                  a<b                     a<b。若T的左子结点为L、中子结点为M、右子结点为R，则：
  
  
  
  • L、M、和R是等高的2–3树；
    
  • a大于L中的全部数据元素，且小于即是M中的全部数据元素；
    
  • b大于M中的全部数据元素，且小于即是R中的全部数据元素。
    
  
  

上面这颗树就是一个2-3树。此时，如果要插入一个元素K，它会先找到I J这个结点；插入元素K，形成暂时结点I J K，不符合2-3树的规则。
差别于AVL树，不满足树的规则时，需要对树进行旋转，2-3树则需要进行分裂操纵。
J往上移，F H这个结点变成F H J，也不符合2-3树的规则。继续上移H，根结点变为D H。同时，上移的过程中，子结点也要相应的分裂，过程大致如下：

图片来自于红黑树。
在上面自均衡的过程中，出现一种结点，它具有四个子结点和三个数据元素，即4结点。如果4结点允许存在，则引出另一种树：2-3-4树。
另外，B树的均衡过程叫分裂，相比于AVL树的旋转，更直观易懂，服从更高。
2-3-4树

与2-3树雷同，多了一种4结点：包罗3个元素和4个子结点。

2-3-4树是有序的：每个元素必须大于或即是它左边的和它的左子树中的任何其他元素。每个子结点因此成为由它的左和右元素界定的一个区间。
2-3-4树的空间复杂度为                                   O                         (                         N                         )                              O(N)                  O(N)，搜刮、插入、删除等操纵的时间复杂度都是                                   O                         (                         l                         o                         g                         N                         )                              O(logN)                  O(logN)。
2-3-4树在多数编程语言中实现起来相对困难，因为在树上的操纵涉及大量特殊环境。红黑树实现起来更简单一些，可用它来替代。
2-3-4树是红黑树的一种等同，这意味着它们是等价的数据布局。对于每个2-3-4树，都存在着至少一个数据元素是雷同序次的红黑树。在2-3-4树上的插入和删除操纵也等价于在红黑树中的颜色翻转和旋转。这使得它成为理解红黑树背后逻辑的紧张工具。
B+树

B+树是B树的变种，但差别资料（以及实现里）中B+树的定义各有差别，其差异在于结点中关键字个数和孩子结点个数。
B+树的特点：

• 每个结点中子结点的个数不能超过N，也不能小于                                        N                            /                            2                                  N/2                     N/2（不然会造成页分裂或页归并）
  
• 根结点的子结点个数可以不超过                                        m                            /                            2                                  m/2                     m/2
  
• m叉树只存储索引，并不真正存储数据，只有末了一行的叶子结点存储行数据
  
• 通过链表将叶子结点串联在一起，方便按区间查找
  

这种在叶结点存放一整行记录的索引被称为聚簇索引，其他的就称为非聚簇索引。
一个                                   m                              m                  m阶的B+树具有如下几个特性：

• 有                                        k                                  k                     k个子树的中间结点包罗有k个元素（B树中是                                        k                            −                            1                                  k-1                     k−1个元素），每个元素不生存数据，只用来索引，全部数据都生存在叶子结点；
  
• 全部的叶子结点中包罗全部元素的信息，及指向含这些元素记录的指针，且叶子结点自己依关键字的大小自小而大顺序链接；
  
• 全部的中间结点元素都同时存在于子结点，在子结点元素中是最大（或最小）元素
  

B+树通常有两个指针，一个指向根结点，另一个指向关键字最小的叶子结点。对于B+树进行查找有两种算法：一种是从最小关键字起顺序查找，另一种是从根结点开始，进行随机查找。
对比B树

和B树一样，雷同于二叉查找树。起始于根结点，自顶向下遍历树，选择其分离值在要查找值的恣意一边的子指针。在结点内部典型的使用是二分查找来确定这个位置。
区别：

• B树必须用中序遍历的方法按序扫库，而B+树直接从叶子结点逐个扫一遍就完；
  
• B+树支持区间查询(Range Query)，而B树不支持。数据库选用B+树的最重要原因；
  
• B+树中间结点没有卫星数据（索引元素所指向的数据记录），只有索引，而B树每个结点中的每个关键字都有卫星数据；即，同样大小磁盘页可以容纳更多结点元素，数据量雷同时，B+树更加矮胖，IO操纵更少
  
• 因卫星数据的差别，导致查询过程也差别；B树的查找只需找到匹配元素即可，最好环境下查找到根结点，最坏环境下查找到叶子结点，性能很不稳定；B+树每次必须查找到叶子结点，性能稳定
  
• 在范围查询方面，B+树的上风更加明显
  B树的范围查找需要不绝依靠中序遍历。首先二分查找到范围下限，再不绝通过中序遍历，直到查找到范围的上限即可。整个过程比较耗时。B+树的范围查找则简单很多。首先通过二分查找，找到范围下限，然后通过叶子结点的链表顺序遍历，直至找到上限即可，整个过程更简单，服从也更高。
  

面试题

• 为啥索引常用B+树作为底层的数据布局？
  
• 除了B+树索引，另有什么索引？
  
• 为啥保举自增ID作为主键，自建主键不行吗？
  
• 什么是页分裂，页归并？
  
• 怎么根据索引查找行记录？
  

B*树

B+树的变体，区别：

• 在B+树的非根和非叶子结点再增加指向兄弟的指针；
  
• B*树定义非叶子结点关键字个数至少为                                        (                            2                            /                            3                            )                            ∗                            M                                  (2/3)*M                     (2/3)∗M，即块的最低使用率为2/3，优于B+树的1/2；
  
• 分裂
  
  
  
  • B+树的分裂：当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，末了在父结点中增加新结点的指针；B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，以是它不需要指向兄弟的指针；
    
  • B*树的分裂：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，末了修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变）；如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，末了在父结点增加新结点的指针；
    
  
  
• B*树分配新结点的概率比B+树要低，空间使用率更高；
  

最小天生树

Minimum Spanning Tree，MST，最小权重天生树，是一副连通加权无向图中一棵权值最小的天生树。
哈夫曼树

Huffman Tree，最优二叉树，是一种带权路径长度最短的二叉树。树的带权路径长度，就是树中全部的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的路径长度是从树根到每一结点的路径长度之和，记为                                   W                         P                         L                         =                         (                         W                         1                         ∗                         L                         1                         +                         W                         2                         ∗                         L                         2                         +                         W                         3                         ∗                         L                         3                         +                         .                         .                         .                         +                         W                         n                         ∗                         L                         n                         )                              WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln)                  WPL=(W1∗L1+W2∗L2+W3∗L3+...+Wn∗Ln)，                                   N                              N                  N个权值                                   W                         i                         (                         i                         =                         1                         ,                         2                         ,                         .                         .                         .                         ,                         n                         )                              Wi(i=1,2,...,n)                  Wi(i=1,2,...,n)构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为                                   L                         i                         (                         i                         =                         1                         ,                         2                         ,                         .                         .                         .                         ,                         n                         )                              Li(i=1,2,...,n)                  Li(i=1,2,...,n)。可证实霍夫曼树的WPL是最小的。
哈夫曼编码就是哈夫曼树的应用。
决策树

Decision Tree，也叫判断树，是一个雷同于流程图的树布局：其中，每个内部结点表如今一个属性上的测试，每个分支代表一个属性输出，而每个树叶结点代表类或类分布。树的最顶层是根结点。
构造决策树的过程叫做决策树算法，常用于呆板学习中的分类。
优点：直观，便于理解，小规模数据集有效
缺点：

• 处置处罚连续变量不好
  
• 类别较多时，错误增加的比较快
  

Trie树与Radix树

参考Trie树、Radix树。
LSM树

Log-Structured Merge-Tree。适用于写入密集型的数据库系统，如LevelDB和RocksDB。
上风：提供非常高的写入性能和批处置处罚能力，支持对数据的压缩。
劣势：因为涉及多层查找和归并操纵，读取性能不如其他数据布局。
后缀树

Suffix Tree，用于字符串搜刮、生物信息学等范畴。
上风：可以快速办理多种字符串相干的问题，如查找子字符串出现的位置、查找最长重复子字符串等。
劣势：空间占用较大，构建过程复杂且耗时。
R树

R-Tree，适用于空间数据库中索引多维空间数据，如地理信息系统(GIS, Geographic Information System)。
上风：支持多维范围查询和最邻近搜刮，适合存储空间数据。
劣势：更新本钱高，查询性能依靠于数据分布。
对比

图片来源：https://bytebytego.com/
参考

• 全面分析二叉树
  
• 红黑树
  
• 面试必知的红黑树
  
• 面试必知B+树
  
• 最小天生树
  
• 红黑树
  
• AA树
  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。