数据结构-二叉搜索树

BST

• 循关键码查询，综合向量和列表的优点
• 顺序性：任意节点不小于右后代，不大于左后代
• 中序查找输出单调非减

查找

减治，从根节点出发，将当前节点与目标数据比较，直到抵达目标节点或空树。 时间复杂度为 $O(h)$ 过程可视为有序向量的二分查找

插入

先 search 到插入位置 _p，再创建新节点作为 _p 的孩子。

删除

单分支

删去节点后用唯一子树代替。

双分支

找到对应节点的右子树的最小节点或左子树的最大节点（直接后继或直接前驱），将这两个节点交换，再删去对应节点，此时问题转化为单分支删除。

• 交换时破坏了顺序性

平衡

BST 的查找、插入和删除时间最坏情况下均正比于高度 有多可能出现最坏情况？

• 随机生成：假设各个排列出现的概率相等，按该次序插入，计算得平均高度为 $\Theta (\log n)$

• 随机组成：假设各种组成的 BST 形状出现的概率相等，共有 $S(n)=catalan(n)$ 颗，计算得平均高度为 $\Theta (\sqrt{n})$

• 实际上，理想随机在实际情况中难以出现，各种局部性、周期性、单调性、关联性等使得朴素实现的 BST 容易退化

• 理想平衡：树高为 $\lfloor \log n\rfloor$

• 渐近平衡：树高渐近为 $O(\log n)$

旋转

只需 $O(1)$ 时间 旋转后全树的高度变化不超过 1 经过不超过 $O(n)$ 次旋转，等价的 BST 均可相互转化

AVL 树

平衡因子

• 定义为左子树高度-右子树高度
• 要求任意节点的平衡因子绝对值小于等于 1

渐近平衡

$n$ 个节点组成的 AVL 树，高度 $h=O(\log n)$ 等价地，高度为 $h$ 的树，规模 $n=\Omega ({\varphi }^h)$ 证明： 设高度为 $h$ 的树的规模最少为 $S(h)$ 有 $S(h)=1+S(h-1)+S(h-2)$ $S(h)+1=S(h-1)+1+S(h-2)+1$ $S(h)=fib(h+3)-1=\Omega ({\varphi }^h)$ 这样固定高度下最小的 AVL 树称为 Fibonaccian Tree

• AVL 树的高度约为 $1.44\log n$

失衡

• 插入：从祖父开始，每个祖先都有可能失衡，且可能同时失衡
• 删除：从父亲开始，每个祖先都有可能失衡，但瞬时至多一个

插入

单旋

同时可有多个祖先失衡，找到第一个失衡的祖先，做一次旋转，全树复衡。

双旋

同时可有多个祖先失衡，先做一次旋转转换为单旋，再做一次旋转复衡。

删除

瞬时至多一个失衡节点，旋转复衡后子树高度未必复原，失衡可能持续向上传播，最多需做 $O(\log n)$ 次调整。 双旋情况可先做一次旋转后转换为单旋情况。

342 重构

AVL 树的重平衡总得来讲就是3 个节点、4 个子树的重构，且外侧的2 个子树相对位置不会改变。 针对重平衡过程中可能的 4 种情况，分别调用重构函数即可。

优缺点

• 优点：最坏情况下时间复杂度都不过 $O(\log n)$，空间复杂度为 $O(n)$
• 缺点：删除操作最坏情况下需旋转 $\Omega (\log n)$ 次，单次动态调整后，全树拓扑结构变化量高达 $O(\log n)$，对并发有影响