首页 > 其他 > 详细

SBT(Size Balanced Tree)

时间:2018-11-20 22:38:58      阅读:159      评论:0      收藏:0      [点我收藏+]

1. 二叉搜索树

  二叉搜索树,是一种能实现动态查询第k大或查询,某数在序列中的排名的树形结构,在数据较为随机的情况下,它的期望复杂度为O(logn),但是若是数据为一个有序序列,那么该二叉搜索树,将会变成一条链,此时每次查找的复杂度将会变成复杂度为O(n)

2. SBT

  针对上述问题,为了能使复杂度回到O(logn),我们在每次插入操作后,对树形进行高效的调整使之变的较为平衡。这时树高变成logn 而搜索的复杂度也于是会变回logn为此我们引入左旋和右旋操作

void zx(int &x)
{
    int y=rs[x];
    rs[x]=ls[y];
    ls[y]=x;
    siz[y]=siz[x];
    siz[x]=siz[ls[x]]+siz[rs[x]]+1;
    x=y;
}
void yx(int &x)
{
    int y=ls[x];
    ls[x]=rs[y];
    rs[y]=x;
    siz[y]=siz[x];
    siz[x]=siz[ls[x]]+siz[rs[x]]+1;
    x=y;
}

  为了能使树更加平衡,我们规定该点的左儿子不可以比该点的右儿子的左儿子和右儿子大,用代码表示起来就是siz[rs[rs[now]]]<=siz[ls[now]]和siz[ls[rs[now]]]<=siz[ls[now]],同理该点的右儿子不可以比该点的左儿子的左儿子和右儿子大。

  为了达到这个目的,我们进行一个maintain操作,对不平衡的子树进行调整(注:虽然它的复杂度看起来似乎是O(n)但实际上它的复杂度是O(1)的)

void maintain(int &now,int how)
{
    if(how)
    {
        if(siz[rs[rs[now]]]>siz[ls[now]]) zx(now);
        else if(siz[ls[rs[now]]]>siz[ls[now]]) yx(rs[now]),zx(now);
        else return;
    }
    else
    {
        if(siz[ls[ls[now]]]>siz[rs[now]]) yx(now);
        else if(siz[rs[ls[now]]]>siz[rs[now]]) zx(ls[now]),yx(now);
        else return;
    }
    maintain(ls[now],0);
    maintain(rs[now],1);
    maintain(now,0);
    maintain(now,1);
}

接下来的操作都是二叉搜索树的操作了,加点操作较为简单,不再赘述

SBT(Size Balanced Tree)

原文:https://www.cnblogs.com/cold-cold/p/9991909.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!