Scapegoat Trees 简介

ScapegoatTree 概述

我们研究一种二叉搜索树数据结构——ScapegoatTree。该结构基于一个常见的观念：当出现问题时，人们往往首先寻找一个替罪羊来承担责任。一旦责任明确，就可以让这个替罪羊去解决问题。

ScapegoatTree 通过部分重建操作来保持自身平衡。在一次部分重建操作中，整个子树被拆解并重新构建为一棵完全平衡的子树。将根节点为 u 的子树重建为完全平衡树有多种方法。其中最简单的一种是遍历 u 的子树，将所有节点收集到数组 a 中，然后递归地使用 a 构建一棵平衡子树。如果令 m = a.length // 2，那么元素 a[m] 成为新子树的根节点，a[0], ..., a[m−1] 递归地存储在左子树中，而 a[m+1], ..., a[a.length−1] 递归地存储在右子树中。

1class ScapegoatTree(BinarySearchTree):
2    def __init__(self):
3        super(ScapegoatTree, self).__init__()
4        self._initialize()
5        
6    def _initialize(self):
7        self.n = 0
8        self.q = 0
9        
10    def rebuild(self, u):
11        ns = self._size(u)
12        p = u.parent
13        a = new_array(ns)
14        self.pack_into_array(u, a, 0)
15        if p == self.nil:
16            self.r = self.build_balanced(a, 0, ns)
17            self.r.parent = nil
18        elif p.right == u:
19            p.right = self.build_balanced(a, 0, ns)
20            p.right.parent = p
21        else:
22            p.left = self.build_balanced(a, 0, ns)
23            p.left.parent = p

调用 rebuild(u) 的时间复杂度为 $O(\text{size}(u))$。重建后的子树具有最小高度；不存在比它更矮且包含 size(u) 个节点的树。

ScapegoatTree：带有部分重建的二叉搜索树

ScapegoatTree 是一种 BinarySearchTree，除了维护树中节点数量 n 外，还维护一个计数器 q，用于记录节点数量的上界。

1class ScapegoatTree(BinarySearchTree):
2    def __init__(self):
3        super(ScapegoatTree, self).__init__()
4        self._initialize()
5        
6    def _initialize(self):
7        self.n = 0
8        self.q = 0

任何时候，n 和 q 都满足以下不等式：

$$q/2 \leq n \leq q$$

此外，ScapegoatTree 具有对数级别的高度；其高度始终不超过：

$$\tag{1} \log_{3/2} q \leq \log_{3/2}2n < \log_{3/2}n + 2$$

即使有此约束，ScapegoatTree 仍可能看起来相当不平衡。下图所示的树中，q = n = 10，高度为 5，小于 $\log_{3/2} 10 \approx 5.679$。

ScapegoatTree 操作

在 ScapegoatTree 中实现 find(x) 操作，使用标准的二叉搜索树查找算法。其时间复杂度与树的高度成正比，根据 (1) 式，为 $O(\log n)$。

实现 add(x) 操作时，我们首先增加 n 和 q，然后使用通常的二叉搜索树插入算法：搜索 x 的位置，并添加一个新叶子节点 u，使得 u.x = x。此时，我们可能幸运地发现 u 的深度不超过 $\log_{3/2} q$。如果是这样，就无需进一步操作。

然而，有时会出现 $\text{depth}(u) > \log_{3/2} q$。在这种情况下，我们需要降低树的高度。这并不复杂；只有唯一一个节点 u 的深度超过了 $\log_{3/2} q$。为了修复 u，我们从 u 向上遍历至根节点，寻找一个“替罪羊”节点 w。这个替罪羊节点 w 是一个严重失衡的节点，它满足：

$$\frac{\text{size(w.child)}}{\text{size(w)}} > \frac{2}{3}$$

其中 w.child 是从根到 u 的路径上 w 的子节点。我们稍后会证明这样的替罪羊必然存在。目前可以先接受这一点。找到替罪羊 w 后，我们将以 w 为根的子树彻底销毁，并重建为一棵完全平衡的二叉搜索树。我们知道，在添加 u 之前，w 的子树就不是一棵完整的二叉树。因此，重建 w 后，树的高度至少减少 1，从而使 ScapegoatTree 的高度再次不超过 $\log_{3/2} q$。

1class ScapegoatTree(BinarySearchTree):
2    def __init__(self):
3        super(ScapegoatTree, self).__init__()
4        self._initialize()
5        
6    def _initialize(self):
7        self.n = 0
8        self.q = 0
9        
10    def add(self, x):
11        (u, d) = self.add_with_depth(x)
12        if d > log32(self.q):
13            # 深度超出限制，寻找替罪羊
14            w = u.parent
15            while 3*self._size(w) <= 2*self._size(w.parent):
16                w = w.parent
17            self.rebuild(w.parent)
18        return d >= 0

如果我们忽略寻找替罪羊 w 和重建以 w 为根的子树的代价，则 add(x) 的运行时间主要由初始搜索决定，时间为 $O(\log q) = O(\log n)$。寻找替罪羊和重建的代价将在下一节通过摊销分析进行讨论。

ScapegoatTree 中 remove(x) 的实现非常简单：我们搜索 x 并使用标准的二叉搜索树删除节点算法将其移除。

注意：remove(x) 永远不会增加树的高度。

接下来，我们减少 n，但保持 q 不变。最后，检查是否 $q > 2n$，若是，则将整棵树重建为一棵完全平衡的二叉搜索树，并设置 q = n。

1class ScapegoatTree(BinarySearchTree):
2    def __init__(self):
3        super(ScapegoatTree, self).__init__()
4        self._initialize()
5        
6    def _initialize(self):
7        self.n = 0
8        self.q = 0
9        
10    def remove(self, x):
11        if super(ScapegoatTree, self).remove(x):
12            if 2*self.n < self.q:
13                self.rebuild(self.r)
14                self.q = self.n
15            return True
16        return False

同样地，如果我们忽略重建的代价，remove(x) 操作的运行时间与树的高度成正比，因此为 $O(\log n)$。

让我们创建一个 ScapegoatTree 的实例，然后使用 add() 和 remove() 方法向树中添加和删除值。

1import math
2from utils import new_array
3from binarysearchtree import BinarySearchTree
4# 对数函数
5def log32(q):
6    return int(math.log(q, 1.5))
7# 主类
8class ScapegoatTree(BinarySearchTree):
9    def __init__(self):
10        super(ScapegoatTree, self).__init__()
11        self._initialize()
12    # 初始化函数
13    def _initialize(self):
14        self.n = 0
15        self.q = 0
16    # 删除值的函数
17    def remove(self, x):
18        if super(ScapegoatTree, self).remove(x):
19            if 2*self.n < self.q:
20                self.rebuild(self.r)
21                self.q = self.n
22            return True
23        return False
24    # 添加值的函数（带深度）
25    def add_with_depth(self, x):
26        u = self._new_node(x)
27        w = self.r
28        if w == self.nil:
29            self.r = u
30            self.n += 1
31            self.q += 1
32            return (u, 0)
33        done = False
34        d = 0
35        while not done:
36            if x < w.x:
37                if w.left == self.nil:
38                    w.left = u
39                    u.parent = w
40                    done = True
41                else:
42                    w = w.left
43            elif x > w.x:
44                if w.right == self.nil:
45                    w.right = u
46                    u.parent = w
47                    done = True
48                else:
49                    w = w.right
50            else:
51                return (None, -1)
52            d += 1
53        self.n += 1
54        self.q += 1
55        return (u, d)
56    # 正常添加值的函数
57    def add(self, x):
58        (u, d) = self.add_with_depth(x)
59        if d > log32(self.q):
60            # 深度超出，寻找替罪羊
61            w = u.parent
62            while 3*self._size(w) <= 2*self._size(w.parent):
63                w = w.parent
64            self.rebuild(w.parent)
65        return d >= 0
66    # 重建树的函数
67    def rebuild(self, u):
68        ns = self._size(u)
69        p = u.parent
70        a = new_array(ns)
71        self.pack_into_array(u, a, 0)
72        if p == self.nil:
73            self.r = self.build_balanced(a, 0, ns)
74            self.r.parent = nil
75        elif p.right == u:
76            p.right = self.build_balanced(a, 0, ns)
77            p.right.parent = p
78        else:
79            p.left = self.build_balanced(a, 0, ns)
80            p.left.parent = p
81    # 将节点打包进数组的函数
82    def pack_into_array(self, u, a, i):
83        if u == self.nil:
84            return i
85        i = self.pack_into_array(u.left, a, i)
86        a[i] = u
87        i += 1
88        return self.pack_into_array(u.right, a, i)
89    # 构建平衡树的函数
90    def build_balanced(self, a, i, ns):
91        if ns == 0:
92            return self.nil
93        m = ns // 2
94        a[i+m].left = self.build_balanced(a, i, m)
95        if a[i+m].left != self.nil:
96            a[i+m].left.parent = a[i+m]
97        a[i+m].right = self.build_balanced(a, i+m+1, ns-m-1)
98        if a[i+m].right != self.nil:
99            a[i+m].right.parent = a[i+m]
100        return a[i+m]
101
102if __name__ == "__main__":
103    # 创建对象
104    tree = ScapegoatTree()
105    # 添加值
106    tree.add(5)
107    tree.add(3)
108    tree.add(8)
109    tree.add(1)
110    tree.add(4)
111    tree.add(7)
112    tree.add(9)
113    print("添加值后的树：")
114    iterator = iter(tree)
115    for i in iterator:
116        print(i, end=' ')
117    print()
118    # 删除值
119    tree.remove(4)
120    print("删除4后的树：")
121    iterator = iter(tree)
122    for i in iterator:
123        print(i, end=' ')