一种贪心的AVL Tree

dazexiaoxi · 2026-10-17 20:54:38 · 算法·理论

前言

这是在学校自习课想出的一种优化方法，偏激进，而且可能很好想。

（但是证明巨麻烦）

标准 AVL

标准 AVL 的思路大致为：

• 对每个操作：
• • 若本次操作导致某个节点的左右子树高度差大于等于 2，对立即该节点进行双旋。
  • 否则，什么也不做。

这造就了 AVL 极高的平衡性，但问题是每次修改树结构的操作都会触发大量双旋，从而导致插入 / 删除效率较低，但与此同时，带来的是极高的查询效率。

从而，我们可以很容易想到一种优化思路：类似于线段树的懒处理思路。

也就是暂时不处理失衡，而在下次需要使用时调整。

但这样需要处理的总旋转次数并没有改变，故而我们引出接下来的优化：

Unstable AVL

下面约定 \Delta_u 为节点 u 的左右子树高度差，若无特殊说明，u 为当前节点。

这就是本文将要详细展开的思路。

• 对于每一个可能修改树结构的查询：
• • 向上回溯时，“分发”unstable：
  • 若 \Delta_u \ge 2，将 u 的 unstable 标记为 true。
  • 否则，什么也不做。
• • 向下查询时，“收回”unstable：
  • • 若本次操作可能减小 \Delta_u（e.g. 向较矮侧插入，向较高侧删除）：
    • 直接将 u 的 unstable 标记为 false。
  • • 否则，对 u 执行标准双旋，然后将 u 的 unstable 标记为 false。

这样，通过操作的“自然修复”，我们可以省下大部分旋转，以常数的预检测为代价换来了更少的昂贵的旋转操作。

现在唯一的问题在于：

如果某次插入是多重插入（不会增加节点），那么可能会触发矮树的双旋，使矮树的高度反而减少，从而使 \Delta_u 增加。

那么我们应该如何证明树高为对数级呢？

（部分来自 GPT6-Astra ）

证明

定义

定义 1
对任意子树 T，记 N(T) 为实际结构节点数，h(T) 为实际高度，并令

空树满足 W(\varnothing)=1
若节点 v 的两个孩子子树为 L,R，则

高度为 h 的树至少含 h 个结构节点，因此

定义 2
令

其中 t 为整数，F 单调递增。

定义 3
对每个非空节点 v，要求

由 P 可推出整体下界：对非空子树 T，

空树也满足 W(\varnothing)=1\ge q^0=1。

定义 4
对节点 v，记

即右子树高度减左子树高度。
若 |\Delta(v)|\ge 2，称 v 失衡
修复旋转指标准 AVL 单旋或双旋，由内侧高度决定。

定义 5
插入或删除进入某个孩子子树时，若进入高度较大的一侧，称进入高侧；若进入高度较小的一侧，称进入矮侧；两侧等高时任意指定。
删除时“进入矮侧”指待删键位于较矮子树中。

Lemma 1

陈述
对任意修复旋转，设旋转前入口子树高度为 H，旋转后新根为 r，则

并且 r 的两个孩子权重均至少 F(H+1)。
若该旋转由删除触发，则待删键所在的新孩子权重至少 F(H)。

证明
只证左高右旋，右高左旋对称。
设 A,B,C 高度分别为 a,b,c，原根为 x，提升后的根为 y。
进入单旋分支意味着 a\ge b，且原根左高至少 2，从而 c\le a-1，a\ge 1。
旋转前 h(y)=a+1，原高度 H=a+2。
旋转后旧根 x 的高度为 \max(b,c)+1\le a+1，新根高度在 H-1 与 H 之间。
由旧不变量，

新根 y 的两侧权重满足：

其中 q+q^2>2。
故单旋后新根两侧权重均至少 F(H+1)。

双旋由两个单旋构成，设 A,B,C,D 高度为 a,b,c,d，令 t=\max(b,c)。
内侧较高意味着 a\le t，原根失衡意味着 d\le t。
旋转前 z,y,x 高度依次为 t+1,t+2,t+3，原高度 H=t+3。
旋转后新根 z 的两侧 y,x 高度均不超过 t+1。
由旧不变量，

于是

故双旋后新根两侧权重均至少 F(H+1)
高度不增由单旋与双旋的直接计算得到。

若旋转由删除触发，则旧矮侧权重至少 F(H)，另一部分权重至少 1，故待删键所在的新孩子权重至少 F(H)+1。
删除至多移除一个结构节点，返回后该孩子权重仍至少 F(H)。
对称情形相同。

Lemma 2

陈述
一次插入使结构节点数增加 0 或 1。
一次删除使结构节点数减少 0 或 1。
旋转不改变所在子树的 W。
删除有两个孩子的节点时，复制后继的键与出现次数，最终只移除一个结构节点；临时出现次数为 0 的后继仍按一个结构节点计数。

证明
插入重复键时只增加出现次数，不增加结构节点；插入新键时增加一个结构节点。
删除重复键时只减少出现次数，不减少结构节点；删除唯一出现键时至多减少一个结构节点。
删除有两个孩子的节点时，后继的键与出现次数先复制到当前节点，后继的出现次数置 0 并递归删除，最终物理移除的是后继这一个结构节点。
在后继被物理移除之前，它仍是一个结构节点，因此本次删除对结构节点数的净影响为 -1。
旋转只改变指针，不改变节点数，因此不改变 W。

Lemma 3

陈述
设 P 在子树 T 上成立，h_T=h(T)，H 为整数且 h_T\ge H-2。
若 T 的结构节点数至多减少 1，所得子树权重 W' 满足：

证明
由 P 的整体推论，

又高度为 h_T 的树至少含 h_T 个结构节点，故

节点数至多减少 1，所以

由 h_T\ge H-2 及 q>1 的单调性，

若 H\le 3，则 F(H)=q^{H-3}\le 1，而 W'\ge 1，成立。

以下设 H\ge 4，

当 4\le H\le 8 时，逐一检查可知：

故 W'\ge H-2\ge F(H)。

当 H\ge 9 时，

因为 q=2^{1/3}>5/4，所以 q-1>1/4。
又 H-3\ge 6，故 q^{H-3}\ge q^6=4
于是

所以

从而 W'\ge F(H)。
两种情形覆盖所有整数 H。

Lemma 4

陈述
若入口节点失衡，修复检查在递归进入孩子之前执行。
若执行了修复旋转，则后续递归以新根为入口，按新根的键决定进入方向。

证明
由算法结构直接得到。
修复检查位于递归调用之前。
若发生旋转，入口节点已被新根替代，后续比较以新根为基准。

Lemma 5

陈述
设入口节点为 u，高度为 H。

1. 若 u 失衡且插入进入高侧，则修复检查执行旋转，整树高度不增加。
2. 若 u 失衡且插入进入矮侧，则修复检查不旋转；矮侧增高 1 后仍不超过高侧，整树高度不变。
3. 若 u 失衡且删除进入矮侧，则修复检查执行旋转。
4. 若 u 失衡且删除进入高侧，则修复检查不旋转；高侧降低后仍不低于矮侧，整树高度不变。

因此，插入时“无旋转但返回高度为 H+1”要求 u 非失衡。
删除时“无旋转”要求 u 非失衡，或删除进入高侧。

证明
逐条对照修复检查的分支条件。
失衡时 |\Delta(u)|\ge 2。

1. 插入进入高侧，高侧会进一步增高。
   若修复检查跳过，则高度差至少变为 3，与修复规则矛盾。
   故修复检查必旋转。
   由 Lemma 1，旋转后高度不增。

2. 插入进入矮侧，矮侧增高 1 后高度差至多 1，不超过高侧。
   故整树高度不变。

3. 删除进入矮侧，矮侧会进一步降低。
   若修复检查跳过，则高度差至少变为 3，与修复规则矛盾。
   故修复检查必旋转。

4. 删除进入高侧，高侧降低 1 后高度差至多 1，不低于矮侧。
   故整树高度不变。

综上，插入时无旋转但高度增加 1 只能发生在入口非失衡时。
删除时无旋转只能发生在入口非失衡或删除进入高侧时。

Theorem 1

陈述
任意插入保持整树的 P 成立。

证明
设入口树 T 非空，h(T)=H，入口处 P 成立。
对子树结构节点数归纳，假设对所有小于 N(T) 的子树成立。
分三种情形：

情形 A：入口执行了修复旋转
由 Lemma 1，旋转后新根 r 满足：

且 r 两侧权重均至少 F(H+1)。
由 Lemma 4，递归插入以 r 为入口。
设被访问侧原高 h_0，插入后高 h_1\in\{h_0,h_0+1\}；另一侧高不变。
插入后的子树由归纳假设满足 P，因为节点数严格小于入口。

若插入未使 r 的高度增加，则 h(r)_{\text{新}}=H'\le H。
两侧权重仍至少 F(H+1)\ge F(H')\ge F(h(r)_{\text{新}})。
故 P 在 r 处成立，后代由归纳假设或未变化保持。

若插入使 r 的高度变为 H'+1，则 H'+1\le H+1。
两侧权重至少 F(H+1)\ge F(h(r)_{\text{新}})。
故 P 在 r 处仍成立。
旋转已留下 F(H+1) 的余额，正好覆盖插入使高度再涨 1 的情况。

情形 B：入口没有旋转，且返回高度不超过 H
递归进入某侧。
未访问侧权重不变，仍至少 F(H)，由入口 P
被访问侧权重由 Lemma 2 不减少，仍至少 F(H)，由入口 P。
返回高度 H'\le H，两侧权重至少 F(H)\ge F(H')。
故 P 在入口根成立，后代由归纳假设或未变化保持。

情形 C：入口没有旋转，但返回高度为 H+1
由 Lemma 5，入口非失衡，即 |\Delta|\le 1。
设被访问侧原高 h，未访问侧高 h'。
要使高度增加，须 h'\le h，否则增长后仍不超过另一侧。
故 H=1+h，返回高度 H+1=h+2。
两侧最终高度为 h+1 和 h'，且 h'\ge h-1，因为 |\Delta|\le 1。

被访问侧由归纳假设满足 P，高度 h+1，故

未访问侧由入口 P 的整体推论，

两侧权重至少 F(H+1)，故 P 在新根成立
后代由归纳假设或未变化保持。

三种情形覆盖所有插入分支，归纳完成。

Theorem 2

陈述
任意删除保持整树的 P 成立。

证明
设入口树 T 非空，h(T)=H，入口处 P 成立。
对子树结构节点数归纳。
删除使入口返回高度不超过 H，由 Lemma 1
分三种情形：

情形 A：入口执行了修复旋转
由 Lemma 5，这是入口失衡且删除进入矮侧的情况。
由 Lemma 1，新根高度 H'\le H。
待删键必位于新根的一个孩子中，不会命中新根，因为新根键与旧根不同。
该孩子由旧矮侧 S 与另一部分合成，旋转后权重至少 F(H)+1。
递归删除进入该孩子。
由 Lemma 2，删除使权重减少至多 1，故返回后该孩子权重至少 F(H)。
未访问侧权重至少 F(H+1)\ge F(H)，由 Lemma 1。
新根高度 H'\le H，两侧权重至少 F(H)\ge F(H')，故 P 在新根成立。
后代由归纳假设、未变化或旋转引理保持。

情形 B：入口没有旋转，递归进入某侧
由 Lemma 5，有两种子情况。
若入口非失衡，即 |\Delta|\le 1，入口高 H 由 H-1 侧决定，另一侧至少 H-2，被访问侧原高 u\ge H-2。
若入口失衡且删除进入高侧，则被访问侧即高侧，u=H-1\ge H-2。
总之被访问侧原高 u\ge H-2。
由归纳假设其 P 成立，且删除使节点数减少至多 1。
由 Lemma 3，返回后该侧权重至少 F(H)。
未访问侧权重至少 F(H)，由入口 P。
入口返回高度不超过 H，故两侧权重至少 F(H)\ge F(\text{新高度})。

Theorem 3

陈述
从空树出发执行任意有限次插入与删除后，整树满足 P。
设当前不同键数量为 n，空树高度为 0，则

因此插入、删除、查询均为最坏 O(\log n)，其中节点分配按摊还计。

证明
空树真空满足 P。
由 Theorem 1 与 Theorem 2，插入和删除都保持 P。
故从空树出发的任意有限操作序列结束后，每个节点都满足 P。

对非空树，由 P 的整体推论，

两边取对数得

空树 n=0，h=0 也满足同一式子。

查询路径长度受树高控制，故为 O(\log(n+1))。
插入与删除沿路径处理，每层只做常数次旋转与更新，结构操作总量同样为 O(\log(n+1))。
若节点分配与回收按 O(1) 计，则更新为最坏 O(\log(n+1))。
实现使用动态数组，单次扩容可线性搬移，因此实际存储开销需按摊还界另计。

再次声明，本部分大部分由 GPT6-Astra 提供，可能有些许问题。

（刚写完这些洛谷登录掉了导致几百行没保存，心情很崩溃，故使用 AI 重写了本部分，请见谅 QAQ）

测试结果

使用 new 的标准 AVL(11.04s)

使用 new 的 Unstable AVL(9.86s)

使用内存池且优化拉满的 Unstable AVL(7.01s)

可以看到效率提升很高，考虑到节省了大部分指针交换，这是必然的。

代码

//Unstable AVL by @dazexiaoxi
//2026/10/17 21:51
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstddef>
#include <optional>
using namespace std;
class LazyAVL{
    struct Node{
        int key;
        int l=0,r=0;
        int h=1,sz=1;
        int cnt=1;
        bool un=false;
        Node(int k=0):key(k){}
    };
    vector<Node> pool;
    vector<int> free_idx;
    int root_=0;
    int newNode(int k){
        if(!free_idx.empty()){
            int idx=free_idx.back();
            free_idx.pop_back();
            pool[idx]=Node(k);
            return idx;
        }
        int idx=(int)pool.size();
        pool.emplace_back(k);
        return idx;
    }
    void delNode(int idx){
        free_idx.push_back(idx);
    }
    int H(int n)const{return n?pool[n].h:0;}
    int S(int n)const{return n?pool[n].sz:0;}
    void update(int n){
        int hl=H(pool[n].l),hr=H(pool[n].r);
        pool[n].h=1+std::max(hl,hr);
        pool[n].sz=pool[n].cnt+S(pool[n].l)+S(pool[n].r);
        int diff=hl-hr;
        pool[n].un=(diff>=2||diff<=-2);
    }
    int rotR(int n){
        int L=pool[n].l;
        pool[n].l=pool[L].r;
        pool[L].r=n;
        update(n);update(L);
        return L;
    }
    int rotL(int n){
        int R=pool[n].r;
        pool[n].r=pool[R].l;
        pool[R].l=n;
        update(n);update(R);
        return R;
    }
    int downRot(int n){
        if(H(pool[n].l)-H(pool[n].r)>=2){
            if(H(pool[pool[n].l].l)<H(pool[pool[n].l].r))
                pool[n].l=rotL(pool[n].l);
            return rotR(n);
        }
        if(H(pool[n].r)-H(pool[n].l)>=2){
            if(H(pool[pool[n].r].r)<H(pool[pool[n].r].l))
                pool[n].r=rotR(pool[n].r);
            return rotL(n);
        }
        return n;
    }
    int settle(int n,bool goL,bool isIns){
        if(!pool[n].un) return n;
        bool tallL=H(pool[n].l)>H(pool[n].r);
        bool goTall=goL?tallL:!tallL;
        if(isIns?goTall:!goTall) n=downRot(n);
        pool[n].un=false;
        return n;
    }
    int insert(int n,int key){
        if(!n) return newNode(key);
        bool goL=(key<=pool[n].key);
        if(pool[n].un) n=settle(n,goL,true);
        if(key<pool[n].key) pool[n].l=insert(pool[n].l,key);
        else if(key>pool[n].key) pool[n].r=insert(pool[n].r,key);
        else{pool[n].cnt++;update(n);return n;}
        update(n);
        return n;
    }
    int remove(int n,int key){
        if(!n) return 0;
        bool goL=(key<pool[n].key);
        if(pool[n].un) n=settle(n,goL,false);
        if(key<pool[n].key) pool[n].l=remove(pool[n].l,key);
        else if(key>pool[n].key) pool[n].r=remove(pool[n].r,key);
        else{
            if(pool[n].cnt>1){pool[n].cnt--;update(n);return n;}
            if(!pool[n].l){int r=pool[n].r;delNode(n);return r;}
            if(!pool[n].r){int l=pool[n].l;delNode(n);return l;}
            int s=pool[n].r;
            while(pool[s].l) s=pool[s].l;
            pool[n].key=pool[s].key;
            pool[n].cnt=pool[s].cnt;
            pool[s].cnt=0;
            pool[n].r=remove(pool[n].r,pool[s].key);
        }
        update(n);
        return n;
    }
public:
    void insert(int key){root_=insert(root_,key);}
    void remove(int key){root_=remove(root_,key);}
    bool contains(int key)const{
        int n=root_;
        while(n){
            if(key<pool[n].key) n=pool[n].l;
            else if(key>pool[n].key) n=pool[n].r;
            else return true;
        }
        return false;
    }
    int getRank(int key)const{
        int r=0,n=root_;
        while(n){
            if(key<=pool[n].key) n=pool[n].l;
            else{r+=pool[n].cnt+S(pool[n].l);n=pool[n].r;}
        }
        return r;
    }
    std::optional<int> getKth(int k)const{
        if(k<1||static_cast<size_t>(k)>size()) return std::nullopt;
        int n=root_;
        while(n){
            int ls=S(pool[n].l);
            if(k<=ls) n=pool[n].l;
            else if(k<=ls+pool[n].cnt) return pool[n].key;
            else{k-=ls+pool[n].cnt;n=pool[n].r;}
        }
        return std::nullopt;
    }
    std::optional<int> predecessor(int key)const{
        std::optional<int> res;
        int n=root_;
        while(n){
            if(pool[n].key<key){res=pool[n].key;n=pool[n].r;}
            else n=pool[n].l;
        }
        return res;
    }
    std::optional<int> successor(int key)const{
        std::optional<int> res;
        int n=root_;
        while(n){
            if(pool[n].key>key){res=pool[n].key;n=pool[n].l;}
            else n=pool[n].r;
        }
        return res;
    }
    size_t size()const{return S(root_);}
    bool empty()const{return root_==0;}
    void clear(){
        pool.clear();
        pool.emplace_back(0);
        free_idx.clear();
        root_=0;
    }
    LazyAVL(){
        pool.reserve(1024);
        pool.emplace_back(0);
    }
};
inline int readInt(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int main(){
    int n=readInt(),m=readInt();
    LazyAVL avl;
    for(int i=0;i<n;i++) avl.insert(readInt());
    int last=0,xorsum=0;
    for(int i=0;i<m;i++){
        int opt=readInt(),xp=readInt();
        int x=xp^last;
        switch(opt){
            case 1: avl.insert(x);break;
            case 2: avl.remove(x);break;
            case 3:{int ans=avl.getRank(x)+1;last=ans;xorsum^=ans;break;}
            case 4:{int ans=avl.getKth(x).value_or(-1);last=ans;xorsum^=ans;break;}
            case 5:{int ans=avl.predecessor(x).value_or(-1);last=ans;xorsum^=ans;break;}
            case 6:{int ans=avl.successor(x).value_or(-1);last=ans;xorsum^=ans;break;}
        }
    }
    printf("%d\n",xorsum);
    return 0;
}

结语

大概就是这样了。

其实这个算法也不算特别难想吧，几乎是直觉的东西了

如果有人有查到前人做过类似的贪心，请一定告知我。