PS-06 Binary Search Tree

1. 二叉搜索树

在中序遍历的意义下，搜索树必然单调非降

接口

• search()
• insert()
• remove()

search

采取减而治之的策略，类似在做二分查找

insert

借助search()确定插入位置，然后由插入位置的父亲生出新的孩子

插入位置都在叶子节点

remove

定位目标节点，当目标节点只有一个子树时，直接用子树替代；当有两个子树时，找到直接前驱或后继，与目标节点替换位置，然后在新的位置删除目标节点

期望树高

从 $n$个元素随机排列的意义上，生成树的期望高度为 $logn$

从 $n$个节点随机生成一棵树的意义上，树的种类数是一个卡特兰数，期望树高为 $\sqrt{n}$

从理想随机的角度来看，二叉搜索树的树高是可以接受的，但是理想随机很难存在，原因有：

• 局部性
• 关联性
• 单调性
• 周期性

因此还需要做平衡化处理

2. 平衡树

zig：顺时针旋转

zag：逆时针旋转

单次恢复平衡所需时间为 $O(logn)$

AVL树

要求每个节点的两个子树高度相差不超过1，左右子树高度差为平衡因子

渐近平衡

考察高度为 $h$的AVL树，总节点个数为 $S(h)$

则 $S(h)=1+S(h-1)+S(h-2)$

$S(h)+1=S(h-1)+1+S(h-2)+1$

即 $fib(n+3)=fib(n+2)+fib(n+1)$

所以 $S(h)=fib(n+3)-1$是指数规模的，反过来 $n$个节点构成的AVL树的树高为对数量级

插入

插入一次之后失衡的最低者不会低于插入节点的祖父，也有可能引发连锁失衡，但是经过一次旋转之后就可以全局恢复

删除

有可能删除节点的父亲就失衡了，但是经过一次旋转恢复后，祖先可能失衡从而引发连锁的效应，因此恢复需要 $O(logn)$的时间

3-4重构