算法与数据结构学习笔记(5)

1、2-3-4树

与红黑树相似,也是一种自平衡树。各类节点的红黑树对应结构,如下:

2-节点:黑色节点

3-节点:黑色节点+红色子节点

4-节点:黑色节点+2个红色子节点

4-节点的分割:新建一个节点,把原4-节点第3个元素移至新节点,并把第3、4个子节点连接至新节点;第2个元素移至父节点,最后把新节点连接到父节点。

2-节点的合并:

(1)从父节点移动与当前节点位置相邻的数据到当前节点,使用相邻节点的第一个或最后一个数据(取决于相邻节点的方向)填补空缺,并把相应的子节点连接到当前节点。

(2)若未合并前相邻节点不是2-节点,则可退出。

(3)若父节点为2-节点且不是根节点,先对其进行合并。

(4)把之前移到父节点的数据移动至当前节点,相邻节点剩余的一个子节点连接至当前节点,并删除相邻节点。如父节点未合并前为2-节点且为根节点,则设置当前节点为新根节点。

2、外部存储

  • B-树:二叉查找树及2-3-4树均为B-树的特殊形式
  • 索引
  • 排序:内存不足的情况下可用归并排序

Leave a Reply

Your email address will not be published. Required fields are marked *