本文共 2486 字，大约阅读时间需要 8 分钟。
转载：http://www.clarkok.com/blog/?p=347#more-347
采取网友建议，写一下SB Tree。
============================================================================
所谓SB，并不是傻X，而是Size Balanced的意思的。本人也比较建议使用，因为写起来比较简单。这种树形结构有一个特点，对于每一个节点，它的左右子树大小（可以单纯地理解为节点数量）相等或只相差一。
type point = ^node; node = record l,r : point; x,s : longint; end;var root,null : point; tmp : point;procedure init;begin new(null); null^.x:=-maxlongint; null^.s:=0; null^.l:=null; null^.r:=null; root:=null;end;
这跟其他几种树结构差不多，多维护一个变量s(size)，保存以该节点为根的子树的大小。显然的，空子树的大小为0。
PS. 关于旋转请参照。
插入非常简单，先将节点插到正确的位置，然后递归返回时通过旋转调整树的大小。如图：
对于这棵树，插入1：
插到对应的位置：
旋转之后（这里只旋转5，因为2，3节点都是满足要求的）：
我们仍然写成函数：
function add(now:point;x:longint):point;begin if now = null then // 找到了叶子节点 begin new(now); now^.l:=null; now^.r:=null; now^.s:=1; now^.x:=x; exit(now); end; if now^.x >x then begin now^.l:=add(now^.l,x); inc(now^.s); if now^.l^.s > now^.r^.s+1 then // 需要旋转 begin now^.s:=now^.r^.s+now^.l^.r^.s+1; now^.l^.s:=now^.s+now^.l^.l^.s+1; exit(TurnLeft(now)); end; exit(now); end else begin now^.r:=add(now^.r,x); inc(now^.s); if now^.r^.s > now^.l^.s+1 then begin now^.s:=now^.l^.s+now^.r^.l^.s+1; now^.r^.s:=now^.s+now^.r^.r^.s+1; exit(TurnRight(now)); end; exit(now); end;end;
跟AVL一样的思想，旋转到叶子然后删除，并选Size大的子树旋转。住是什么的也参照AVL吧。
function del(now:point;x:longint):point;begin if now = null then exit(null); if now^.x = x then if now^.l^.s > now^.r^.s then begin now:=TurnLeft(now); now^.r:=del(now^.r,x); dec(now^.s); end else begin if now^.r = null then begin dispose(now); exit(null); end; now:=TurnRight(now); now^.l:=del(now^.l,x); dec(now^.s); end else if now^.x > x then now^.l:=del(now^.l,x) else now^.r:=del(now^.r,x); dec(now^.s); exit(now);end;