一文搞懂搜索树 - 二叉搜索树(排序树) AVL树 多路搜索树(B树) (2,4)树 伸展树 B+树 B*树 R树 性能分析

文章较长,建议参照目录

参考：

书 :《数据结构与算法–Python语言实现》(原名:《Data Structures and Algorithms in Python》)

• 有序映射 - 同时提供有序序列和映射的功能

  • 有序序列

    • le() / lt() / ge() / gt()
    • max() / min()
    • indexOf()
    • range()
    • iter()
    • reverse()
    • 可以利用有序序列对无序元素进行排序

  • 映射

    • map[k] - 查找
    • map[k]=v - 添加&修改
    • del map[k]
    • items()/keys()/values()

  • 其它方法

    • len()

  • 有几种方式可以提供有序映射,有序数组查询快但修改慢,有序链表查询慢但修改快.搜索树以一种特殊的组织方式,对前两者搜索和修改的性能进行了折中,使搜索和修改拥有了相同的性能

    下表为几种有序映射数据结构的运行时间上界

• 这一章的搜索树都做同一件事 ---- 有效实现有序映射(sorted map).

• 有序映射是指内部元素按照某种顺序保存并提供有序访问的映射

几种有序映射数据结构的对比

根据场景进行选择

线性结构	搜索	添加删除 (先搜索)	存储空间
有序数组	O(logn)	O(n+logn)	最小
有序链表	O(n)	O(n)	小
树结构	树结构都接近logn	树结构都接近logn		旋转	向上分裂
二叉搜索树	慢 - 取决于数据随机程度	慢 - 取决于数据随机程度	小	○	○
AVL树	快	慢	大	√	○
多路搜索树	快	慢	大	○	√
伸展树	慢	慢	小	√	○
红黑树	慢	快	大	√	√

二叉搜索(排序)树

• 二叉搜索树的性质
  • 左子树 < 父结点 < 右子树
  • 中序遍历,元素是有序的
• 这一节的两个关键方法 after(x) search(x),是后面各种有序映射结构的基础
• 有序映射的first()和last()方法可以通过不断地调用left()和right()在O(h)的时间内实现,这里省略.

after(x)

当知道一个元素x的位置之后,如何找到它按顺序的下一个元素y的位置

首先y不可能在x的左子树中

1. 如果x有右子树，则y在右子树中

   1. 进入右子树
   2. 一直向左走到头找到y

2. 如果x没有右子树,则y在x的祖先之中

   1. 记录当前位置now(开始为x)和当前位置的父位置parent(now)
   2. 不断向上迭代now和parent(now),直到遇到parent(now)在now右上的情形,则y=parent(now)
      

该算法依赖了下面三个"树"的方法,通过结点中存放的指针进行查找,这里省略它们的具体实现.

可以看出,通过连续使用这三个方法来实现的before(node)和after(node)方法,时间复杂度为O(n).

其运行时间只受到树的高度h的限制.既最坏的情况下运行时间为O(h).

但连续调用before(node)和after(node)摊销的运行时间为O(1),因为要找结点的位置在大多数情况下都是相邻的.

• parent(node) - O(1)
• left_child(node) - O(1)
• right_child(node) - O(1)

另一个对称的方法before()可以使用对称的算法,这里省略.

search(x)

二叉搜索树的搜索算法十分简单

以根节点为now开始递归

1. now = x,搜索成功
2. now < x,now=right(now)
3. now > x,now=left(now)
4. left(now)==null / right(now)==null,搜索失败

最坏运行时间O(h)

插入 - map(key)=val

普通的插入方法很简单,只需要执行类似上面的search()方法

• 如果key搜索成功,则直接赋值
• 如果key搜索失败,在失败的位置插入新节点key

删除 - del map[key]

删除方法要比插入复杂一些,分成三种情况

• key没有子节点 -> 直接删除
• key只有一个子节点(左或右) -> 直接用子节点替换它
• key有两个子结点
  • 找到r=before(key) - 既映射中key的前一个键的位置.由于key有孩子,则r在key左子树的最右边的位置
  • 直接使用r替换key - 由于r是key的前一个键,所以key右子树的节点都比r大,左子树的节点都比r小
  • 因为r不可能再有右子树,所以直接用r的左子树替换r的位置

分析

• h为树的最大高度,n为元素(结点)数量

• 搜索树的所有方法都要先进行时间复杂度为O(h)的搜索,这个无法优化,所以我们只能尽可能地优化和保持树的结构,尽可能地降低h.最好的结构为完全二叉树.h=logn,时间复杂度是O(logn)

• 普通的二叉搜索树最大问题就在于树的结构可能因为后续的修改操作而变得不平衡.

  最差的情况是形成了一条链,这时各方法的性能就和线性表的性能相同了.此时h=n,时间复杂度就从对数O(logn)变为了线性O(n).但如果插入的元素是真正随机的,通过概率可以证明树的形状还是会自动保持大体平衡的.在不能保证元素的随机性的场景下,才需要用到本章后面的其它排序树

  本章节后面介绍的所有树,都通过维护树的平衡结构,以保证各个操作的效率

操作	最坏时间
查找 - 添加 - 删除	O(h)
找第一个/最后一个/最小/最大	O(h)
找索引位置	O(h)
找前一个/后一个	O(h)
按范围找	O(h+查找个数)
迭代 - 翻转	O(n)

旋转 & 重组

这一章没有讲具体的搜索树结构,而是关注当树不平衡时如何通过旋转使其恢复平衡.

何时进行旋转在后面几章会讲到.

旋转 _rotate()

• 目的是缩短a上的路径长度
• 单个旋转操作占用O(1)的运行时间
• 旋转不影响对二叉树中序遍历的结果
• 一种情况下的步骤(上图的情况)
  • 把根结点由**c设置为b**
  • 把**b的右子树放到c的左子树**
  • 把**c放到b的右子树**

重组 _restructure()

• 重组就是连续的旋转
• 将多个旋转合并以获得更广泛的平衡
• 需要两次旋转的情况,通过一次旋转转换为需要一次旋转的情况

AVL树

• AVL树在普通搜索树的基础上,加入了简单的平衡策略 - 树中每一个位置P,其孩子的高度最多相差1
• AVL树通过旋转维持树的平衡结构
• 每次因为结点更新而使树的某些位置不平衡时,需要旋转使它恢复平衡.
• 要对比某个位置子树的高度,就需要给每个结点额外增加一个变量记录子树的最大高度
• 特性
  • 子树还是AVL树
  • 高度为O(logn)

插入

• 当插入结点p后,唯一可能会变得不平衡的位置是p的祖先
• 只需要重组从p开始到根节点遇到的第一个不平衡位置,就可以使树恢复平衡
• 插入并重组之后,子树的高度和插入之前一样
  

删除

• 当删除一个结点p,其祖先路径上可能会出现不平衡位置
• 遇到第一个不平衡位置,重组使该位置恢复平衡
• 第一个不平衡位置恢复平衡后,继续向上还可能出现新的不平衡位置,继续重组
• 最多会重组O(logn)次
• 在删除结点后进行重组前,记录当前不平衡位置的最大高度,如果重组后最大高度没有变化,则不需要继续向上进行平衡检查

分析

• AVL树和普通的搜索树相比,基本映射操作的运行时间变得更加稳定,将最坏情况从O(n)控制在了O(logn).但与此同时,在更新结点操作时要花费额外添加-O(1) 删除-O(logn)的时间对树进行重组维护平衡
• 添加花费的时间
  • 从上向下查找插入位置 - O(logn)
  • 插入后进行一次旋转 - O(1)
• 删除花费的时间
  • 从上向下查找插入位置 - O(logn)
  • 插入后进行1-logn次旋转 - O(logn)

操作	最坏时间
查找 - 添加 - 删除	O(logn)
找第一个/最后一个/最小/最大	O(logn)
找索引位置	O(logn)
找前一个/后一个	O(logn)
按范围找	O(logn+查找个数)
迭代 - 翻转	O(n)

多路搜索树

• 也叫做B树 B-树 B-tree

• 多路搜索树通过向上分裂保证树的平衡结构

• 多路搜索树和二叉搜索树比,每个结点内部可以存储多个key-value.从总体上看,树的高度变低了,但节点内确定搜索路径的操作从二选一变成了多选一.也就是说,将一部分路径的选择过程移动到了结点之内

• 多路搜索树的首要效率目标是保持高度尽可能小,即维持树的平衡.通过维护树的两个属性来实现

  • 大小属性 - 每个结点最多有m个孩子
  • 深度属性 - 所有外部结点都在同一层

• 节点

  • 内部节点
    • 内部的数据结构 - 通常只有常数(少数)几个键值对,所以选什么结构区别不大,运行时间都是O(1).可以使用:
      • 这一章都在讲的有序映射
      • 有序数组
    • 有m个元素,有m+1个孩子
    • 每一个内部结点都一定有左右孩子,不像二叉搜索树的左右孩子可能为空
  • 外部结点
    • 不存储数据,仅作为占位符,没有其它作用
    • 一颗有n个元素的树,有n+1个外部节点

• 搜索的过程和二叉搜索树相似,效率为O(h).因多路搜索树保证了h=logn,所以搜索的效率为O(logn)

(2,4)树

• (2,4)树也叫2-3-4树,是多路搜索树的一个特殊情况.节点内有1-3个元素,有2-4个孩子

• (2,4)树与红黑树有着密切的联系,是红黑树的基础

插入 - 向上溢出

向上溢出保证了树的深度属性,因为溢出会一直向上传递,不会增加高度.只有到溢出到了树的根部,才会让整棵树所有的结点深度都+1

1. 直接向要插入的位置插入要添加的元素,并增加需要的外部结点
   

2. 进行分裂
   

3. 如果分裂生成的新结点造成上层结点新的溢出,则继续分裂上层结点
   

删除 - 向下溢出

1. 先执行二叉搜索树的删除步骤,会转换为删除外部结点的情况,删除对应的外部结点

   1. key没有子节点 -> 直接删除

   2. key只有一个子节点(左或右) -> 直接用子节点替换它

   3. key有两个子结点

• 找到r=before(key) - 既映射中key的前一个键的位置.由于key有孩子,则r在key左子树的最右边的位置
  - 直接使用r替换key - 由于r是key的前一个键,所以key右子树的节点都比r大,左子树的节点都比r小
  - 因为r不可能再有右子树,所以直接用r的左子树替换r的位置

2. 第一步中的前两种情况,会直接导致最底层结点产生溢出

   多路搜索树的每个结点一定都有左右孩子,所以第一步的情况三中,删除一个非底层结点的元素p,会用它在有序映射中的前一个元素b进行替换,而b一定在一个底层的结点.所以替换后还是会导致底层结点的溢出

   所以,无论删除任何一个元素,最后都会转换为底层结点的溢出.也就是说只需要去处理这种情况就够了.

   底层结点p溢出分成两种情况处理(多路搜索树的性质决定p至少有一个兄弟结点q) :

   1. 借 : q内有2-3个元素,则向q"借"一个元素
      

   2. 融合 : p只有q一个兄弟,或q内只有一个元素,向父亲"借"一个元素
      

   3. 上一步向父亲借可能进而导致上层出现新的下溢,继续向上按方法1/2处理
      

性能分析

• (2,4)树各操作性能和AVL树基本相同
  • 搜索/插入/删除结点需要访问O(h)个结点,h=logn.这里访问的O(h)个结点,包括从上向下的查找和从下向上的分裂 借 融合.也就是说,(2,4)树在操作完成后,和AVL树一样需要花费O(logn)的时间对树的平衡进行维护
  • 添加时的"分裂",删除时的"借"和"融合"操作,都花费O(1)的时间
• 添加花费的时间 - O(logn)
  • 从上向下查找插入位置 - O(logn)
  • 插入后进行最多logn次向上分裂 - O(logn)
• 删除花费的时间 - O(logn)
  • 从上向下查找删除位置 - O(logn)
  • 插入后进行最多logn次向下溢出的处理 - O(logn)

红黑树

参考视频教程:

https://www.bilibili.com/video/BV1HJ411z7ZU?p=100

• 红黑树本质上是变形后的(2,4)树

  • 任意红黑树都对应一棵(2,4)树,但红黑树的操作并不和(2,4)树完全相同.它同时使用AVL树的旋转和(2,4)树的向上分裂来维护平衡.可以这样操作是因为红黑树的实际形态是AVL树一样的二叉树,所以可以方便地旋转.而它的逻辑形态是(2,4)树一样的多结点树,所以可以向上分裂.

  • 红黑树的每一个黑色结点连同它的红色孩子(如果有的话),对应(2,4)树的一个结点.这也是所有路径黑色结点数量相同的原因.

    红黑树将(2,4)树的 有1-3个元素的结点 转换为 1个黑色结点+1-2个红色结点
    

  • (2,4)树的2 3 4结点分别对应了红黑树的四种情况.在插入和删除的时候,也要针对这四种情况做处理
    
    

• 红黑树弥补了AVL树和(2,4)树在添加和删除元素后还需要最多logn次的结构变化来维护平衡的缺点(但依旧可能需要logn次染色)

  它牺牲了一部分平衡性(搜索的速度),节省了添加和删除元素后对树维护的开销

• 红黑树有几条基本性质,目的是为了保证和(2,4)树结构上的完全等价

  在进行二叉树常规的插入和删除操作之后,还需要进行维护红黑树性质的操作

  • 节点分为红色和黑色
  • 根是黑色
  • 黑色结点的孩子可能是黑色或红色
  • 红色结点的孩子只能是红色,也就是说红色结点不可能连续出现
  • 所有路径黑色结点数量相同

• 树的高度 - 决定了查找 添加 删除操作的效率

  (效率为O(1)的添加和删除操作前也会先查找,所以也受高度影响)

  • 最小高度 - log(n) - 树中只有黑色结点
  • 最大高度 - 2log(n) - 最长路径上每个黑色结点都有一个红色孩子
  • 宽松的平衡 - 只保证没有任何一条路径的长度会大于另一条路径的两倍

• 下图中不断在红黑树的一侧添加更小的元素,能发现树的一部分始终会在一定的限度内(一个红色结点的高度)增高,而不会完全失衡.

#实验网站地址:http://520it.com/binarytrees/
#添加元素的顺序:
140,139,138,137,136,135,134,133,132,131,130,129,128,127,126,125,124,123,122,121,120,119,118,117,116,115,114,113,112,111,110,109,108,107,106,105,104,103,102,101,100,99,98,97,96,95,94,93,92,91,90,89,88,87,86,85,84,83,82,81,80,79,78,77,76,75,74,73,72,71,70,69,68,67,66,65,64,63,62,61,60,59,58,57,56,55,54,53,52,51,50,49,48,47,46,45,44,43,42,41,40,39,38,37,36,35,34,33,32,31,30,29,28,27,26,25,24,23,22,21,20,19,18,17,16,15,14,13,12,11

搜索 - 与标准二叉树的搜索相同

插入

1. 按照查找的规则找到需要插入的位置
2. 将要插入的元素(结点)染成红色后直接插入(因为如果直接插入成功,一定是红色的.黑色结点只通过后期调整染色才能得到)
3. 插入后按照父节点和叔结点的状态分成三种情况
   1. 父节点是黑色 - 插入即可 - 插入位置本就应为红色,且插入后无需分裂
   2. 父结点是红色,叔结点不为红色 - 需要调整(旋转)
      • 插入红色结点后,不符合(2,4)树中结点内有三个元素时对应红黑树的染色规则
      • 需要对插入结点p,p的父亲,p的祖父进行旋转并重新染色
   3. 父结点是红色,叔结点为红色 - 需要向上分裂
      • 插入红色结点后,不符合(2,4)树结点内最多只能有3个元素的规则,产生了溢出
      • 需要对插入结点p,p的父亲,p的叔叔,p的祖父,四个结点先进行分裂
      • 分裂的过程中需要按规则对结点进行重新染色
      • 将分裂后产生的树的根结点染成红色,当作新结点执行插入操作,插入这几个元素原先的位置
      • 这时如果产生新的溢出,则继续向上分裂

添加的三种情况效率如下

情况	操作	效率
插入即可	直接插入	O(1)
需要调整(旋转)	一次重组	O(1)
需要分裂	可能产生连续上溢.连续染色	O(logn)

删除

和普通二叉搜索树相同,删除非最下层结点,最终都能转换成删除最下层位置(可能是红色或黑色)的情况(注意转换时的染色)

• 转换后删除的位置为红色 - 对应删除(2,4)树2-3个元素的结点中的元素 - 直接删除

• 转换后删除的位置为黑色 - 对应删除(2,4)树只有1个元素的结点,发生向下溢出

  • 删除位置兄弟结点为黑色

    • 兄弟结点有红色孩子,向兄弟"借"一个结点
      

    • 兄弟结点冇红色孩子,向黑色父亲结点"借"一个结点.

      如果黑色父亲本身没有红色孩子,把自己借给黑色孩子之后变空了,则发生了新的向下溢出,重新执行开头删除位置为黑色结点的流程

      

  • 删除位置兄弟结点为红色 - 对黑色父亲结点p和p的红色孩子进行一次旋转,转换为删除位置兄弟为黑色的情况
    

删除的位置分成了四种情况,效率如下

情况	操作	效率
情况零 - 直接删除红色结点	直接删除	O(1)
情况一 - 向兄弟借一个孩子	一次重组	O(1)
情况二 - 向父亲借一个元素	可能连续下溢,需要连续染色	O(logn)
情况三 - 转换为情况一/二	一次旋转	O(1)

性能分析

• 搜索的性能O(logn)取决于树的高度
• 添加和删除前需要先搜索
• 添加和删除最坏的情况需要进行下面的操作来维护树的平衡,相比(2,4)树和AVL树速度提升的原因是染色操作的速度要快于结构变化
  • O(logn)次的染色
  • 常数次的结构变化(向上分裂和旋转 )

伸展树

• 永远将最后搜索/访问 删除 修改 添加的结点移动至根节点,类似于启发式动态调整列表(每次将最后访问的元素移动至首位)
• 高度h没有严格的对数上界
• 伸展 - 关键操作
  • 将某一节点通过一系列不改变中序遍历结果的重组操作移动至根节点
  • 随机的查询和修改造成了随机的永久性伸展,随机的伸展又导致了新添加元素位置的随机性
  • 伸展一个位置p需要的时间为O(位置的深度),等同于从根位置到p的向下搜索
• 插入 删除 搜索操作运行时间
  • 平摊 - O(logn)
  • 最坏 - O(n)
• 伸展树的摊销(平均)性能和AVL树 (2,4)树的最坏情况性能相同.但优点是不需要存储任何额外的辅助数据(高度等),占用更小的存储空间
• 访问一个结点i的摊销时间 - O(log(从零形成树的总操作数量/i的被访问次数))

用于数据库和文件系统的搜索树

参考链接

• 从B树、B+树、B*树谈到R 树

  https://blog.csdn.net/v_JULY_v/article/details/6530142/

• 一文详解 B-树，B+树，B*树

  https://zhuanlan.zhihu.com/p/98021010

• b树和b+树的区别

  https://blog.csdn.net/windflybird/article/details/79875972

• 平衡二叉树、B树、B+树、B*树 理解其中一种你就都明白了

  https://zhuanlan.zhihu.com/p/27700617

• B+树和B*树的存储结构,更适合文件系统的存储结构

  因为其数据分布更为集中(增强了空间局部性),容易被一次从磁盘调入主存,节省磁盘读取时间,提高效率

B+树

• B+树是多路搜索树(B树)的变形,不同点 :
  • 非叶子结点负责查找,叶子结点负责存储数据
    • 在最底层的叶子结点保存多个**关键字key 和 数据存储位置的指针**
    • 在非叶子结点保存关键字的检索索引
  • 这导致每次查询都访问到最下层的叶子结点才结束
    • 每次查询效率相同,和多路搜索树相比更加稳定
    • 对于数据访问频率相差大,可以优化的情况,多路搜索树效率更高,因为其非叶结点也存储了元素,离根更近
  • 叶子结点的结尾指向右边兄弟叶子结点的开头
    • 所有的叶子节点构成一个有序链表，在查询大小区间的数据时候更方便
    • 数据紧密性高，缓存的命中率也会比B树高
    • 全节点遍历更快 - 遍历整棵树只需要遍历所有的叶子节点即可
  • 底层叶子结点数=关键词数

B*树

• B*树是B+树的变种
  • 在B+树的非叶子结点的结尾也增加了指向兄弟结点开头的指针
  • 当结点存满时,不会像多路搜索树那样立即向上分裂,会先试图将元素向相邻的兄弟结点q转移,q也满了才进行分裂
    • 这使树在添加元素时通过更少的结构变化实现了平衡
  • 增加了非叶结点中索引个数的限制,要求结点内最少有两个元素.提升了存储空间的利用率

高维数据的存储 R树

参考链接

• 从B树、B+树、B*树谈到R 树

  https://blog.csdn.net/v_JULY_v/article/details/6530142/

- 完 -