P5076

· · 题解

注：本文适合入门选手食用，神犇请绕道P3369

BST 是什么？

BST（Binary Search Tree ，二叉搜索树），它或是一颗空树，或是满足某种性质的二叉树：

性质要熟记 ! ! !

  1. BST 的左子树不为空时，左子树上的值均小于它的根结点的值。
  2. BST 的右子树不为空时，右子树上的值均大于它的根节点的值。
  3. 无相同权值的节点 (所以我们要定义一个 cnt 来记录一个权值出现的次数)。
  4. 左右子树均满足 BST 的性质。

了解完了 BST 的性质，我们来看看，

BST 上的节点都有什么？

  1. 该节点的权值 val ，也就是给出的数列中的元素。
  2. 该节点的左儿子（左子树） ls 和右儿子（右子树） rs 的下标。
  3. 该节点的权值 val 出现的次数 cnt。
  4. 该节点子树的大小和自己的大小的和 size（用处下述）。

据上述，我们可以用一个结构体来存 BST。

代码如下:

struct node
{
    int val,ls,rs,cnt,size;
}tree[100010];

前驱和后继（后面有用）

前驱：小于当前节点值的最大值

后继：大于当前节点值的最小值

BST 的基本操作

1.插入 add\_son(x,v)

如果当前节点权值 $ tree[x].val $ 等于要插入的值 $ v $ ，则当前节点值出现的次数 $ tree[x].cnt $ +1。 否则就往这个节点的子树寻找 ，往左子树还是往右子树寻找取决于 $v$ 大于还是小于 $tree[x].val$ ，若大于则往左子树找，小于则往右子树找。 具体代码如下（内附注释）： ```cpp void add_son(int x,int v)//x->当前节点下标 v->要插入的值 { tree[x].size++; if(tree[x].val==v) { tree[x].cnt++;//权值出现次数+1 return ;//直接退出 加入下个值 } if(tree[x].val>v)//∵tree[x].val>v ∴v->tree[x].ls { if(tree[x].ls)//节点x有左子树就将v放入x的左子树 add_son(tree[x].ls,v); else//若没有，则v就是x的左子树的权值 { ct++; tree[ct].val=v; tree[ct].size=tree[ct].cnt=1; tree[x].ls=ct; } } else//右子树与左子树同理 { if(tree[x].rs) add_son(tree[x].rs,v); else { ct++; tree[ct].val=v; tree[ct].size=tree[ct].cnt=1; tree[x].rs=ct; } } return ;//个人习惯 } ``` ## 2.找前驱 $ findfnt(x,val,ans) 这个操作就是顺着树从上往下搜，详细解释结合代码内注释理解： ```cpp int findfnt(int x,int val,int ans) { if(tree[x].val>=val) //节点x值大于val，说明这个数大了，所以我们要在左子树找 { if(!tree[x].ls) //若节点x没有左子树，说明当前的ans就是val的前驱，直接return ans return ans; else //有的话，就在左子树查 findfnt(tree[x].ls,val,ans); } else //小于val，则查找右子树 { if(!tree[x].rs) //若节点x没有右子树，则返回tree[x].val,原因参考性质2 return tree[x].val; if(tree[x].cnt) //若当前x的子节点不为零，ans则更新为tree[x].val return findfnt(tree[x].rs,val,tree[x].val); else //反之，则不更新 return findfnt(tree[x].rs,val,ans); } } ``` ## 3.找后继 $findnxt(x,val,ans) 
int findnxt(int x,int val,int ans)
//x->当前节点的下标 val->要找后继的值 ans->目前已找到的>val的最小值(val可能的后继)
{
//与找前驱同理(改改符号就行了)
    if(tree[x].val<=val)
    {
        if(!tree[x].rs)
            return ans;
        else
            findnxt(tree[x].rs,val,ans);
    }
    else
    {
        if(!tree[x].ls)
            return tree[x].val;
        if(tree[x].cnt)
            return findnxt(tree[x].ls,val,tree[x].val);
        else
            return findnxt(tree[x].ls,val,ans);
    }
}

4.按值找排名 findval(x,val)

（排名：$val$ 在树中的节点值是第 $k$ 小的） 我们先看几组数据 ``` 要找排名的值：8 树上元素值：9 2 3 4 7 19 8 0 7 24 排名：7 ``` ``` 要找排名的值：24 树上元素值：5 7 24 9 81 121 8 13 17 38 排名：7 ``` ``` 要找排名的值：18 树上元素值：12 15 1 91 18 4 20 20 1 26 排名：6 ``` 由上面几组数据我们不难看出 ，排名其实就是比 $val$ 小的值的个数+1，所以我们可以将问题简化为找比 $val$ 小的值的个数，在最后输出时+1即可。 找比 $val$ 小的值就可以用到 $tree[x].size$ 了，详细结合代码（含注释）理解： ```cpp int findval(int x,int val) { if(x==0) return 0; //没有排名 if(tree[x].val==val) //当前节点的值等于val，则返回它的左子树的大小(原因参考性质1) return tree[tree[x].ls].size; if(tree[x].val>val) //大了就在左子树找(原因参考性质1) return findval(tree[x].ls,val); else //小了就在右子树找(原因参考性质2)，再加上这个节点的左子树的大小和这个节点的值出现的次数 //因为这个节点小于val，所以它的左子树都小于val(原因参考性质1) return findval(tree[x].rs,val)+tree[tree[x].ls].size+tree[x].cnt; } ``` ## 5.按排名找值 $findrnk(x,rnk)

其实 findrnk 和 findval 很相似，各位同学自行查看代码中的注释并结合 findval 部分食用

int findrnk(int x,int rnk)//x->当前节点的下标 rnk->要找值的排名
{
    if(x==0) return INF;
    if(tree[tree[x].ls].size>=rnk)//左子树的大小大于rnk，说明rnk在左子树
        return findrnk(tree[x].ls,rnk);//查左子树
    if(tree[tree[x].ls].size+tree[x].cnt>=rnk)//左子树的大小加上这个节点的值出现的次数恰好大于等于rnk，说明我们找到答案了
        return tree[x].val;//直接返回当前点的权值
    else
        return findrnk(tree[x].rs,rnk-tree[tree[x].ls].size-tree[x].cnt);//否则查右子树，并将rnk减去左子树的大小和当前节点的值出现的次数
}

以上是递归版 BST ，学有余力的同学可以看一下其他神犇的循环版 BST

感谢观看