TREAP树(树堆)
1980年Jean Vuillemin在解决范围搜索的问题时提出笛卡尔树,其特点是节点包含2个关键字。之后Edward McCreight提出一种基于笛卡尔树的结构并称之为Treap树,这是Tree和Heap的合成词,所以Treap也译为树堆。1989年Raimund Seidel和Cecilia R. Aragon利用带随机化策略的Treap树实现了BST的功能,在此之后Treap树一般用于指代这种结构。Treap树不是严格意义的自平衡二叉树,但其相比BST能在更一般的条件下保证二叉树的期望高度是\(O(\lg{n})\)。这里直接给出Treap树的定义,首先Treap节点相比前文的BST节点要额外存储一个堆关键字\(hkey\),Treap树的运算功能和前文的BST一致,但每次运算开始前后除了要保证二叉树是BST还要保证任意节点的\(hkey\)都不大于其所有后代的\(hkey\),最后规定Treap树的运算为如下的步骤:
1) \(find(k)\):与BST的\(find(k)\)完全一致(按之前讨论BST的文章中的步骤);
2) \(insert(k)\):先执行BST的\(insert(k)\)得到新节点\(x\)(按之前讨论BST的文章中的步骤),并初始化\(x\)的\(hkey\)为一个尽可能大的范围内的随机数(仅为了降低其重复的概率)。然后开始一个迭代过程,在每轮迭代中,若此时\(x\)无父亲或\(x\)的\(hkey\)不小于其父亲的,则退出迭代,否则通过一次左旋转或右旋转使\(x\)取代其父亲的位置,然后继续下一轮迭代;
3) \(remove(k)\):先执行BST的\(find(k)\)得到待删除节点\(x\)(按之前讨论BST的文章中的步骤),若查找失败则退出,否则开始一个迭代过程,在每轮迭代中,若\(x\)是叶节点,则删除\(x\)并退出迭代,否则找到此时\(x\)的\(hkey\)较小的孩子\(x’\),通过一次左旋转或右旋转使\(x’\)取代\(x\)的位置,然后继续下一轮迭代;
不难验证上述步骤能正确维护“任意节点的\(hkey\)都不大于其所有后代的\(hkey\)”。注意到Treap树有一定概率能在每次运算后都刚好是“链表”形态,所以其不可能是严格意义的自平衡二叉树,其各个运算也不可能有\(O(\lg{n})\)的摊还代价。另外上述定义所给出的Treap树也称为小根堆Treap树,若修改上述运算步骤使其维护“任意节点的\(hkey\)都不小于其所有后代的\(hkey\)”,则称之为大根堆Treap树。实际堆(heap)本身也是种数据结构,大根堆和小根堆都是关于堆的概念,之后有文章专门讨论堆。
TREAP树的时间复杂度
下面从统计的角度分析Treap树的各个运算的代价。首先假定\(hkey\)的取值范围大到\(hkey\)不可能重复,并且\(key\)也不重复。考虑对空树\(T\)执行由上述运算所组成的运算序列,可以认为该运算序列是已知的,于是在执行完运算序列后\(T\)中的所有节点及其它们的\(key\)就都是已知的,但由于\(hkey\)值是随机的,所以可认为\(T\)的形态是未知的,但此时还是能按照\(key\)值的升序将\(T\)中的所有节点依次计为\(x_1,x_2…x_n\)(\(n\geq 2\))。接下来通过给出一组命题并证明这些命题来讨论:
a1) 若\(i\neq j\)且\(i,j\)的值都属于\([1,n]\)则有“\(x_i\)是\(x_j\)的祖先 \(\Leftrightarrow\) \(x_i\)是\(x_{min(i,j)},x_{min(i,j)+1}…x_{max(i,j)}\)中\(hkey\)最小的节点”;
证明:将问题划为如下情况讨论:
1) \(x_i\)是树根:显然(a1)左右两边都成立;
2) \(x_j\)是树根:显然(a1)左右两边都不成立;
3) \(x_i,x_j\)都不是树根:继续分情况讨论如下:
3.1) \(x_i\)非\(x_j\)的祖先且\(x_j\)非\(x_i\)的祖先:设\(x_k\)是\(x_i,x_j\)的最近公共祖先,则\(x_k\)的\(hkey\)一定小于\(x_i\)的\(hkey\)。注意到\(x_i,x_j\)一定分别位于\(x_k\)的两个子树,否则\(x_k\)就不是最近的公共祖先,故\(min(i,j)<k<max(i,j)\)。综上(a1)左右两边都不成立;
3.2) \(x_j\)是\(x_i\)的祖先:根据BST的性质,若\(j>i\)则\(x_{min(i,j)}…x_{max(i,j)-1}\)都在\(x_j\)左子树,若\(i>j\)则\(x_{min(i,j)+1}…x_{max(i,j)}\)都在\(x_j\)右子树。无论如何\(x_j\)都是\(x_{min(i,j)},x_{min(i,j)+1}…x_{max(i,j)}\)中\(hkey\)最小的节点。综上(a1)左右两边都不成立;
3.3) \(x_i\)是\(x_j\)的祖先:根据BST的性质,若\(i>j\)则\(x_{min(i,j)}…x_{max(i,j)-1}\)都在\(x_i\)左子树,若\(j>i\)则\(x_{min(i,j)+1}…x_{max(i,j)}\)都在\(x_i\)右子树。无论如何\(x_i\)都是\(x_{min(i,j)},x_{min(i,j)+1}…x_{max(i,j)}\)中\(hkey\)最小的节点。综上(a1)左右两边都成立;
由于在任何情况下(a1)的左右两边要么同时成立要么同时不成立,所以(a1)的左右两边是一对充要条件。
a2) 此时\(T\)中的任意节点\(x_k\)的期望高度都以\(2\ln{n}+1\)为上界;
证明:设\(i\neq j\)且\(i,j\)的值都属于\([1,n]\),\(Y_{i,j}\)为一组指示器型随机变量,若\(x_i\)是\(x_j\)的祖先则\(Y_{i,j}=1\),否则\(Y_{i,j}=0\)。注意到节点的高度为该节点的祖先数+1,所以\(x_k\)的高度\(H_k = \sum_{x=1}^{k-1} Y_{x,k} + \sum_{x=k-1}^{n} Y_{x,k} + 1\),对该式两边求期望并利用期望的线性性可得\(E[H_k] = \sum_{x=1}^{k-1} E[Y_{x,k}] + \sum_{x=k+1}^{n} E[Y_{x,k}] + 1\)。根据(a1)有\(E[Y_{i,j}]\)等于“\(x_i\)是\(x_{min(i,j)}…x_{max(i,j)}\)中\(hkey\)最小的节点”的概率,由于每个\(hkey\)都是随机和独立的,故\(x_{min(i,j)}…x_{max(i,j)}\)中每个节点都等可能的会成为它们中\(hkey\)最小的节点,于是可得到\(E[Y_{i,j}]=\frac{1}{|i-j|+1}\),进而有\(E[H_k]=\sum_{x=1}^{k-1} \frac{1}{|x-k|+1} + \sum_{x=k+1}^{n} \frac{1}{|x-k|+1} + 1 = \sum_{y=2}^{k} \frac{1}{y} + \sum_{y=2}^{n-k+1} \frac{1}{y} + 1\)。做进一步的放缩并利用积分可得到\(E[H_k] \leq 2 \sum_{y=2}^{n} \frac{1}{y}+1 < 2\int_{1}^{n} \frac{1}{y}dy + 1 = 2\ln{n} + 1\)。
至此根据(a2)可确定\(T\)的期望高度也以\(2\ln{n}+1\)为上界,并且对于\(n=1\)这个界同样也是正确的。换句话说如果从空树开始不停执行上述运算,则每次运算的期望代价都是\(O(\lg{N})\),其中\(N\)是每次运算开始时的二叉树节点数。另外前面为方便讨论假设\(key\)不重复,但即使\(key\)重复也不影响上述分析的正确性,简单来说如果对空树执行运算序列\(L\)后会出现重复的\(key\),则必然存在与\(L\)步骤“等价”且不导致重复\(key\)的运算序列,换句话说重复的\(key\)并不能实际影响到运算步骤本身。
总结与实现
Treap树的运算步骤本身很简单,唯一要注意的是在程序中无法保证\(hkey\)重复的概率为0,通常会用2种方法生成\(hkey\),一种是在整个int数据类型的范围中取值,另一种是生成随机浮点数。最后给出Treap树的程序实现如下,为了方便这里直接使用Python内置的random.random生成0~1之间的随机浮点数。其他未提到的细节见程序与注释。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 | from random import random class Node: def __init__(self, key): self.key = key self.parent = None self.left = None self.right = None class Treap: def __init__(self): self.root = None def _rightRotate(self, n): m = n.left n.left = m.right m.right = n if not n.parent: self.root = m elif n.parent.left is n: n.parent.left = m else: n.parent.right = m m.parent = n.parent n.parent = m if n.left: n.left.parent = n def _leftRotate(self, n): m = n.right n.right = m.left m.left = n if not n.parent: self.root = m elif n.parent.left is n: n.parent.left = m else: n.parent.right = m m.parent = n.parent n.parent = m if n.right: n.right.parent = n def _bstFind(self, k): root = self.root while root: if k == root.key: return root elif k < root.key: root = root.left else: root = root.right return None def find(self, k): return self._bstFind(k) def _bstInsert(self, k): if not self.root: self.root = Node(k) return self.root root = self.root while root: if k < root.key: if not root.left: root.left = Node(k) root.left.parent = root return root.left root = root.left else: if not root.right: root.right = Node(k) root.right.parent = root return root.right root = root.right def insert(self, k): x = self._bstInsert(k) x.hkey = random() # 初始化hkey while x.parent and x.parent.hkey > x.hkey: if x.parent.left is x: self._rightRotate(x.parent) else: self._leftRotate(x.parent) return x def remove(self, k): x = self._bstFind(k) if not x: return x while x.left or x.right: if not x.left: self._leftRotate(x) elif not x.right: self._rightRotate(x) elif x.left.hkey > x.right.hkey: self._leftRotate(x) else: self._rightRotate(x) if x.parent: if x.parent.left is x: x.parent.left = None else: x.parent.right = None x.parent = None else: self.root = None return x |