数据结构之2-3-4树

2-3-4树是一种阶为4的B树。它是一种自平衡的数据结构，可以在O(lgn)的时间内查找、插入和删除，这里的n是树中元素的数目。2-3-4树和红黑树是等价的，也就是每个红黑树都可以转化为一颗2-3-4树，每个选择操作也和2-3-4树中的分裂操作对应。

      2-3-4树是这样一种数据结构，满足如下性质:

      1) 每个节点每个节点有1、2或3个key，分别称为2-node，3-node，4-node。

      2) 每个节点的keys把区间进行了划分，以4-nde为例，key1、key2、key3分别夹在subtree1, subtree2和subtree2, subtree3和subtree3, subtree4之间。

      3) 4-node的子节点不能是4-node。

      如下图所示：

      搜索：

      1. 从root开始

      2. 比较当前节点的值

          2.1 如果找到，就返回当前节点

          2.2 如果没有找到，就找出要搜索的值属于哪一个子树

      3. 递归的搜索子树

  在插入和删除的关键是维持性质3），即4-node的节点不能是4-node

     插入Key

1.递归搜索Key

         1.1 如果root是4-node(ABC)，则建一个新的root(B)，A，C成为它的两个子树

　　   1.2 向下搜索, 对于中途经过的每一个node, 如果它是4-node则使用如下图的变换分拆(注意到根据假设算法不会产生4-node的子节点是4-node, 所以这个操作总是能进行的)

　　   1.3 如果相应的key已存在, 则算法结束, 不需要插入 

     2. 注意到如果key不存在, 则1的递归搜索一定停在叶节点

     3. 在当前的叶节点插入

　　   3.1 如果是2-node或3-node, 则插入当前节点把它变成3-node或4-node, 算法结束   

　　   3.2 如果是4-node, 则根据假设, 它的父节点一定不是4-node(即是2-node或者3-node)       

　　　　   3.2.1 使用与1.2相同的变换分拆4-node       

　　　　   3.2.2 插入相应节点(如图所示, 一定是2-node)

       要证明2-3-4上面的出入算法一定形成一个平衡树，即从root开始往下到任一个叶子的长度都是相等。

       用数学归纳法：

       1. 只有一个节点的树当然是平衡的

       2. 假设插入了n个元素，树还是平衡的，现在插入一个新元素，要证明不会破坏平衡性：

       算法会改变tree的是1.1, 1.2, 3.1, 3.2。显然1.2, 3.1, 3.2都不会改变树的深度，考虑1.1，它令树的路径深度增加1，原来的树是平衡的，深度增加后当然还是平衡的。

        有n个元素的2-3-4树的深度的粗略估计；最坏情况全是2-node，则深度是logn，最好情况全是4-node，深度为logn/2，故：

logn/2 <  depth  ≤  logn(左边括号是不可能的，因为不存在4-node的子节点是4-node)。