从234树到红黑树（上）

欢迎探讨&＃xff0c;如有错误敬请指正

如需转载&＃xff0c;请注明出处   http://www.cnblogs.com/nullzx/

相关博客&＃xff1a;

从2-3-4树到红黑树&＃xff08;中&＃xff09;

从2-3-4树到红黑树&＃xff08;下&＃xff09;

2-3-4树是一种阶为4的B树。它是一种自平衡的数据结构&＃xff0c;可以保证在O(lgn)的时间内完成查找、插入和删除操作。它主要满足以下性质&＃xff1a;

&＃xff08;1&＃xff09;每个节点每个节点有1、2或3个key&＃xff0c;分别称为2&＃xff08;孩子&＃xff09;节点&＃xff0c;3&＃xff08;孩子&＃xff09;节点&＃xff0c;4&＃xff08;孩子&＃xff09;节点。

&＃xff08;2&＃xff09;所有叶子节点到根节点的长度一致&＃xff08;也就是说叶子节点都在同一层&＃xff09;。

&＃xff08;3&＃xff09;每个节点的key从左到右保持了从小到大的顺序&＃xff0c;两个key之间的子树中所有的

key一定大于它的父节点的左key&＃xff0c;小于父节点的右key。

&＃xff08;1&＃xff09;如果2-3-4树中已存在当前插入的key&＃xff0c;则插入失败&＃xff0c;否则最终一定是在叶子节点中进行插入操作

&＃xff08;2&＃xff09;如果待插入的节点不是4节点&＃xff0c;那么直接在该节点插入

&＃xff08;3&＃xff09;如果待插入的节点是个4节点&＃xff0c;那么应该先分裂该节点然后再插入。一个4节点可以分裂成一个根节点和两个子节点&＃xff08;这三个节点各含一个key&＃xff09;然后在子节点中插入&＃xff0c;我们把分裂形成的根节点中的key看成向上层插入的key&＃xff0c;然后重复第2步和第3步。

   如果是在4节点中进行插入&＃xff0c;每次插入会多出一个分支&＃xff0c;如果插入操作导致根节点分裂&＃xff0c;则2-3-4树会生长一层。

&＃xff08;1&＃xff09;如果2-3-4树中不存在当前需要删除的key&＃xff0c;则删除失败。

&＃xff08;2&＃xff09;如果当前需要删除的key不位于叶子节点上&＃xff0c;则用后继key覆盖&＃xff0c;然后在它后继

key所在的子支中删除该后继key。

&＃xff08;3&＃xff09;如果当前需要删除的key位于叶子节点上:

       &＃xff08;3.1&＃xff09;该节点不是2节点&＃xff0c;删除key&＃xff0c;结束

       &＃xff08;3.2&＃xff09;该节点是2节点&＃xff0c;删除该节点&＃xff1a;

              &＃xff08;3.2.1&＃xff09;如果兄弟节点不是2节点&＃xff0c;则父节点中的key下移到该节点&＃xff0c;兄弟节点中的一个key上移

             &＃xff08;3.2.2&＃xff09;如果兄弟节点是2节点&＃xff0c;父节点是个3节点或4节点&＃xff0c;父节点中的key与兄弟节点合并

             &＃xff08;3.2.3&＃xff09;如果兄弟节点是2节点&＃xff0c;父节点是个2节点&＃xff0c;父节点中的key与兄弟节点中的key合并&＃xff0c;形成一个3节点&＃xff0c;把此节点看成当前节点&＃xff08;此节点实际上是下一层的节点&＃xff09;&＃xff0c;重复步骤3.2.1到3.2.3

   如果是在2节点&＃xff08;叶子节点&＃xff09;中进行删除&＃xff0c;每次删除会减少一个分支&＃xff0c;如果删除操作导致根节点参与合并&＃xff0c;则2-3-4树会降低一层。

上面的插入以及删除操作在某些情况需要不断回溯来调整树的结构以达到平衡。为了消除回溯过程&＃xff0c;在插入操作过程中我们可以采取预分裂的操作&＃xff0c;即我们在插入的搜索路径中&＃xff0c;遇到4节点就分裂&＃xff08;分裂后形成的根节点的key要上移&＃xff0c;与父节点中的key合并&＃xff09;这样可以保证找到需要插入节点时可以直接插入&＃xff08;即该节点一定不是4节点&＃xff09;

在删除过程中&＃xff0c;我们同样可以采取预合并的操作&＃xff0c;即我们在删除的搜索路径中&＃xff08;除根节点&＃xff0c;因为根节点没有兄弟节点和父节点&＃xff09;&＃xff0c;遇到当前节点是2节点&＃xff0c;如果兄弟节点也是2节点就合并&＃xff08;该节点的父节点中的key下移&＃xff0c;与自身和兄弟节点合并&＃xff09;&＃xff1b;如果兄弟节点不是2节点&＃xff0c;则父节点的key下移&＃xff0c;兄弟节点中的key上移。这样可以保证&＃xff0c;找到需要删除的key所在的节点时可以直接删除&＃xff08;即要删除的key所在的节点一定不是2节点&＃xff09;。

这里包含key为60的节点也可以选择让父节点中的key 76下移和兄弟节点中的83合并&＃xff0c;两种方式都能达到B树的平衡&＃xff0c;这也是在2-3-4树对应的红黑树中使用的方式。