【算法学习】有旋treap

treap是平衡树的一种。与其他平衡树一样，它也能够支持插入和删除，求第k极值等，接下来我们主要探讨有旋treap的实现过程。

treap中每个节点要维护其值，左右孩子以及子树大小。父亲要不要写则看你的写法了，如果用的是指针或引用传入，则没有必要写。

特别的是，treap的每个节点还需要维护另一个值——它的优先度，优先度在节点新建时就赋值，并且在节点删除前不会改变。

treap的平衡性就取决于这个关键的值，这个值在一开始是随机赋值的，在建立平衡树时，还需要让结点的优先度有堆性质！

即意结点的原值要呈二叉排序树结构，而结点的“优先度”要满足父节点的优先度比两个儿子结点的优先度都要大！

也就是说treap既是一棵二叉排序树，还是一个堆【其实只是有堆性质，并不是严谨的堆的定义】！

这意味着当每个结点的优先度都不同时，这棵树只有一种排列方式满足它既是二叉排序树，也是堆（想一想为什么）。

而这种排列方式平均来说是平衡的，即它的树高正比于logn。这是因为优先度是随机赋值的，随机化思想给了它这个性质。

在修改时，不需要刻意维护平衡，只要当其堆性质被破坏，把它恢复就可以了。

====

接下来看具体实现过程：

我用的是指针+引用写法，目前写了插入，删除和查询某节点的排名。

接下来我们边看代码边分析：

 namespace Treap{//我专门搞了个命名空间……
 }

 struct node{//这里是结点的结构体定义，要注意每个东西都要指针，因为这是指针写法
     int val,pri,siz;//值，优先度和子树大小
     node* son[];//孩子
     node();//构造函数，定义在下面
 }*null=new node,*root=new node;//空结点(null)和根结点(root)
 node::node(){son[]=son[]=null;}//在结构体外定义构造函数要加"::"

 inline ]->siz+x->son[]->siz+;}//这个函数用于更新结点的子树大小

 inline void rotate(node* &x,bool lr){//典型的平衡树旋转函数
 //传进去的第一个是引用的节点指针，第二个表示左/右旋
 //传指针不奇怪，传引用是为什么呢？
 //这是因为在旋转时把结点x和它的左/右孩子互换了位置，x原来的父亲现在的孩子指针要修改，可是我们没有父亲指针，所以传引用，在指针x的地址改变时，调用它时的传进去的父亲的孩子指针也会改变。
     node *v=x->son[lr^],*vs=v->son[lr];//保存一下中间变量
     x->son[lr^]=vs;//往一边旋，x的新“另一边”孩子就是x的原“另一边”孩子的“同一边”孩子
     v->son[lr]=x;//而要旋转的另一个结点的孩子改变为x
     combine(x);combine(v);//重新计算siz
     x=v;//改变x的指针，指向子树的新根，这样可以使原父亲的孩子指针也变化
 }

先写到这里……以后再补充

巴特西

【算法学习】有旋treap

最新文章

热门文章