7.2 BBST

理想平衡
节点数目固定时，兄弟子树高度越接近（平衡），全树越趋向于更低
由n个节点组成二叉树，高度不低于 $\left \lfloor \log_{2}{n} \right \rfloor$ ，恰为 $\left \lfloor \log_{2}{n} \right \rfloor$ 时，称作理想平衡
理想平衡出现概率极低，维护成本过高
高度渐进不超过O(logn)，即可称作适度平衡
适度平衡的BST，称作平衡二叉搜索树(BBST)

等价BST
联接关系不尽相同，承袭关系可能颠倒
中序遍历序列完全一致，全局单调非降

平衡因子
balFac(v) = height(lc(v)) - height(rc(v))
G.Adelson-Velsky & E. Landis: ∀ v, | balcFac(v) | ≤ 1
height(AVL) = O(logn)
高度为h的AVL树，至少包含S(h) = fib(h + 3) - 1个节点

AVL接口

#define Balanced(x) \ // 理想平衡
    (stature((x).lChild) == stature((x).rChild))
#define BalFac(x) \ // 平衡因子
    (stature((x).lChild) - stature((x).rChild))
#define AvlBalanced(x) \ // AVL平衡条件
    ((-2 < BalFac(x)) && (BalFac(x) < 2))

tempalte <typename T> class AVL: public BST<T> { // 由BST派生
public: // BST::search()等接口可直接沿用
    BinNodePosi(T) insert(const T &); // 插入重写
    bool remove(const T &); // 删除重写
}

插入节点
插入一个节点可能导致同时有多个失衡节点，g经单旋或双旋调整后复衡，子树高度复原，全树复衡

template <typename T> BinNodePosi(T) AVL<T>::insert(const T & e) {
    BinNodePosi(T) & x = search(e);
    if (x)
        return x;
    x = new BinNode<T>(e, _hot);
    _size++;
    BinNodePosi(T) xx = x; // 若目标不存在，则创建x
    for (BinNodePosi(T) g = x -> parent; g; g = g -> parent) { // 从x的父节点出发逐层向上检查
        if (!AvlBalanced(*g)) { // 若发现g失衡，则通过调整恢复平衡
            FromParentTo(*g) = rotateAt(tallerChild(tallerChild(g)));
            break; // g复衡后，局部子树高度必然复原，调整结束
        } else {
            updateHeight(g); // 否则只需更新高度
        }
    }
    return xx; // 返回新节点，至多需要一次调整
}

删除节点
删除一个节点可能导致同时至多一个失衡节点g，可能是x的父节点_hot
g经单旋调整后复衡，子树高度未必复原，全树仍可能失衡
由于有失衡传播现象，可能需要O(logn)次调整

template <typename T> bool AVL<T>::remove(const T & e) {
    BinNodePosi(T) & x = search(e);
    if (!x)
        return false;
    removeAt(x, _hot);
    _size--; // 若目标存在，则在按BST规则删除后，_hot以上可能失衡
    for (BinNodePosi(T) g = _hot; g; g = g -> parent) { // 从_hot出发逐层向上检查
        if (!AvlBalanced(*g)) // 若发现g失衡，则通过调整恢复平衡
            g = FromParentTo(*g) = rotateAt(tallerChild(tallerChild(g)));
        updateHeight(g); // 更新高度
    } // 可能需要Ω(logn)次调整，无论是否经过调整，全树高度均可能下降
    return true; // 删除成功
}

3+4重构
设g(x)为最低失衡节点，考察三代g ~ p ~ v，按中序遍历次序重命名a < b < c
拥有互不相交的4个子树（可能为空），按中序遍历次序重命名T₀ < T₁ < T₂ < T₃

template <typename T> BinNodePosi(T) BST<T>::connect34(BinNodePosi(T) a, BinNodePosi(T) b, BinNodePosi(T) c, BinNodePosi(T) T0, BinNodePosi(T) T1, BinNodePosi(T) T2, BinNodePosi(T) T3) {
    a -> lChild = T0;
    if (T0)
        T0 -> parent = a;
    a -> rChild = T1;
    if (T1)
        T1 -> parent = a;
    updateHeight(a);
    c -> lChild = T2;
    if (T2)
        T2 -> parent = c;
    c -> rChild = T3;
    if (T3)
        T3 -> parent = c;
    updateHeight(c);
    b -> lChild = a;
    a -> parent = b;
    b -> rChild = c;
    c -> parent =b;
    updateHeight(b);
    return b; // 该子树新的根节点
}

template<typename T> BinNodePosi(T) BST<T>::rotateAt(BinNodePosi(T) v) {
    BinNodePosi(T) p = v -> parent;
    BinNodePosi(T) g = p -> parent;
    if (IsLChild(*p)) { // zig
        if (IsLChild(*v)) { // zig-zig
            p -> parent = g -> parent; // 向上联接
            return connect34(v, p, g, v -> lChild, v -> rChild, p -> rChild, g -> rChild);
        } else { // zig-zag
            v -> parent = g -> parent; // 向上联接
            return connect34(p, v, g, p -> lChild, v -> lChild, v -> rChild, g -> rChild);
        }
    } else { // zag
        if(IsRChild(*v)) { // zag-zag
            p->parent = g->parent;
            return connect34(g, p, v, g -> lChild, p -> lChild, v -> lChild, v -> rChild);
        } else { // zag-zig
            v->parent = g->parent;
            return connect34(g, v, p, g -> lChild, v -> lChild, v -> rChild, p -> rChild);
        }
    }
}

AVL树无论查找、插入或删除，最坏情况下的复杂度均为O(logn)
借助高度或平衡因子，需改造元素结构或额外封装
实测复杂度与理论值有差距
单次动态调整后，全树拓扑结构的变化量可能Ω(logn)