Size Balanced Tree(SBT)
许多人(尤其指phpers)连基础的算法都不会.更有许多人只会算法不会coding.
这方面让高中生给所有人做榜样.
陈启峰发现了一种BST(Binary Search Tree)的新实现方式,
命名为Size Balanced Tree(SBT).
(显然这是不容易的,学业压力中能够得到这样的成果)
SBT和其它BST一样,基本都支持以下操作.
insert,delete,find,rank,select,pred,succ
SBT最值得称道的就是它均摊O(1)的maintain操作.
正因为这样的维护操作,使它有着超过AVL的速度
(注:仅限于题目的测试,其它种类的BST没有经过严格的测试)
偶自己认为最终在于:
AVL进行了许多多余的操作来维持绝对的平衡
SBT只需要维护子树的大小,满足这两个条件.
(a)s[right[t]]>=s[left[left[t]]],s[right[left[t]]]
(b)s[left[t]]>=s[right[right[t]]],s[left[right[t]]]
简化的操作:
procedure insert(var t:longint;v:longint);
begin
if t=0 then
t=newnode(v)
else
if v<key[t] then begin
inc(s[t]);
insert(left[t],v);
if s[left[left[t]]]>s[right[t]] then
right_rotate(t,left[t]);
end
else begin
inc(s[t]);
insert(right[t],v);
if s[right[right[t]]]>s[left[t]] then
left_rotate(t,right[t]);
end;
end;
当然,SBT不是绝对完美的.
—
注:这里讨论的BST主要是自平衡BST(Self-balancing binary search tree)
比较流行的实现有Treap,Splay,AA Tree,RB Tree(红黑树),AVL Tree等.
平衡的一定比不平衡的快,不是吗?
—
这里偶又想到了另一种树.
Hans Reiser的 Dancing Tree.
Dancing Tree在reiser4文件系统上被应用.
简单说就是在将树存入磁盘之前先进行整理.(把小块聚成大块?)
而不是每次更新都进行整理(增加了读写的开销).
如果Hans没有被指控谋杀的话…
—
撤远了,就到这里.
http://www.nocow.cn/index.php/Size_Balanced_Tree
Size Balanced Tree
来自"NOCOW"
Size Balanced Tree(SBT)是一种平衡二叉查找树。它的论文由中国广东中山纪念中学的陈启峰于2006年底完成，并在Winter Camp 2007中发表。由于SBT的拼写很容易找到中文谐音，它常被中国的OIer们戏称为“傻X树”、“Super BT”等。但它的性能并不SB，编写起来也并不BT。恰恰相反，SBT易于实现，且据陈启峰论文中所言，“这是目前为止速度最快的高级二叉搜索树”。它能在O(logn)的时间内完成所有BST的相关操作。而且由于SBT赖以保持平衡的是Size域而不是其他“无用”的域，它可以很方便地实现动态顺序统计中的select和rank。性质
Size Balanced Tree（SBT）是一种通过大小（Size）域来保持平衡的二叉搜索树，它也因此得名。它总是满足：对于SBT的每一个结点 t：
- 性质(a) s[right[t] ]≥s[left[left[t]]]，s[right[left[t]]]
- 性质(b) s[left[t] ]≥s[right[right[t]]]，s[left[right[t]]]
图1
- s[R] ≥ s[A]，s[B]
- s[L] ≥ s[C]，s[D]
旋转
SBT的旋转（Rotations）与其他许多高级BST相同。它是下面提到的Maintain操作的基础。
图2
左旋转
Left-Rotate (t) 1 k ← right[t] 2 right[t] ← left[k] 3 left[k] ← t 4 s[k] ← s[t] 5 s[t] ← s[left[t]] + s[right[t]] + 1 6 t ← k
[编辑] 右旋转
Right-Rotate(t) 1 k ← left[t] 2 left[t] ← right[k] 3 right[k] ← t 4 s[k] ← s[t] 5 s[t] ← s[left[t]] + s[right[t]] + 1 6 t ← k
保持性质(Maintain)
当我们插入或删除一个结点后，SBT的大小就发生了改变。这种改变有可能导致性质(a)或(b)被破坏。这时，我们需要用Maintain操作来修复这棵树。Maintain操作是SBT中最具活力的一个独特过程；Maintain(T)用于修复以T为根的 SBT。调用Maintain(T)的前提条件是T的子树都已经是SBT了。我们需要讨论的有4种情况。由于性质a和性质b是对称的，所以我们仅仅详细的讨论性质a。
- 第一种情况：s[left[left[t]]>s[right[t]]
图3（同图1）- 首先执行Right-Ratote(t)，这个操作让图3变成图4；
图4 - 在这之后，有时候这棵树还仍然不是一棵SBT，因为 s[C]>s[B] 或者 s[D]>s[B] 也是可能发生的。所以就有必要继续调用Maintian(t)。
- 结点L的右子树有可能被连续调整，因为有可能由于性质的破坏需要再一次运行Maintain(L)。
- 首先执行Right-Ratote(t)，这个操作让图3变成图4；
- 第二种情况：s[right[left[t]]>s[right[t]]
图5- 在执行完Left-Ratote(L)后，图5就会变成下面图6那样了。
图6 - 然后执行Right-Ratote(T)，最后的结果就会由图6转变成为下面的图7。
图7 - 在第1步和第2步过后，整棵树就变得非常不可预料了。万幸的是，在图7中，子树A、E、F和R仍就是SBT，所以我们可以调用Maintain(L)和Maintain(T)来修复结点B的子树。
- 在第3步之后，子树都已经是SBT了，但是在结点B上还可能不满足性质a或性质b，因此我们需要再一次调用Maintain(B)。
- 在执行完Left-Ratote(L)后，图5就会变成下面图6那样了。
- 第三种情况：s[right[right[t]]>s[left[t]]
与情况1对称。 - 第四种情况：s[left[right[t]]>s[left[t]]
与情况2对称。
通过前面的分析，很容易写出一个普通的Maintain。
Maintain (t) 01 If s[left[left[t]]>s[right[t]] then //case1 02 Right-Rotate(t) 03 Maintain(right[t]) 04 Maintain(t) 05 Exit 06 If s[right[left[t]]>s[right[t]] then //case2 07 Left-Rotate(left[t]) 08 Right-Rotate(t) 09 Maintain(left[t]) 10 Maintain(right[t]) 11 Maintain(t) 12 Exit 13 If s[right[right[t]]>s[left[t]] then //case1' 14 Left-Rotate(t) 15 Maintain(left[t]) 16 Maintain(t) 17 Exit 18 If s[left[right[t]]>s[left[t]] then //case2' 19 Right-Rotate(right[t]) 20 Left-Rotate(t) 21 Maintain(left[t]) 22 Maintain(right[t]) 23 Maintain(t)
前 面的标准过程的伪代码有一点复杂和缓慢。通常我们可以保证性质a和性质b的满足，因此我们只需要检查情况1和情况2或者情况3和情况4，这样可以提高速 度。所以在那种情况下，我们需要增加一个布尔（boolean）型变量：flag，来避免毫无意义的判断。如果flag是false，那么检查情况1和情 况2；否则检查情况3和情况4。
Maintain (t,flag) 01 If flag=false then 02 If s[left[left[t]]>s[right[t]] then //case1 03 Right-Rotate(t) 04 Else 05 If s[right[left[t]]>s[right[t]] then //case2 06 Left-Rotate(left[t]) 07 Right-Rotate(t) 08 Else //needn’t repair 09 Exit 10 Else 11 If s[right[right[t]]>s[left[t]] then //case1' 12 Left-Rotate(t) 13 Else 14 If s[left[right[t]]>s[left[t]] then //case2' 15 Right-Rotate(right[t]) 16 Left-Rotate(t) 17 Else //needn’t repair 18 Exit 19 Maintain(left[t],false) //repair the left subtree 20 Maintain(right[t],true) //repair the right subtree 21 Maintain(t,false) //repair the whole tree 22 Maintain(t,true) //repair the whole tree为什么Maintain(left[t],true)和Maintain(right[t],false)被省略了呢？您可以在陈启峰论文第六部分的分析中找到答案。
其他可以从论文中获得的信息：每次SBT后树的总深度递减的证明；Maintain的平摊运行时间是O(1)的证明（也就是说你不必担心Maintain这个递归过程是否会永不停止）等。
基本操作
查找
SBT的查找操作与普通BST完全相同。下面的过程将返回指向目标节点的指针。Search(x,k) 1 if x=NULL or k=key[x] //找到了目标节点或目标节点不存在则返回x 2 then return x 3 if k<key[x] 4 then return Search(left[x],k) 5 else return Search(right[x],k)
取大/取小
由于SBT本身已经维护了size，因此这两项可用Select操作完成。后继
SBT的后继操作与普通BST完全相同。前趋
SBT的前趋操作与普通BST完全相同。它与上面的后继操作对称。插入
SBT的插入操作很简单。它仅仅比普通BST的多出了一个Maintain操作和对s的简单维护。下面这个过程将一个节点v插入SBT中。Insert (t,v) 1 If t=0 then 2 t ← v 3 Else 4 s[t] ← s[t]+1 5 If v<key[t] then 6 Insert(left[t],v) 7 Else 8 Insert(right[t],v) 9 Maintain(t,v≥key[t])
删除
与普通维护size域的BST删除相同。关于无需Maintain的说明by sqybi：
在删除之前，可以保证整棵树是一棵SBT。当删除之后，虽然不能保证这棵树还是SBT，但是这时整棵树的最大深度并没有改变，所以时间复杂度也不会增加。这时，Maintain就显得是多余的了。
动态顺序统计操作
由于SBT本来就是靠着size域来维持平衡的，当我们进行动态顺序统计操作时，我们就无需去“额外”维护一个size域来进行数据结构的扩张。这样，以下操作就与其他高级BST扩张后的动态顺序统计操作完全一样了。检索具有给定排序的元素
下面这个过程将返回一个指向以x为根的子树中包含第i小关键字的节点的指针。Select(x,i) 1 r ← size[left[x]] + 1 2 if(i=r) 3 then return x 4 else if i<r 5 then return Select(left[x],i) 6 else return Select(right[x],i-r)
沒有留言:
張貼留言