2-3 Tree

已发布 2017-12-18 11:43:11

2-3树的结构

类比于二叉树,结点可以含有两个值,左小右大,此时含有三个子结点,子结点值被他们父结点的两个值切分。

2-3树的插入自平衡

  • 1 向2结点插入
    • 2结点变成3结点
  • 2 向一颗只含有3结点的树插入
    • 此结点为根节点,树高度+1, 一个3结点变成3个2结点的二叉树
  • 3 向一个父节点为2结点的3结点插入(树平衡的关键)
    • 树高度不变,父2结点变成3结点
  • 4 向父节点为3结点的3结点插入
    • 向上递归第3种情况
    • 5 根节点也是3结点
      • 这就是情况2,树向上生长,高度+1

从2-3树到红黑树

红链接将2个2结点连接起来构成一个3结点,黑链接则是2-3树种的普通链接。

  • 约束
    • 红链接均为左链接
    • 没有任何一个结点同时和两条红链接相连
    • 该树是完美黑色平衡的,即任意空链接到根节点的路径上的黑链接数量相同

旋转操作

TODO

comments powered by Disqus