[科普中国]-左高树

左高树是一棵二叉树，且如果该二叉树不空，则对其中的每个内部结点x，都有左儿子到一个外部结点的最短路程长度大于或等于右儿子到一个外部结点的最短路程长度。

左高树定义设x是扩充二叉树的一个结点，并令left_child(x)和right_child(x)分别表示内部结点的左、右儿子。定义shortest(x)为从x到一个外部结点的最短路程长度。

左高树是一棵二叉树，且如果该二叉树不空，则对其中的每个内部结点x，都有：

Shortest(left_child(x))>= Shortest(right_child(x))。

左高树的一个应用是合并操作，应用场景是:当某个优先队列的服务器关闭时,就需要将其与另一个正在运行服务器的优先队列合并。如果两个队列的元素总数为n，则一般的堆结构的复杂度为O(n),但是左高树可以达到O(logn)。插入和删除操作都可以通过合并操作来完成。1

研究背景堆结构是一种隐式数据结构（implicit data structure），用完全二叉树表示的堆在数组中是隐式存贮的（即没有明确的指针或其他数据能够重构这种结构）。由于没有存贮结构信息，这种描述方法空间利用率很高，事实上没有空间浪费。尽管堆结构的时间和空间效率都很高，但它不适合于所有优先队列的应用，尤其是当需要合并两个优先队列或多个长度不同的队列时。因此需要借助于其他数据结构来实现这类应用，左高树（leftist tree）就能满足这种要求。

令s (x)为从节点x到它的子树的外部节点的所有路径中最短的一条，根据s(x)的定义可知，

若x是外部节点，则s的值为0，若x为内部节点，则它的s值是：

其中L与R分别为x的左右孩子。2

最小左高树定义及操作最小（最大）左高树是一棵左高树，其中的每个内部结点的关键字值不大于（不小于）该结点的儿子结点的关键字值。

对于最小左高树的操作，插入和删除最小元素操作都可以通过合并操作来完成。要把元素x插入到左高树A中，先建立一棵只有一个元素x的最小左高树B，再合并最小左高树A和B。要从一棵非空最小左高树A删除最小元素，则只需合并最小左高树A的左子树和右子树，再把最小左高树的根结点删除。

以下重点介绍最小左高树的合并操作。

假设要合并最小左高树A和B，首先，沿着A和B的最右路径，得到一棵包含A和B所有元素的二叉树（注意：这里只是得到二叉树，而不是最小左高树）。使得该二叉树具有以下性质：所有结点的关键字都不大于其儿子结点关键字。必要时交换结点的左、右子树，将其转化为最小左高树。

合并操作1、假设合并最小左高树A和B，首先比较两棵树根结点的关键字值，以最小的关键字作为新二叉树的根结点。

2、保留A的左子树不变，将其右子树与最小左高树B合并，合并后的二叉树成为新的A的右子树。

3、把二叉树转换为最小左高树从最后一个修改结点（注意：这里不是最后结点）开始，回溯到最终的树根结点，使得路径上的所有结点满足不等式：shortest（left_child()）>= shortest（right_child()）1

高度优先左高树定义当且仅当一棵二叉树的任何一个内部节点，其左孩子的s值大于等于右孩子的s值时，该二叉树为高度优先左高树（height-biased leftist tree, HBLT）。

最大****HBLT即同时又是最大树的HBLT；

最小****HBLT即同时又是最小树的HBLT。

最大优先队列可以用最大HBLT表示，最小优先队列可用最小HBLT表示。可以通过考察子树的节点数目而不是从根到外部节点的路径来得到另一类左高树。定义x的重量w(x)为以x为根的子树的内部节点数目。注意到若x是外部节点，则其重量为0；若x为内部节点，其重量为其孩子节点的重量之和加1，图中二叉树各节点的重量如图d所示。

定理令x为一个HBLT的内部节点，则

1)以x为根的子树的节点数目至少为2s (x)-1。

2)若子树x有m个节点，s (x)最多为l o g2(m+ 1 )。

3)通过最右路径（即，此路径是从x开始沿右孩子移动）从x到达外部节点的路径长度为s (x)。

证明：根据s (x)的定义可知，从x节点往下第s (x)-1层没有外部节点（否则x的s值将更小）。

以x为根的子树在当前层只有一个节点x，下一层有两个，再下一层有四个，⋯⋯，x层往下第s (x)-1层有个2s (x) - 1，在s (x)-1层以下可能还有其他节点，因此子树x的节点数目至少为i=s (x) - 12i= 2s (x)-1。

从1)可以推出2）。

根据s的定义以及HBLT一个节点的左孩子的s值总是大于等于其右孩子的s值，可以推得3）成立。2

重量优先左高树当且仅当一棵二叉树的任何一个内部节点，其左孩子的w值大于等于右孩子的w值时，该二叉树为重量优先左高树（weight-biased leftist tree, WBLT）；最大（小）WBLT 即同时又是最大（小）树的WBLT。

同HBLT类似，具有m个节点的WBLT的最右路径长度最多为log2(m+ 1 )。可以对WBLT与HBLT执行优先队列的查找、插入、删除操作，其时间复杂性与堆的相应操作相同。同堆一样，WBLT与HBLT可在线性时间内完成初始化。用WBLT或HBLT描述的两个优先队列可在对数时间内合并为一个，而当用堆描述优先队列时，则不能在对数时间内完成合并。2

本词条内容贡献者为:

王伟 - 副教授 - 上海交通大学