# 左偏树

## 性质

1. 节点的键值小于或等于它的左右子节点的键值。
2. 节点的左子节点的距离不小于右子节点的距离。
3. 节点的距离等于它的右子节点的距离加1。
4. 一棵N个节点的左偏树root节点的距离最多为log(N+1)-1。

## 操作

### 合并两颗左偏树

Java代码实现合并两棵左偏的最小树：

1. root键值最小的树的右子树与其它树合并；
2. 上步合并结果作为与root键值最小树的右子树。
3. 比较root的左右子树的距离值（s-value），如果右子树大于左子树则交换两棵子树
```public Node merge(Node x, Node y) {
if(x == null)
return y;
if(y == null)
return x;

// if this was a max height biased leftist tree, then the
// next line would be: if(x.element < y.element)
if(x.element.compareTo(y.element) > 0) {
// x.element > y.element
Node temp = x;
x = y;
y = temp;
}

x.rightChild = merge(x.rightChild, y);

if(x.leftChild == null) {
// left child doesn't exist, so move right child to the left side
x.leftChild = x.rightChild;
x.rightChild = null;

} else {
// left child does exist, so compare s-values
if(x.leftChild.s < x.rightChild.s) {
Node temp = x.leftChild;
x.leftChild = x.rightChild;
x.rightChild = temp;
}
// since we know the right child has the lower s-value, we can just
// add one to its s-value
x.s = x.rightChild.s + 1;
}
return x;
}
```

## 参考文献

1. ^ 《左偏树的特点及其应用》黄源河2005全国青少年信息学奥林匹克竞赛冬令营国家集训队论文

## 延伸阅读

• Leftist Trees页面存档备份，存于互联网档案馆）, Sartaj Sahni
• 傅清祥,王晓东 算法与数据结构(第二版) 电子工业出版社
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein Introduction to Algorithms (Second Edition) The MIT Press
• Mark Allen Weiss Data Structures and Algorithm Analysis in C (Second Edition) Pearson Education