数据结构 Tree相关知识点总结

数据结构 Tree相关知识点总结

Posted by julyerr on March 9, 2018

本文文章对数据结构中树中比较容易忽视的内容进行总结,其他常见知识点例如二叉树的几种遍历方式等可以参考本人leetcode的tree刷题记录

平衡二叉树(红黑树)

二叉树在某些场景,可能O(n)的查找效率。为了维护二叉树的平衡性,学者先提出了平衡二叉树(AVL)算法,但是AVL操作较为繁琐;后来又有学者提出红黑树算法。红黑树是一种近似平衡二叉树算法,操作等方面更易理解,在现实场景中使用比较多。

二叉树的旋转

左旋(右子为轴,当前结点左旋)

右旋(左子为轴,当前节点右旋)

红黑树的定义

  • 每个节点非黑即红
  • 根节点是黑色的
  • 每个哨兵节点是黑色的
  • 红节点的两个子节点都是黑色
  • 每个节点到后代哨兵节点路径上的黑色节点数量是一样多

上面的五大约束条件,决定了红黑树插入和删除的时间复杂度均是O(logn),由于插入和删除操作可能修改上面的规则,因此需要进行调整.

插入操作

一共可能出现三种情况

叔节点是红色
父亲x.p和叔节点y都染成黑色,将父亲的父亲x.p.p节点染成红色; x设置为x.p.p节点,交给下个迭代解决

当前的节点是右孩子,叔节点是黑色
将x设置成x.p,对x左旋

前节点是左孩子,叔节点y是黑色

x.p染成黑色,再将x节点的父亲的父亲x.p.p染成红色

将x.p.p右旋

删除操作

总共可能出现四种情况

兄弟sib是红色节点
将兄弟设置黑色,将x的父亲设置为红色,并将x的父亲左旋,设置新的兄弟节点为sib。将情况1转换成情况2或3或4。

兄弟节点sib是黑色的,且sib的两个孩子节点也是黑色

设置兄弟节点sib为红色,将x设置为x的父亲,以此向上循环达到平衡。

兄弟节点sib是黑色的,sib的左孩子是红色,sib的右孩子是黑色
设置sib的左孩子为黑色,设置sib为红色,将sib右旋,重新设置sib为x的兄弟节点。

兄弟sib是黑色的,sib的右孩子是红色的
设置sib为父亲的颜色,设置父亲为黑色,设置sib的右孩子为黑色,对父亲左旋,并将x设置为root。

这篇文章使用例子的方式讲解插入和删除的具体过程。
java TreeMap内部使用红黑树算法,也可以看看源码实现。


B 树

常见的查找算法以及上文的红黑树算法都是内排序查找算法(内存中进行,不涉及磁盘等操作,数据量较少,速度较快);B树等则是外排序算法(通常数据量较大、涉及到磁盘操作,速度相对较慢一些)。

B树是对二叉树的扩展,可以拥有多于2个的孩子节点,而且为系统大块数据的读写操作做了优化。

B-树

M为树的阶数,B-树要么为空要么满足下列条件:

  1. 根结点的儿子数为[2, M]
  2. 除根结点以外的非叶子结点的儿子数为[M/2, M]
  3. 每个结点存放至少ceil(M/2)-1(取上整)和至多M-1个关键字
  4. 非叶子结点的关键字:K[1], K[2], …, K[M-1];且K[i] < K[i+1]
  5. 所有叶子结点位于同一层

下图为3阶B-树

小红方块表示对应关键字所代表的文件的存储位置,P则代孩子指针。指针,关键字,以及关键字所代表的文件地址这三样东西合起来构成了B树的一个节点,这个节点存储在一个磁盘块上。

搜索过程

从根结点开始,对结点内的关键字(有序)序列进行二分查找,如果命中则结束,否则进入查询关键字所属范围的儿子结点;重复,直到所对应的儿子指针为空,或已经是叶子结点。

下面是搜索29具体过程:

  • 从根节点开始,读取根节点信息,根节点有2个关键字:17和35。因为17 < 29 < 35,所以找到指针P2指向的子树,也就是磁盘块3(1次I/O操作)
  • 读取当前节点信息,当前节点有2个关键字:26和30。26 < 29 < 30,找到指针P2指向的子树,也就是磁盘块8(2次I/O操作)
  • 读取当前节点信息,当前节点有2个关键字:28和29。(3次I/O操作)

插入过程

插入过程需要调整关键之处是,当一个节点的关键字数超过m-1,要对节点进行“分裂”。此文中有一个较好的插入实例过程

删除过程

同样删除过程需要调整关键之处是,关键字被删除导致节点的关键字小于ceil(M/2)-1,需要采用合并操作.

notes
内部节点的删除可以通过元素交换,将被删除的节点交换到叶子节点中。

有下面几种情况需要考虑(以具体的示例讲解)

1.被删关键字所在结点中的关键字数目不小于ceil(m/2),只需要直接删除该关键字和指针即可;下图为图4.1( a)删除关键字12所得结果

2.被删关键字所在结点中的关键字数目等于ceil(m/2)-1,而与该结点相邻的右兄弟(或左兄弟)结点中的关键字数目大于ceil(m/2)-1。需将其兄弟结点中的最小(或最大)的关键字上移至双亲结点中,而将双亲结点中小于(或大于)且紧靠该上移关键字的关键字下移至被删关键字所在结点中。下图为图4.2( a)中删去50所得结果

3.被删关键字所在结点和其相邻的兄弟结点中的关键字数目均等于ceil(m/2)-1。 删除关键字之后,它所在结点中剩余的关键字和指针,加上双亲结点中的关键字K[i]一起,合并到 Ai所指兄弟结点中.下图为从图4.2(b)所示 B-树中删去53所得结果。

如果因此使双亲结点中的关键字数目小于ceil(m/2)-1,则依次类推。

上图为在图4.2(c)的B-树中删去关键字37之后,双亲b结点中剩余信息(“指针c”)应和其双亲a结点中关键字45一起合并至右兄弟结点e中,所得到的结果。

此文中有一个较好的删除实例过程


B+树

B+树是B-树的变体,也是一种多路搜索树,其定义基本与B-树同

  1. 非叶子结点的子树指针与关键字个数相同
  2. 所有关键字都在叶子结点出现,并为所有叶子结点增加一个链指针

B+和B-树的区别

  • 内部节点中,B+关键字的个数与其子树的个数相同
  • B+中所有的关键字都出现在叶子节点中(内部节点仅仅起到索引的作用),B-树中部分关键在内部节点
  • B+树在搜索过程中,如果查询和内部节点的关键字一致,那么搜索过程不停止,而是继续向下搜索这个分支

B+树在文件系统、数据库系统当中,更有优势

  • 磁盘读写代价更低:B+树的内部结点并没有指向关键字具体信息的指针,因此其内部结点相对B树更小。同一块盘中所能容纳的关键数量也越多,I/O读写次数也就降低了;
  • 查询效率更加稳定:任何关键字的查找必须走一条从根结点到叶子结点的路,每一个数据的查询效率相当。
  • 有利于对数据库的扫描:只需要遍历叶子节点就可以解决对全部关键字信息的扫描,所以对于数据库中频繁使用的range query,B+树有着更高的性能。

B*

在B+树的非根和非叶子结点再增加指向兄弟的指针

区别 B*树定义了非叶子结点关键字个数至少为(2/3)*M,即块的最低使用率为2/3(代替B+树的1/2)。而且在分裂阶段,当一个结点满时,如果它的下一个兄弟结点未满,那么将一部分数据移到兄弟结点中;如果兄弟也满了,则在原结点与兄弟结点之间增加新结点,并各复制1/3的数据到新结点。 B*相对于B树而言提高了空间使用率.


MyISAM和InnoDB两个存储引擎的索引实现方式

MyISAM索引

主键索引

MyISAM引擎使用B+Tree作为索引结构,叶节点的data域存放的是数据记录的地址。

MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引,如果指定的Key存在,则取出其data域的值,然后以data域的值为地址,读取相应数据记录。

辅助索引在结构上没有任何区别,只是主索引要求key是唯一的,而辅助索引的key可以重复。

InnoDB索引

主键索引

InnoDB中,表数据文件本身就是按B+Tree组织的一个索引结构,这棵树的叶节点data域保存了完整的数据记录。

InnoDB叶子节点包含了完整的数据记录,这种索引方式称为聚集索引;MyISAM的索引方式也成为非聚集索引。因为InnoDB的数据文件本身要按主键聚集,所以InnoDB要求表必须有主键(MyISAM可以没有)。

辅助索引 InnoDB的所有辅助索引都引用主键作为data域 聚集索引这种实现方式使得按主键的搜索十分高效,辅助索引搜索需要检索两遍索引:首先检索辅助索引获得主键,然后用主键到主索引中检索获得记录。


参考资料