首页 > 代码库 > 数据结构之2-3-4树

数据结构之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)。

想详细了解代码实现,请移步http://www.cnblogs.com/guoyiqi/archive/2011/06/08/2129310.html。我这里只提一些概念性的东西

数据结构之2-3-4树