SBT總結

SBT

什麼是SBT

SBT即Size Balanced Tree，是一種高效的二叉查找樹，複雜度非常穩定。

SBT保證的一個節點的子樹大小與兄弟節點子樹大小相同，這個特殊性質需要維護，也可以完成很多操作。

SBT的數組

struct SBT
{
	int key,left,right,size;
}tree[100100];
           

其中key是節點的鍵值，left和right是節點左右子樹，size是節點的大小。

子樹大小的維護

樹要滿足一下條件：

tree[i].left.size>=max(tree[i].right.right.size,tree[i].right.left.size)  
tree[i].right.size>=max(tree[i].left.left.size,tree[i].left.right.size) 
           

我們思考我們要怎麼維護子樹大小。我們有一個常用的方法，就是旋轉。

左旋和右旋

其實和treap，splay是相似的。比如：

變為了

是以旋轉是很好了解也是很普通的，這個過程是可逆的。

void lrot(int &x)
{
	int y=tree[x].right;
	tree[x].right=tree[y].left;
	tree[y].left=x;
	tree[y].size=tree[x].size;//轉上去的節點數量為先前此處節點的size
	tree[x].size=tree[tree[x].left].size+tree[tree[x].right].size+1;
	x=y;
}
           

void rrot(int &x)
{
	int y=tree[x].left;
	tree[x].left=tree[y].right;
	tree[y].right=x;
	tree[y].size=tree[x].size;
	tree[x].size=tree[tree[x].left].size+tree[tree[x].right].size+1;
	x=y;
}
           

與很多二叉查找樹不同的是，不用記錄父親節點，是以旋轉中不需要改變多少變量。

旋轉是維護平衡的基礎。

maintain函數

當我們插入一個點，樹就可能不再平衡，我們使用的函數就是maintain函數。

maintain(x)指修複以x為根的樹的平衡性。調用maintain(x)的前提條件是，x的左右子樹都已平衡。

插入時我們要考慮四種情況。

分别是：

• x.left.left.size>x.right.size
• x.left.right.size>x.right.size
• x.right.right.size>x.left.size
• x.right.left.size>x.left.size

我們直接看一下代碼。

void maintain(int &x,bool flag)
{
	if(flag==false)//左邊
	{
		if(tree[tree[tree[x].left].left].size>tree[tree[x].right].size)//左孩子的左子樹大于右孩子
			rrot(x);
		else if(tree[tree[tree[x].left].right].size>tree[tree[x].right].size)//右孩子的右子樹大于右孩子
		{
			lrot(tree[x].left);
			rrot(x);
		}
		else return ;
	}
	else //右邊
	{
		if(tree[tree[tree[x].right].right].size>tree[tree[x].left].size)//右孩子的右子樹大于左孩子
			lrot(x);
		else if(tree[tree[tree[x].right].left].size>tree[tree[x].left].size)//右孩子的左子樹大于左孩子
		{
			rrot(tree[x].right);
			lrot(x);
		}
		else return ;
	}
	maintain(tree[x].left,false);
	maintain(tree[x].right,true);
	maintain(x,true);
	maintain(x,false);
}
           

比如這樣一張圖

然後插入一個鍵值為0的點。insert(t,left,data)，即insert(1,left,data)就是插在1的左邊。

對于6号節點，它右子樹大小為2，左兒子的左子樹大小為3

我們怎麼處理這些情況呢？

我們先讓x右旋,即6右旋。

這個時候它已經滿足條件了。

有時候我們不能一次旋轉就可以達到平衡，是以要多次旋轉。

比如這種兩次旋轉。

把3旋轉到1。

這樣就和之前一次旋轉一樣了。

把3旋轉到5。

可能我們需要更多次旋轉，但可以證明，最多旋轉logn次。

現在我們就可以用SBT解決問題了。

其他操作

插入操作

void insert(int &x,int key)
{
	if(x==0)
	{
		x=++top;
		tree[x].left=tree[x].right=0;
		tree[x].size=1;
		tree[x].key=key;
	}
	else
	{
		++tree[x].size;
		if(key<tree[x].key) insert(tree[x].left,key);
		else insert(tree[x].right,key);//相同元素插入到右子樹中
		maintain(x,key>=tree[x].key);//每次插入把平衡操作壓入棧中
	}
}
           

前驅查詢與後繼查詢

前驅

int pred(int &x,int y,int key)//查找key的前驅 
{
	if(x==0) return y;
	if(tree[x].key<key) return pred(tree[x].right,x,key);
	else return pred(tree[x].left,y,key);
}
           

後繼

int succ(int &x,int y,int key)//查找key的後繼 
{
	if(x==0) return y;
	if(tree[x].key>key) return succ(tree[x].left,x,key);
	else return succ(tree[x].right,y,key);
}
           

删除操作

雖說删除會使樹不再平衡，但是樹的深度不會增加，可以不調用maintain函數。

我們有兩種删除方法。

即用前驅或後繼替換這個元素。

前驅替換

int predremove(int &x,int key)
{
    int kkey;
    //if(!x) return 0;
    --tree[x].size;
    if((key==tree[x].key)||((key<tree[x].key)&&(tree[x].left==0))||((key>tree[x].key)&&(tree[x].right==0)))
    {
        kkey=tree[x].key;
        if((tree[x].left)&&(tree[x].right))
        {
            tree[x].key=predremove(tree[x].left,tree[x].key+1);
        }
        else
        {
            x=tree[x].left+tree[x].right;
        }
    }
    else if(key>tree[x].key) kkey=predremove(tree[x].right,key);
    else if(key<tree[x].key) kkey=predremove(tree[x].left,key);
    return kkey;
}
           

後繼替換

int succremove(int &x,int key) 
{
    --tree[x].size;
    if(key>tree[x].key) succremove(tree[x].right,key);
    else if(key<tree[x].key) succremove(tree[x].left,key);
    else
    {
        //有左子樹，無右子樹
        if((tree[x].left!=0)&&(tree[x].right==0))
        {
            int temp=x;
            x=tree[x].left;
            return temp;
        }
        else if((tree[x].right!=0)&&(tree[x].left==0))
        {
            int temp=x;
            x=tree[x].right;
            return temp;
        }
        //無左子樹和右子樹
        else if((!tree[x].left)&&(!tree[x].right))
        {
            int temp=x;
            x=0;
            return temp;
        }
        //有右子樹
        else //找到x右子樹中最小元素，也就是找後繼元素
        {
            int temp=tree[x].right;
            while(tree[temp].left) temp=tree[temp].left;
            tree[x].key=tree[temp].key;
            succremove(tree[x].right,tree[temp].key);
        }
    }
}
           

其他查詢操作

實際上幾乎所有的平衡樹查詢都能實作。

查詢最小值或最大值

int getmin(int x)//根為x的子樹中的最小值
{
	while(tree[x].left) x=tree[x].left;
	return tree[x].key;
}
int getmax(int x)
{
	while(tree[x].right) x=tree[x].right;
	return tree[x].key;
}
           

查詢第k小值

int select(int &x,int k)//求第k小數
{
	int r=tree[tree[x].left].size+1;
	if(r==k) return tree[x].key;
	else if(r<k) return select(tree[x].right,k-r);
	else return select(tree[x].left,k);
}
           

查詢排行

int rank(int &x,int key)//求key排第幾
{
	if(key<tree[x].key) return rank(tree[x].left,key);
	else if(key>tree[x].key) return rank(tree[x].right,key)+tree[tree[x].left].size+1;
	return tree[tree[x].left].size+1;
}
           

最後的最後

我為了友善了解，沒有打記錄重複的SBT，其實就是加一個cnt嘛。

SBT其實很好寫的。

祝大家++RP