首页 > 代码库 > 数据结构之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树