平衡树前传之BST
二叉查找树((BST)),是一个类似于堆的数据结构,
并且,它也是平衡树的基础.
因此,让我们来了解一下二叉查找树吧.
(其实本篇是作为放在平衡树前的前置知识的,但为了避免重复懒得写就单独拎了出来)
首先,二叉查找树,是一个树形的数据结构废话,树上的每个节点有一个权值(val).
而树中的任意一个节点,都满足以下性质:
-
该节点的权值不小于它左子树中任意节点的权值.
-
该节点的权值不大于它右子树中任意节点的权值.
显然,二叉查找树的中序遍历就是一个递增序列.
那么接下来,让我们了解(BST)的操作吧.
step 1:BST的建立
其实这个很简单,就是为了避免越界而插入(INF)和(-INF)而已.
看代码吧(是不是好简单):
struct BST{int l,r,val;}t[100001];
int tot=0,rt/*根节点*/,INF=1<<30;
inline int New(int val){
t[++tot].val=val;
return tot;
}
inline void build(){
New(-INF);New(INF);
rt=1;t[1].r=2;
}
step 2:BST的查找
查找也很好理解.
假设我们要查找的是权值(v),
那么根据两条性质,
若(v)小于当前节点的权值,就往左走,否则就往又走.
相等或者是空节点(即没有)时,就返回.
上代码(应该很好想吧):
int find(int p,int val){
if(!p||t[p].val==val) return p;
return find(val<t[p].val? t[p].l:t[p].r,val);
}
step 3:BST的插入
shanchu其实这和查找的想法一样.
插入时,若已经插入过,就直接返回(或根据题目情况而定),
到空节点时,就新建节点.
step 4:BST求前驱&后继
就拿前驱为例子吧(因为道理是一样的).
首先,我们先去找要求的点(p),
那么有几种情况:
- 没有找到(p).
- 找到了(p),但(p)无左子树.
- 找到了(p),且(p)有左子树.
对于第一种情况,答案就在寻找过的路径中.
因为如果要插入(p)的话,它肯定在它前驱的右子树中(模拟一下插入就知道了).
而第二种情况,由于没有左子树,因此答案也在之前的路径中.
第三种的话,我们先找到它的左子树,再一直往右走,就能找到了(根据BST的性质仔细想想就能理解了).
来上代码吧:
inline int getpre(int val){
int ans=1,p=rt;//t[1].val=-INF
while(p){
if(val==t[p].val){
if(!t[p].l) return ans;
p=t[p].l;
while(t[p].r) p=t[p].r;
return p;
}
if(t[p].val<val&&t[p].val>t[ans].val) ans=p;
p=val<t[p].val? t[p].l:t[p].r;
}
return ans;
}
step 5:BST的删除
删除就要复杂一些了qwq.
如果是空节点,就直接返回.(先排除掉一种情况)
那么假设我们找到了要删除的点,
还有三种情况:
- (p)为叶子节点.
- (p)无左/右子树.
- (p)有左/右子树.
对于第一种,直接删掉就好.
而第二种的话,就可以用子节点代替它.
第三种有点难想啊...
其实,我们可以找出它的前驱/后继节点(就是上一步的第三种情况).
然后再代替它就行啦.
来上代码吧:
inline void remove(int &p,int val){
if(!p) return ;
if(val==t[p].val){
if(!t[p].l) p=t[p].r;
else if(!t[p].r) p=t[p].l;
else {
int next=t[p].r;
while(t[p].l) p=t[p].l;
remove(t[p].r,t[next].val);
t[next].l=t[p].l;t[next].r=t[p].r;
p=next;
}
return ;
}
remove(val<t[p].val? t[p].l:t[p].r,val);
}
总结
BST的几个操作都讲完啦!
然而,发现一件事没?
如果我们依次插入一个递增/递减序列,BST就会被卡成一条链.
因此,我们有了平衡树...