摘自《ACM/ICPC算法训练教程》
键值是用于比较节点的大小
距离则是如下定义的：节点i称为外节点，当且仅当节点i的左子树或右子树为空；节点i的距离时节点i到他的后代中，最近的外节点所经过的边数。特别地，如果节点i本身是外节点，则它的距离为0；而空节点的距离规定为-1。
左偏树的4条性质：
(1)节点的键值小于或等于它的左右子节点的键值
(2)节点的左子节点的距离不小于右子节点的距离
(3)节点的距离等于它的右子节点的距离加1
(4)一颗N个节点的左偏树距离最多为log(N+1)-1
(1)左偏树的合并
c <- Merge(A,B)
Merge()把A、B两颗左偏树合并，返回一颗新的左偏树C，包含A和B中的所有元素。这里一颗左偏树用它的根节点指针表示。
在合并操作中，最简单的情况是其中一棵树为NULL，这时只需要返回另一棵树。
若A和B都非空，假设A的根节点小于等于B的根节点(否则交换A、B)，把A的根节点作为新树C的根节点，剩下的事就是合并A的右子树和B了
合并Right(A)和B之后，right(A)的距离可能会变大，当right(A)的距离大于left(A)的距离时，左偏树的性质(2)会被破坏，在这时，只需要交换left(A)和right(B);
最后，由于right(A)的距离可能发生改变，必须更新A的距离。
(2)插入新节点
单节点的树一定是左偏树，因此向左偏树插入一个节点可以看做是对两颗左偏树的合并。
(3)删除节点
删除根节点后，只需要把左子树和右子树合并。
/* */ #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAXN = 10000; struct Tree{ int value; int dist; Tree *left,*right; }; Tree* tree[MAXN]; int distance(Tree* t){ return t==NULL?0:t->dist; } void fixdist(Tree* t){ if(distance(t->left) < distance(t->right)){ swap(t->left,t->right); } t->dist = distance(t->right)+1; } Tree* merge(Tree* a,Tree* b){ if(a==NULL)return b; if(b==NULL)return a; if(b->value > a->value){//最大堆 swap(a,b); } a->right = merge(a->right,b); fixdist(a); return a; } Tree* delMax(Tree* t){ if(t!=NULL){ return merge(t->left,t->right); } return NULL; } void init(Tree* &t,int value){ t = new Tree; t->dist = 1; t->value = value; t->left = t->right = NULL; } Tree* insert(Tree* t,int value){ Tree* p; init(p,value); return merge(t,p); } int main() { return 0; }
