Size Balanced Tree
陈启峰 (Farmer John) 中国广东纪念中学 Email:344368722@QQ.com
2006.12.29
摘要
这篇论文将展现一个独特巧妙的策略，动态地维护二叉搜索树（Binay Search Trees，缩写为BST），并且它在最坏的情况下也有着良好的期望运行速度。Size Balanced Tree，顾名思义，这是一棵通过大小（Size）域来维持平衡的二叉搜索树。
这是一种简单、高效并且在各方面都通用的数据结构。
这也是一种很容易被语言工具表述的数据结构，它有着简单明了的定义，和令人惊叹的运行速度，而且你会惊讶于它简单的证明。
[1]
这是目前为止速度最快的高级二叉搜索树。
此外，它比其它一些知名的高级二叉搜索树要快得多，并且在实践中趋于完美。 它不仅支持典型的二叉搜索树操作，而且也支持Select和Rank。
关键字
Size Balanced Tree
SBT Maintain
翻译 By 竹子的叶子
文档经过处理，可以使用“视图”——“文档结构图”来方便阅读。
希望大家不要随便修改，谢谢！
陈启峰 WC2007论文 数据结构 Size Balanced Tree 第1页
1 介绍
在展现Size Balanced Tree之前，有必要详细说明一下二叉搜索树的旋转，左旋（Left-Ratote）和右旋（Right-Ratote）。
1.1 二叉搜索树
二叉搜索树是一种非常重要的高级数据结构，它支持很多动态操作，其中包括搜索（Search），取小（Minimum），取大（Maximun），前驱（Predecessor），后继（Successor），插入（Insert）和删除（Delete）。它能够同时被当作字典和优先队列使用。
二叉搜索树是按照二叉树结构来组织的，树中的每个节点最多只有两个儿子，二叉搜索树中关键字的储存方式总是满足以下二叉搜索树的性质：
设x是二叉搜索树中的一个结点，那么x的关键字不小于左子树中的关键字，并且不大于右子树中的关键字。 对于每一个结点t，我们使用left[t]和right[t]来储存它两个儿子的指针[2]，并且我们定义key[t]来表示结点t用来做比较的值。另外，我们增加s[t]，表示以t为根的子树的大小（Size），维持它成为这棵树上结点的个数。特别地，当我们使用0时，指针指向一棵空树，并且s[0]=0。
1.2 旋转
为了保持二叉搜索树的平衡（而不是退化成为链表），我们通常通过旋转改变指针结构，从而改变这种情况。并且，这种旋转是一种可以保持二叉搜索树特性的本地运算[3]。
Y 右旋（Right-Ratote） X Y C 左旋（Left-Ratote） A X A B B C
图 1.1 图 1.1：左旋Left-Ratote(x)操作通过更改两个常数指针将左边两个结点的结构转变成右边的结构，右边的结构也可以通过相反的操作Right-Ratote(x)来转变成左边的结构。 1.2.1 右旋的伪代码
右旋操作假定左儿子存在。
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
1.2.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
2 Size Balanced Tree
Size Balanced Tree（SBT）是一种通过大小（Size）域来保持平衡的二叉搜索树。它支持许多运算时间级别为O(logn)的主要操作：
陈启峰 WC2007论文 数据结构 Size Balanced Tree Insert(t,v) Delete(t,v) Find(t,v) Rank(t,v) Select(t,k) Pred(t,v) Succ(t,v) 在以t为根的SBT中插入一个关键字为v的结点。 从以t为根的SBT中删除一个关键字为v的结点，如果树中没有一个这样的结点，删除搜索到的最后一个结点。 查找并返回结点关键字为v的结点。 返回v在以t为根的树中的排名，也就是比v小的那棵树的大小（Size）加一。 返回在第k位置上的结点。显然它包括了取大（Maximum）和取小（Minimun），取大等价于Select(t,1)，取小等价于Select(t,s[t])。 返回比v小的最大的数。 返回比v大的最小的数。 第2页 通常SBT的每一个结点包含key，left，right和size等域。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]]]
T L R A B 图 2.1 C D
图2.1：结点L和R分别是结点T的左右儿子。子树A、B、C和D分别是结点L和R各自的左右子树。 符合性质a和性质b，s[A],s[B]?
s[R]&s[C],s[D]?s[L]
3 Maintain
如果我们要在一个BST插入一个关键字为v的结点，通常我们使用下列过程来完成任务。
Simple-Insert (t,v) 1 If t=0 then
2 t ← NEW-NODE(v) 3 Else
4 s[t] ← s[t]+1 5 If v 6 Simple-Insert(left[t],v) 7 Else 8 Simple-Insert(right[t],v) 在执行完简单的插入之后，性质a或性质b可能就不满足了，于是我们需要调整SBT。 SBT中最具活力的操作是一个独特的过程，Maintain。 Maintain(t)用来调整以t为根的SBT。假设t的子树在使用之前已经都是SBT。 由于性质a和性质b是对称的，所以我们仅仅详细的讨论性质a。 情况1：s[left[left[t]]] ?s[right[t]] 陈启峰 WC2007论文 数据结构 Size Balanced Tree 插入后发生s[A]?s[R]正如图2.1，我们可以执行以下的指令来修复SBT。 （1）首先执行Right-Ratote(t)，这个操作让图2.1变成图3.1； 第3页 L A T B R C 图3.1 D 图3.1：所有结点的描述都和图2.1一样 （2）在这之后，有时候这棵树还仍然不是一棵SBT，因为s[C]?s[B]或者s[D]?s[B]也是可能发生的。所以就有必要继续调用Maintian(t)。 （3）结点L的右子树有可能被连续调整，因为有可能由于性质的破坏需要再一次运行Maintain(t)。 [left[t]]]?情况2：s[right 在执行完Insert(left[t],v)后发生s[B]?s[right[t]] s[R]，如图3.2，这种调整要比情况1复杂一些。我们可以执行下面的操作来修复。 T L R A B C D E F 图3.2 图3.2：除了E、B、F以外，其他结点都和图2.1种的定义一样。E、F是结点B的子树。 （1）在执行完Left-Ratote(L)后，图3.2就会变成下面图3.3那样了。 T B L R F E C D A 图3.3 图3.3：所有结点的定义都和图3.2相同
相关推荐：
loading