猫史档案馆

 

 

数据结构是程序设计和编程中十分重要的一块。

我之前讲解的数据结构有树、栈、队列、树状数组、线段树、并查集、堆和分块。其中线段树和分块是比较高级的，难度也较大，其他的则是一些很常用并且简单的数据结构。

平衡树在OI中实现较难，但是却很重要。一般不是省选及以上不会弄太毒瘤的平衡树和其他数据结构，并且lxl不是每年都出题（雾

平衡树总共准备发三篇，分别是BST、Treap、Splay（发一个帖子实在写不下）

 

___________________________________________________________________

目录

 

 

 · BST

 · Treap

 

 

 

BST(Binaru Search Tree)

___________________________________________________________________

 

BST(Binaru Search Tree)，二叉查找树。又称二叉排序树、二叉搜索树。

BST是拥有BST性质的特殊的树，每一个结点都有一个关键码（权值）。

BST性质是所有平衡树的基础。

 

 

 

BST性质

___________________________________________________________________

 

BST性质是指，对于树中的任意一个节点：

1.该节点的关键码不小于其左子树中任意节点的关键码；

2.该节点的关键码不大于其右子树中任意节点的关键码。

 

通俗的讲，左子树中的点的关键码<=子树根节点关键码<=右子树中的点的关键码。

显然，满足BST性质的树，其中序遍历是一个关键码单调递增的数列。

 

 

 

BST图示

___________________________________________________________________

 

 

 

 

BST建树

___________________________________________________________________

 

为了避免越界，建立BST时在树中额外插入一个关键码为负无穷（很大的数）的节点，并在这个节点的右子树中插入一个正无穷的节点。

最初的BST有两个节点：一个负无穷，一个正无穷。

 

//结构体存储
struct BST{
    int l,r;//左右节点在数组中的下标
    int val;//节点关键码
}a[SIZE];//结构体数组
int tot,root,INF=1<<30;
//tot用于表示下标，root是根节点下标，INF是一个很大的数

//建立节点
int New(int val){//val是要建立的值，分别是负无穷和正无穷
    a[++tot].val=val;//下标加一，然后存储
    return tot;
}

//初始建树
void build{
    New(-INF),New(INF);//新建两个节点，分别是负无穷和正无穷
    root=1,a[1].r=2;//根节点（负无穷）的右子节点的下标为2
}

 

 

 

BST的检索

___________________________________________________________________

 

由于BST性质的存在，检索会非常方便。

让p代表根节点root，val表示要查找的值。执行以下操作：

1.若p的关键码等于val，则已经找到；

2.若p的关键码大于val，

    (1)若p左子节点为空，表明不存在；

    (2)若不为空，递归左子树

3.若p的关键码小于val，

    (1)若p右子节点为空，表明不存在；

    (2)若不为空，递归右子树

 

//p是当前遍历到的节点的标号，val是要查找的关键码
int Get(int p,int val){
    if(p==0)return 0;//这个位置是空的，返回
    if(val==a[p].val)return p;//找到了，检索成功
    if(val<a[p].val)return Get(a[p].l,val);
    else return Get(a[p].r,val);
    //为了方便，这句话珂以写成 return val<a[p].val?Get(a[p].l,val):Get(a[p].r,val);
}

 

 

 

BST的插入

___________________________________________________________________

 

和检索过程类似。

在发现要走向的p的子节点为空，说明p不存在。

此时直接电力关键码为cal的新节点，作为p的子节点。

 

void Insert(int &p,int val){
    if(p==0){p=New(val);return;}
    if(val==a[p].val)return;
    if(vsl<s[p].val)Insert(a[p].l,val);
    else Insert(a[p].r,val);
}

 

 

 

BST求前驱/后继

___________________________________________________________________

 

前驱：在树中关键码小于val的前提下，关键码最大的节点

后继：在树中关键码大于val的前提下，关键码最小的节点

 

以求后继为例。

 

初始化ans为正无穷关键码那个节点的编号。随后，检索val。

检索过程中，每经过一个节点，都检查这个节点的关键码，判断能否更新ans。

检索完成后，有三种可能：

1.没有找到val。此时ans即为所求。

2.找到了关键码为val的节点p，但是p没有右子树。此时ans为所求。

3.找到了关键码为val的节点p，p有右子树。此时从p的右子节点出发，一直往左走，就找到了。

 

int GetNext(int val){
    int ans=2;//a[2].val==INF
    int p=root;
    while(p){
        if(val==a[p].val){
            if(a[p].r>0){
                p=a[p].r;
                //右子树上一直向左走
                while(a[p].l>0)p=a[p].l;
                ans=p;
            }
            break;
        }
        //每次经过一个节点，尝试更新后继ans
        if(a[p].val>val&&a[p].val<a[ans].val)ans=p;
        p=cal<a[p].val?a[p].l:a[p].r;
    }
    return ans;
}

 

 

 

BST的节点删除

___________________________________________________________________

 

在BST中检索关键码为val的节点p。

 

如果p的子节点个数小于2个，直接删除p，并让p的子节点代替p，与父节点相连。

如果p既有左子树又有右子树，此时为了维持BST性质，要把p的后继拖过来，然后把p删了。那么在BST中求出p的后继next。根据求后继的第三种情况，这个时候next没有左子树。因此直接删除next，让next的右子树代替next。最后让原先的next代替p即可。

 

//删除节点。p是引用，所以改动参数p之后会把传进来的原来的变量一起改掉
void Remove(int &p,int val){//从子树p中删除值为val的节点
    if(p==0)return;
    if(cal==a[p].val){//检索到了
        if(a[p].l==0)//没有左子树
            p=a[p].r;//右子树代替p的位置
        else if(a[p].r==0)//没有右子树
            p=a[p].l;//左子树代替p的位置
        else{//左右子树都有
            //求后继
            int next=a[p].r;
            while(a[next].l>0)next=a[next].l;
            //next一定没有左子树，删了
            Remove(a[p].r,a[next].val);
            //令节点next代替节点p的位置
            a[next].l=a[p].l,a[next.r=a[p].r;
            p=next;//p是引用
        }
        return;
    }
    if(val<a[p].cal)Remove(a[p].l,val);
    else Remove(a[p].r,val);
}

___________________________________________________________________

今天就讲到这里。下次讲Treap，接着再下次讲Splay。