数据结构——Size_Balanced_Tree 的实现代码

Knuth学徒

SBT和AVL、红黑树一样都是高效率二叉搜索树，它是由国家集训队的陈启峰发明的，论文在2007年的冬令营发表。

    它通过维护节点的size域来保持平衡，相比较 AVL、红黑，SBT在各种操作上有着不逊色的最坏时间复杂度，而且SBT易于编写。



注：代码均是由我本人编写，不保证效率最高，也不保证没有编译错误等。



SBT的性质：

（1） size[right[T]] ≥ MAX{ size[left[left[T]]] , size[left[right[T]]] }

（2） size[left[T]]  ≥ MAX{ size[right[right[T]]]} , size[right[left[T]]] }



节点结构：
typedef struct node{
    int data;              //节点的键值
    int size;              //以该节点为根的子树的节点个数
    struct node *lch,*rch;
}SBTnode,*SBTree;

SBT的各种操作：

关键操作（*）MainTain：

1. SBTree maintain(SBTree root, bool flag)
   
2. //将以root为根的子树进行调整，调整成SBT，flag 参数代表插入节点的左右情况
   
3. {
   
4.      if(!root)  //空树
   
5.           return root;
   
6.      if(!flag ){  //  key < root -> data ,  key插入在左子树
   
7.           if(root -> lch && root -> lch -> lch && (root -> rch || root -> lch -> lch -> size > root -> rch -> size))  
   
8.               //第一种情况:  size[left[left[T]]] > size[right[T]]   违背了SBT的性质(1)
   
9.               root = R_rot(root);   //右旋root
   
10.           else if(root -> lch && root -> lch -> rch && (root -> rch || root -> lch -> rch -> size > root -> rch -> size)){
    
11.               //第二种情况： size[right[left[T]]] > size[right[T]]  违背了SBT的性质（1）
    
12.               root -> lch = L_rot(root -> lch); //先对 左子树 左旋
    
13.               root = R_rot(root);               //再对 根节点 右旋
    
14.           }
    
15.           else
    
16.               return root;
    
17.      }
    
18.      else
    
19.      {
    
20.           if(root -> rch && root -> rch -> rch && (root -> lch || root -> rch -> rch -> size > root -> lch -> size))
    
21.               //第三种情况： size[right[right[T]]] > size[left[T]]  违背了SBT的性质（2）
    
22.               root = L_rot(root);  //左旋 root
    
23.           else if(root -> rch && root -> rch -> lch && (root -> lch || root -> rch -> lch -> size > root -> lch -> size)){
    
24.               //第四种情况： size[right[left[T]]] > size[left[T]]   违背了SBT的性质（2）
    
25.               root -> rch = R_rot(root -> rch)   //先对 右子树 右旋
    
26.               root = L_rot(root);                //再对 根节点 左旋
    
27.           }
    
28.           else
    
29.               return root;
    
30.       }
    
31.       
    
32.       root -> lch = maintain(root -> lch , false);  //修复左子树
    
33.       root -> rch = maintain(root -> rch , true );  //修复右子树
    
34. 
    
35.       root = maintain(root, true);
    
36.       root = maintain(root ,false);   //修复整棵树
    
37.       return root;   //返回根节点
    
38. }

复制代码

插入函数：

1. SBTree insert(SBTree root, int key)
   
2. //在以ROOT为根的子树中插入key, 同时更新这棵树每个节点的size域，再保持SBT的性质 , 最后返回根的指针
   
3. {
   
4.      if(!root)
   
5.      {
   
6.            SBTree root = new SBTnode;
   
7.            root -> data  = key;
   
8.            root -> lch = root -> rch = NULL;
   
9.            root -> size = 1;
   
10.       }
    
11.       else
    
12.       {
    
13.            root -> size ++;    //树的节点个数 + 1
    
14.            
    
15.            if(key < root -> data)
    
16.            {
    
17.                  root -> lch = insert(root -> lch ,key );
    
18.                  root = maintain(root , false )   //传入false给 maintain
    
19.                  //其中 false 的结果是表达式 —— key > root -> data  得到
    
20.            }
    
21.            else
    
22.            {
    
23.                  root -> rch = insert(root - >rch ,key );
    
24.                  root = maintain(root , true )    //传入true给 maintain
    
25.                  // 其中true  的结果是表达式 —— key > root -> data 得到
    
26.            }
    
27.        }
    
28.       
    
29.        return root ;
    
30. }
    

复制代码

删除操作：

1. SBTree remove(SBTree root , int key)
   
2. //在以root为根的子树中插入key ，同时更新这棵树的每个节点的size域，再保持SBT性质，最后返回实际删除节点的指针
   
3. {
   
4.        if(!root)
   
5.             return root;
   
6.        root -> size --;  //根节点的大小 - 1
   
7. 
   
8.        if(key == root -> data
   
9.            || (!root -> lch && key < root -> data)
   
10.              || (!root -> rch && key > root -> data))
    
11.        {
    
12.             SBTree del;
    
13.             if(!root -> lch || !root -> rch){  //如果root有一个节点是空节点
    
14.                   del = root ;
    
15.                   root = (root -> lch ? root -> lch : root -> rch) ;  //用root的非空的子节点代替
    
16.             }
    
17.             else{
    
18.                   del = remove(root -> rch , key);
    
19.                   root -> key = del -> key;
    
20.             }
    
21.             return del;
    
22. 
    
23.         }
    
24.         else
    
25.        {
    
26.             return remove( key < root -> key ? root -> lch : root -> rch , key ) ;
    
27.             //根据 二叉搜索树的 性质 递归
    
28.        }
    
29. }

复制代码

SBT树和TREAP一样非常易于编写，只不过SBT树发明的比较晚，任意一本数据结构书上均没有。   

当然，SBT树在数学上可以严格证明效率和AVL一样，而且SBT在AVL上有常数级的优化。

Knuth学徒

SBT树的写法是具有革命性的，我有强烈的预感这会代替用了几十年的AVL，以后的计算机系的同学们不用再为 AVL发愁了。