平衡树

这两天学了三种平衡树，我在这里简单recap一下

AVL tree

AVL tree的平衡条件是，如果左右节点的高度差>1，则进行rotation。
我们以某节点A left heavy为例，rotation会分成三种情况，如过左子树left heavy或者equally heavy，则直接right rotate。如果左子树right heavy，则先对左子树进行left rotate再对A进行right rotate。

插入：插入后检测这个节点到根节点的路径上有没有不平衡的点，最多进行两次rotate（只对第一个不平衡点操作），因为rotate相当于减少height，和插入操作拮抗。
删除：对于需要删除的节点u：1）如果有两个child，首先找到其predecessor或successor v，将v和u交换，然后删除u。可以保证v最多只有一个child。2）如果有一个child，直接删除并将其child接上即可。3）如果是叶子节点，直接删除。
最后检测这个节点到根节点路径上有没有不平衡的点，要对所有不平衡点进行rotate，因为删除操作和rotate操作都是减少height的。

Scapegoat tree（替罪羊树）

scapegoat tree的平衡条件是，我们取一个平衡常数 $\alpha$ ，同时给每个节点维护其子树重量。如果某个子节点的weight > 当前节点的weight $\alpha \in (0, 1)$ 则对整个子树进行重构。

我们首先证明替罪羊树的平衡性。由于每一个子节点最多只包含整棵树的 $\alpha$ 比例的weight，所以高度最多为 $log_{\frac{1}{\alpha}}n$ 。

插入：普通平衡树的插入，并更新节点weight。递归结束后用类似查找节点的方法，从根节点向下依据路径找到第一个非balance节点，进行重构。重构完就不需要继续寻找路径了。这里要注意，必须从根节点向下，因为重构子树并不能影响祖先的balance，而重构祖先可以保证子树balance
删除：不需要真正地删除节点（惰性删除），只要更新weight即可。增加实际的删除操作并不会增加时间复杂度，但是增加代码复杂度。更新weight结束后用插入同样的方法找到需要重构的节点。
重构：对于节点A重构。已知A的所有节点都是符合BST的性质的，in-order便利可以导出排序好的数组。通过这个数组可以用O(n)的时间重构出一棵完美的平衡子树。

B tree ((a,b) tree)

B tree并不符合传统二叉树的结构。B tree的每个节点有 $n \in (a-1, b-1)$ 个key，划分了 $n + 1$ 个子节点，如下图所示：

规则(invariant):

每个非叶子节点最多有b个子节点
除了root的非叶子节点，每个节点最少有 $a = \lceil{b}\rceil$ 个子节点，根节点最少有2个子节点（如果根节点非叶子节点）。
有k个子节点的非叶子节点拥有k-1个元素，且升序排列，满足 $k[i] \lt k[i + 1]$
所有叶子节点都在同一层。
插入：所有插入都在叶子节点曾，不存在向叶子节点的子节点插入。这就是与普通BST最不同的地方，它是向上发展而非向下延展。由于每个节点最多b - 1个key，所以如果超过了则从中间将这个节点的所有key分成左右两部分，把中间的key拿出来归入父节点中，左右两部分分别作为一个节点。如果到根节点还是满的，则将根节点也给分成左右两部分，将中间的节点单独拿出来作为父节点。
删除：如果删除的节点有子节点，则将左子节点的最右或右子节点的最左放入当前key，然后将要删除的key递归到叶子节点后再删除。如果删除后某节点最小key个数小于a，则将其与左右某个节点合并，并且下移相应父节点key。如果下移后父节点key不足，则递归进行合并。

B tree的优势

由于硬盘读取和内存读取一般是以16kb一个block来读取的，所以这种构造一次性可以读取一个很长的数组，而B tree每一个节点正好是数组形式，且层数显著降低。且通过改变节点的key数量可以充分利用缓存机制进行优化。

Treap/笛卡尔树

Treap的本质是笛卡尔树，即key为一个<k,w>对，构造一棵树使k符合树的性质，而w符合堆的性质。可以证明一定能且仅能构造一棵树。形象证明如下：

（图源自维基百科）

最上面的array是树的中序遍历(in-order traverse)，通过对层高的比对可以将整棵树的节点分层。例如，最小的是1，1绝对是第一层，3和5分别是1的两边的最小值，所以1的两个子节点为3和5。以此递归类推。

关于树高的证明请见https://oi-wiki.org/ds/treap/，我还没有仔细研究过。

旋转treap

插入：用和AVL tree一样的方式进行旋转，只是在这棵树中，当我们将新的节点插到叶子结点之后，是通过旋转将其旋转到正确的高度。即u.father.w > u.w > u.children.w
删除：同样是和successor或者predecessor交换并删除，交换后肯定不符合堆的性质，所以要进行旋转来维护性质。如果u.leftChild.w < u.rightChild.w，则将u.leftChild和u交换。反之亦然。

无旋treap

to-do: FHQ tree

KD Tree (K-Dimension Tree)

图源：OI-wiki

这个树维护了整个k维的分割。为了简单，我们在这里以2-D Tree为例。

构建：KD Tree是没办法一个点一个点进行插入的，因为插入点之后x，y轮流分割的invariant会被改变。一般需要修改，则积累到一定量或者需要使用之后再进行重构。
对于一次构造操作，我们会轮流对于x, y进行分割。每次分割选取当前区间的median，median可以通过QuickSelect算法每一层都是O(n)，总时间为O(nlogn)。
1. 查询：KD Tree的作用是在给定的n维立方体中查询立方体内所有点的集合信息（例如和，最大值等）。KD Tree的每一个点都代表着一个空间立方体。查询的时间是 $O(\sqrt{n})$ 的，因为我们相当于把平面分成了n个小方块，其中最多有 $\sqrt{n}$ 个小方块。我们如果考虑较大方块的贡献，也是无法超过 $O(\sqrt{n})$ 。
2. 插入，删除：to-do

平衡树