Size Balanced Tree(SBT)

April 11, 2007 18:34 Filed under 技术杂谈

许多人(尤其指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没有被指控谋杀的话…

撤远了,就到这里.