目录

2-3树与红黑树

基本介绍

2-3树是最简单的b树结构,具有如下性质:

  1. 2-3树的所有叶子节点都在同一层。(只要是b树都满足这个条件)
  2. 有两个子节点的节点叫二节点,二节点要么没有子节点,要么有两个子节点。
  3. 有三个子节点的节点叫三节点,三节点要么没有子节点,要么有三个子节点。
  4. 2-3树是由二节点和三节点构成的树。
  5. 2-3树仍然遵守BST的排序规则

相关概念

  1. 2节点:要么没有子节点要么有2个子节点,存储一个值
  2. 3节点:要么没有子节点要么有3个子节点,存储2个值
  3. 节点分裂:3节点可以分裂成2节点,插入的时候会引入4节点也需要分裂成3节点,比如: https://gitee.com/lienhui68/picStore/raw/master/null/20200630140851.png
  4. 节点合并:比如有父节点的4节点,节点分裂后,需与父节点进行合并。若合并后父节点还是4节点,则继续分裂,直至满足定义为止。下图中6与3合并后,满足条件,无需再进行操作。 https://gitee.com/lienhui68/picStore/raw/master/null/20200630141046.png

2-3树的查找

与BST查找类似,只不过对于3节点情况需要判断左中右3颗子树,原理一样。

2-3树的插入

插入一个节点后,也要满足2-3树的定义。我们需要找到一个适合的位置来插入新的值,但是和二叉树不同的是,它不会生成新的叶子节点来存储,而是找到合适的叶子节点来进行合并。下层节点的合并可能会引起上层节点的分裂,分裂的最坏情况是树的高度+1。

  1. 对于空树,插入一个2节点即可
  2. 插入节点到一个2节点的叶子上 由于其本身只有一个元素,所以只需要将2节点升级成3节点(也就是2个2节点合并成3节点)即可。
  3. 插入节点到一个3节点的叶子上 这种情况比较复杂,因为涉及到分裂,假定待插入节点是N,待插入节点的父节点是P。 先临时将节点插入到N中,使之成为一个4节点,4节点不满足2-3树性质,因此需要将4节点分裂成3节点,因此需要将其中一个元素(3个元素的中间值)与P进行合并,此时需要考虑P的类型。 3.1. P是2节点 将N中的中值插入到P中,使P构成一个3节点,N的左右值分裂成2个2节点 https://gitee.com/lienhui68/picStore/raw/master/null/20200630144351.png 3.2. P是3节点 N的中值插入到P中使的P成为了4节点,此时P的孩子也需要分裂。P将中值插入到P的父节点,依此类推。如下图的一个示例: https://gitee.com/lienhui68/picStore/raw/master/null/20200630145713.png 非叶子节点调整如下图: https://gitee.com/lienhui68/picStore/raw/master/null/20200630145931.png 好的情况是往上合并的过程中遇到一个2节点则结束,坏的情况是一直合并到根节点并且根节点是3节点,那么只好往上分裂出新的根节点,然后处理节点与其他节点的关系,树的高度+1. https://gitee.com/lienhui68/picStore/raw/master/null/20200630150007.png

2-3树的删除

2-3树节点的删除也会破坏平衡性,同样树本身也会产生分裂和合并,如下: https://gitee.com/lienhui68/picStore/raw/master/null/20200630150249.png 节点的删除,与二叉搜索树的删除类似,不同的是2-3树会寻找中序的后继节点来替换要删除的节点的值,然后再删除替换的值: https://gitee.com/lienhui68/picStore/raw/master/null/WX20200630-150532@2x.png 与插入类似,删除的过程中root节点的值可能会被调整到新的节点,而原root节点就会变成空节点,从而需要删除,如下: https://gitee.com/lienhui68/picStore/raw/master/null/20200630150720.png 删除的过程,也是非常复杂的,涉及到节点的分裂,合并,重分布,删除等操作,这里不再详细描述。

将2-3树转换成左倾红黑树

主要思想:3节点分裂成2节点 将3节点的第一个元素,作为第二个元素的左节点,并用红色的线连接,此时红色线连接的节点就相当于红色。 https://gitee.com/lienhui68/picStore/raw/master/null/20200630151059.png 来分析下左倾红黑树的性质

  1. 没有任何一个节点同时与两个红链接相连 因为一个红链表示一个3节点,如果有2个红链相连,则表示为4节点,不符合2-3树定义。
  2. 根节点为黑色 只有3节点的左链才为红色。根节点没有父节点,不可能为红色。
  3. 根节点到叶子节点经过的黑色节点数目相同 因为2-3树是完美平衡的。红黑树中经过的黑节点数=其层数。

参考

什么是2-3树 从2-3树理解红黑树