BST,AVL树,B树,B+树,红黑树

引言

算法课老师讲到了二叉搜索树(BST),因为大四背面经接触过下面几种类型,因此想简单mark一下

注:本篇文章对树的操作并无图,可自行绘制理解
另:里面的操作部分的文字描述是我看了较多文章自己综合口述的,有可能有错

BST

BST(Binary Search Tree)二叉搜索树,也叫二叉查找树
它是由二分法+二叉树构成,即以树结构呈现的二分法.左子树的节点值均小于根节点,右子树的节点值均大于根节点

BST

对于查找,插入,删除,平均时间复杂度是$O(\log_{2}{n})$,而其最坏状况,若是依有序数据构建树,则会退化成链表,则对应的时间复杂度都是最坏的$O(n)$

对于其查找,插入,都跟二分法类似,不赘述;而对于删除问题,因删除后需保持BST的二分特性,因此需要对删除后的树进行一些修改,分三种情况讨论:

1. 删除的是叶子节点: 直接删除,无影响
2. 删除的是中间节点,且只有一个子树: 直接把子树根节点对中间节点进行顶替
3. 删除的是中间节点,且有两个子树: 若删除的节点位于根节点的左子树,则用删除节点的左子树顶替之,并将删除节点的右子树移到其原兄弟节点的右子树下即可;另一侧是对称操作,不赘述.
4. 删除的是非空根节点:与左子树中最大值交换后删除即可或与右子树中最小值交换后删除即可

AVL树

AVL树叫做平衡二叉树,是对BST的一种改进,引进了平衡机制,后面要谈的红黑树也是一种balance tree,但是AVL树的平衡更是一种强平衡
平衡机制:任意节点的左右子树高度差不超过1,我们管这个1叫做平衡因子(Balance factor),即bf=1
通过平衡机制的强硬限制,规避了退化成链表的可能

AVL树

AVL树在查找,插入,删除的平均及最差的时间复杂度均为:$O(\log{2}{n})$

对于其查找,与二分法类似,不赘述.之于插入删除问题,由于会影响树的高度,需为维持平衡机制,因此存在左旋,右旋的概念,示意图如下:

AVL-ROTATE

右旋:rotateRight(Q),将节点Q作为其左孩子的右孩子
左旋:rotateLeft(P),将节点P作为其右孩子的左孩子

针对插入情况的讨论(假设原始状态均满足平衡机制):

插入位置	状态	操作
在节点T的left child的left tree上插入元素	LL	右旋
在节点T的right child的right tree上插入元素	RR	左旋
在节点T的left child的right tree上插入元素	LR	先左旋,再右旋
在节点T的right child的left tree上插入元素	RL	先右旋,再左旋

以下以一个插入导致的LL情况作为示例,图示如下:

AVL-LL

注:图示的例子是给原树插了两个元素,其实这里一个或是两个元素数量都一样,因为都是挂载在同一棵树上,主要目的是导致了有的节点左右子树高度差超过了1

特别注意:AVL树插入位置的条件与后面介绍的红黑树的插入位置的条件并不等价!其不等价的原因与各自平衡机制相关

以下是插入元素后的旋转情况概览图:

AVL-ALL-ROTATE

删除的情况太多了,大致其实都是删了之后进行1~2次的旋转即可.此处不讨论

B-树

B-树就是B树(Balance Tree),中间的一杠是连字符.它是MongoDB的WiredTiger引擎中索引采用的数据结构.而数据库持久化的数据都是放在硬盘上的,索引也是.而对于硬盘的一次访问即是一次I/O操作,它的时间消耗是毫秒级别的.因此,我们需要减少I/O操作的次数以提高访问速度(毕竟存储结构没办法改变)

而之所以采用树形结构对索引进行存储,是因其于等值查询和区间查询都具备一定优势,而这些正是我们数据库中绝大多数涉及到的操作.

那么为什么用B-树呢?

因为B-树跟上面的树相比更加矮胖.B树允许一个节点有多个子节点,且节点内部可以存储多个元素.这就使得我们树的高度可控,不会太高,即树会变得矮胖.而之所以期望树可以更矮胖是因为我们从硬盘中读数据是以磁盘块为单位的,磁盘块有固定大小(一般4096B,4K大小),读出来的数据就等价于我们数据库中的页的概念,页和磁盘块是一样大小的,因此我们树的一个节点对应的是一个磁盘块大小的数据,那么减少I/O操作即转换成减少访问树的节点个数.B树是多路查找树,也是平衡树,它的bf=0.因此树的宽度(节点大小)决定了一次I/O操作获取到的数据量,树的高度决定了访问的I/O次数

一颗m阶B树有如下特点:(这里将节点分为:[根节点,内部节点,叶子节点])

• 根节点或是叶子节点,或是拥有$2$到$m$个孩子节点的非叶子节点;
• 所有内部节点都有$k-1$个key值和$k$个孩子节点,其中$\lceil \frac{m}{2} \rceil \le k \le m$
• 所有叶子节点都包含$k-1$个key值,其中$\lceil \frac{m}{2} \rceil \le k \le m$
• 所有叶子节点位于同一层(bf=0的体现)
• 每个节点中的key值是升序排列的,节点中的$k-1$个key值可以划分出$k$个孩子节点

一颗普通的B树如下图示:

B-Tree

注:上图的P1,P2这些是指针,我们的树与子树的关系基本都是通过指针维系的,别的也是,没画出来而已,这里如磁盘块2,它只画了索引值,其实还有个叫卫星数据(不知道为啥叫这个)的东西,它所指代的是索引元素指代的数据记录,那就比如是某张表的某一行数据

看完上面对B树的特点定义会好奇为何根节点要么是叶子节点,要么至少有两个子节点,它的插入删除咋执行的,其实这些问题都源于以下两句话:

• 插入key值至超出阈值(上面所说的节点内key值的上界),会致使节点产生分裂,分裂伴随着该节点中值的上溢(上移),甚至有的情况节点上溢会递归导致一个新的根节点的产生

插入致使上溢,有新节点产生

插入致使上溢,无新节点产生

注:可以很清晰地看出来,B-树以及下面要将的B+树,跟以往的树的构造不一样,它们是由下至上构建的,而先前学的二叉树啥的都是自顶向下构建的

• 删除叶子节点的key值至超出阈值(上面所说的节点内key值的下界),会致使其向兄弟节点借一个key值,如果它的兄弟节点key值也不够,那就要三合一(删了key值的节点,它的兄弟节点,它们间的父节点的key值即使其下溢(下移)),甚至可能导致父节点的key值也刚好不够,则递归下溢直至所有节点满足要求

叶子节点删除key,向兄弟借key

叶子节点删除key,做合并

• 删除内部节点(中间节点)的key值至超出阈值,向有足够key值的子节点借一个key值,如果不够,就只可以合并,这个合并也是三合一(跟上面的一样)

内部节点删除key,向子节点借key

内部节点删除key,做合并

B+树

我们知道B+树是MySQL的InnoDB引擎中索引采用的数据结构,而B+树是B树的升级版,它增加了如下的特点:(树的节点于此处分为:[根节点,内部节点,叶子节点])

1. 非叶子节点内含有k个子节点,亦含有k个key值,每个key值对应一个子节点;
2. 非叶子节点内不含数据,只有key值用于索引;key值及数据全存放于叶子节点,叶子节点间的key值依升序链接,叶子节点间通过链表链接;
3. 非叶子节点的key值都存在于子节点中,且是子节点中key值的最大或最小的

1,3制造冗余边界数据,便于插入和删除的方式改进,将对树的变形控制在单一分支(其实如插入也存在上溢的情况,也要比较猛烈的变形,但对删除有了很大改变),避免了复杂的树变形;
2.则扩增了每个节点的key值数目,进而使得树更加矮胖,有利于减少I/O操作次数;而数据全放在叶子节点,树更稳定(查询都要$O(\log_{2}{n})$),也利于MySQL常用的区间查询

以下是B+树的一个普通示例图:

B+Tree

MongoDB是文档型的数据库,是NoSQL中的一种,用JSON格式存数据(这是一种聚合型的方式,与MySQL的表结构的设计思路很不同,MySQL的表间关系通过外键进行链接,而JSON对有关系的可以直接编到一个map里),于MongoDB而言更多进行的是单一数据查询,不涉及遍历查询,那么我们此刻B+树的优点于它而言就没啥意义,而B-树的值也存在于非叶子节点中,它的时间复杂度处于$O(1)$~$O(\log_{2}{n})$的状态,相较于B+树的稳定的$O(\log_{2}{n})$,B-树更适用于MongoDB数据库;
MySQL则是我们都熟悉的关系型数据库,很显然,它涉及到较多遍历操作和区间查询,因此更适用于B+树,B-树的遍历和区间查询(需找边缘值后中序遍历)会产生更多的IO操作,不值得

勘误:经过看MongoDB官方文档,底层用的也是B+树,网上各类博客害人不浅
援引如下:

WiredTiger maintains a table’s data in memory using a data structure called a B-Tree ( B+ Tree to be specific), referring to the nodes of a B-Tree as pages. Internal pages carry only keys. The leaf pages store both keys and values.

红黑树

前面说过,AVL树是一种强平衡的树,而红黑树则是弱平衡的BST.它较之于AVL树而言,正由于它的弱平衡性,导致我们在插入删除时不必要进行那么多的旋转操作!

红黑树的平衡性体现在:从根到叶子的最长路径不会比最短路径长超过两倍

之所以说它是弱平衡的,是因为它没有将bf强制约束于某个值,而是通过如下5条性质来维持弱平衡性:

• 节点是红色或黑色的
• 根节点是黑色的
• 叶子节点都是黑色的,它们都是空节点,data为null
• 不能出现连续的两个红色节点(即一个红色节点的父节点及其子节点一定都是黑色的)
• 从任一节点到叶子节点的所有路径都包含相同数目的黑色节点

针对最后一点性质,红黑树有一个黑高度(黑高)的概念:从某个节点出发至一叶子节点,所经历的黑色节点的个数(不包括起始节点,即使它是黑的)称为该节点的黑高bh.因此某一个节点的bh值应是唯一的,若不唯一则违背了最后一条性质

以下是红黑树的一张示意图:

RBT

红黑树的查找,插入,删除的时间复杂度都是$O(\log_{2}{n})$,跟AVL树的一样,但其实AVL树在处理插入和删除问题时,为了保持bf=1,会涉及到复杂的旋转问题.而具有强平衡性的AVL树的查询能力显然更强.因此在设计底层数据结构的时候可以根据侧重进行选择

而在之后介绍如插入等的相关操作时,一般会忽略掉最后的叶子节点,就是data为null的节点

一颗红黑树,通过将红色节点上移至父节点同一高度组成B树节点后,即等价于一颗4阶B树,其变形如下所示:

RBT2BTree

由上图可以看出来,红黑树变形为4阶B树后有如下性质:

• 红黑树与4阶B树具有等价性
• 黑色节点和其红色子节点融合形成一个B树节点
• 在一个融合形成的B树节点里,根节点是黑色的,子节点是红的
• 红黑树的非叶子节点的黑色节点个数与4阶B树的节点总数相等

我们先来探讨一下转换为4阶B树的红黑树,对应的节点内部情况.4阶B树节点内部最多允许有3个元素,依据上述的性质3,即存在以下情况:红黑红,黑红,红黑,黑,且其中黑色的一定是原红黑树的子树/树本身的根节点,图示如下:

RBT2BTree-node-classfication

对红黑树的插入删除情况的讨论也转换为对4阶B树的插入删除情况的讨论,但需要满足红黑树的性质

插入情况讨论:

首先给出插入情况的红黑树的图:

RBT2BTree-Insertion

对于B树的插入,是自底向上的.因此对插入情况可分为如下两大类及对应的细分:

• 插入导致上溢
• 插入不导致上溢
  • 父节点是黑色的
  • 父节点是红色的

而根据红黑树的性质:某一结点至叶子节点的任意路径的黑色节点个数相等可知,若插入节点的颜色是黑的,一定会破坏这条规则,且需要花较大功夫来维持这条规则;若插入节点是红的,则可能破坏了不允许有两个连续的红色节点这一规则,但对这一规则的维护可以通过旋转及变色来操作,较容易处理.因此插入节点一定都是红色节点

根据给出的示意图,可以分析得出如下的插入情况,分别是:

• 满足红黑树性质,无需修复
• 不满足红黑树性质,需要修复

对应的图示如下:

RBT2BTree-Insertion-without-repair

RBT2BTree-Insertion-need-repair

针对上图的不需上溢的情况,其实就是做旋转以及变色,旋转后变色需遵循上述的新B树节点内的根节点是黑色的两侧节点是红色的.之所以不需上溢可以通过旋转加变色处理,是因4阶B树允许节点内部最多三个元素,且当是三个元素的时候,是红黑红(根节点黑,俩子节点红)的情况

以下仅介绍不需上溢的其中一种情况,即LL.LL意味着插入元素位于父节点的左侧(L),而父节点也是位于grand节点的左侧,之于这种情况可通过右旋更新父节点,而后染色成红黑红的B树节点即可,过程见下图示:

RBT2BTree-Insertion-LL-RR

而后面的[LR,RL]这俩情况则是需要双旋,旋转成[LL,RR]后再转一次和进行染色就ok了

这四种情况[LL,LR,RL,RR]的流程如下表所示:

插入位置	状态	操作
插入元素位于其parent节点的left,而其parent位于其grand的left	LL	右旋
插入元素位于其parent节点的right,而其parent位于其grand的right	RR	左旋
插入元素位于其parent节点的right,而其parent位于其grand的left	LR	先左旋,再右旋
插入元素位于其parent节点的left,而其parent位于其grand的right	RL	先右旋,再左旋

而针对于需要上溢的情况其实更简单,因为我们首要解决的是上溢的问题,即节点分裂,上移,那么此刻就会分裂出两个新的子节点,而这俩子节点是原先父节点的子节点,现在做了独立的B树节点的根节点,即对二者变色即可,则此刻新插入的节点的情况等价于往黑色的根节点插入新节点,即满足红黑树性质,无需修复.这个整体过程可以概括为:上溢,变色,无需旋转

示例图如下:

RBT2BTree-Insertion-upflow

然后对[25<-38<-55]这一个B树节点(LL情况)右旋然后变色即可

关于删除的部分情况较多,之后有时间再补上:)