数据结构——Size_Balanced_Tree 的实现代码
本帖最后由 Knuth学徒 于 2011-2-7 11:06 编辑SBT和AVL、红黑树一样都是高效率二叉搜索树，它是由国家集训队的陈启峰发明的，论文在2007年的冬令营发表。
它通过维护节点的size域来保持平衡，相比较 AVL、红黑，SBT在各种操作上有着不逊色的最坏时间复杂度，而且SBT易于编写。
注：代码均是由我本人编写，不保证效率最高，也不保证没有编译错误等。
SBT的性质：
（1） size] ≥ MAX{ size]] , size]] }
（2） size]≥ MAX{ size]]} , size]] }
节点结构：
typedef struct node{
int data; //节点的键值
int size; //以该节点为根的子树的节点个数
struct node *lch,*rch;
}SBTnode,*SBTree;
SBT的各种操作：
关键操作（*）MainTain：SBTree maintain(SBTree root, bool flag)
//将以root为根的子树进行调整，调整成SBT，flag 参数代表插入节点的左右情况
{
if(!root)//空树
return root;
if(!flag ){//key < root -> data ,key插入在左子树
if(root -> lch && root -> lch -> lch && (root -> rch || root -> lch -> lch -> size > root -> rch -> size))
//第一种情况:size]] > size] 违背了SBT的性质(1)
root = R_rot(root); //右旋root
else if(root -> lch && root -> lch -> rch && (root -> rch || root -> lch -> rch -> size > root -> rch -> size)){
//第二种情况： size]] > size]违背了SBT的性质（1）
root -> lch = L_rot(root -> lch); //先对 左子树 左旋
root = R_rot(root); //再对 根节点 右旋
}
else
return root;
}
else
{
if(root -> rch && root -> rch -> rch && (root -> lch || root -> rch -> rch -> size > root -> lch -> size))
//第三种情况： size]] > size]违背了SBT的性质（2）
root = L_rot(root);//左旋 root
else if(root -> rch && root -> rch -> lch && (root -> lch || root -> rch -> lch -> size > root -> lch -> size)){
//第四种情况： size]] > size] 违背了SBT的性质（2）
root -> rch = R_rot(root -> rch) //先对 右子树 右旋
root = L_rot(root); //再对 根节点 左旋
}
else
return root;
}
root -> lch = maintain(root -> lch , false);//修复左子树
root -> rch = maintain(root -> rch , true );//修复右子树
root = maintain(root, true);
root = maintain(root ,false); //修复整棵树
return root; //返回根节点
}插入函数：SBTree insert(SBTree root, int key)
//在以ROOT为根的子树中插入key, 同时更新这棵树每个节点的size域，再保持SBT的性质 , 最后返回根的指针
{
if(!root)
{
SBTree root = new SBTnode;
root -> data= key;
root -> lch = root -> rch = NULL;
root -> size = 1;
}
else
{
root -> size ++; //树的节点个数 + 1
if(key < root -> data)
{
root -> lch = insert(root -> lch ,key );
root = maintain(root , false ) //传入false给 maintain
//其中 false 的结果是表达式 —— key > root -> data得到
}
else
{
root -> rch = insert(root - >rch ,key );
root = maintain(root , true ) //传入true给 maintain
// 其中true的结果是表达式 —— key > root -> data 得到
}
}
return root ;
}
删除操作：SBTree remove(SBTree root , int key)
//在以root为根的子树中插入key ，同时更新这棵树的每个节点的size域，再保持SBT性质，最后返回实际删除节点的指针
{
if(!root)
return root;
root -> size --;//根节点的大小 - 1
if(key == root -> data
|| (!root -> lch && key < root -> data)
|| (!root -> rch && key > root -> data))
{
SBTree del;
if(!root -> lch || !root -> rch){//如果root有一个节点是空节点
del = root ;
root = (root -> lch ? root -> lch : root -> rch) ;//用root的非空的子节点代替
}
else{
del = remove(root -> rch , key);
root -> key = del -> key;
}
return del;
}
else
{
return remove( key < root -> key ? root -> lch : root -> rch , key ) ;
//根据 二叉搜索树的 性质 递归
}
}SBT树和TREAP一样非常易于编写，只不过SBT树发明的比较晚，任意一本数据结构书上均没有。
当然，SBT树在数学上可以严格证明效率和AVL一样，而且SBT在AVL上有常数级的优化。 SBT树的写法是具有革命性的，我有强烈的预感这会代替用了几十年的AVL，以后的计算机系的同学们不用再为 AVL发愁了。
页:
[1]