下面我们来讨论左偏树的距离和节点数的关系。

[引理1] 若左偏树的距离为一定值，则节点数最少的左偏树是完全二叉树。

证明:由性质2可知，当且仅当对于一棵左偏树中的每个节点i，都有dist(left(i)) =dist(right(i)) 时，该左偏树的节点数最少。显然具有这样性质的二叉树是完全二叉树。

[定理1] 若一棵左偏树的距离为k，则这棵左偏树至少有2^(k+1)-1个节点。

证明:由引理1可知，当这样的左偏树节点数最少的时候，是一棵完全二叉树。距离为k的完全二叉树高度也为k，节点数为2^(k+1)-1，所以距离为k的左偏树至少有2^(k+1)-1个节点。

作为定理1的推论，我们有:

[性质4] 一棵N个节点的左偏树距离最多为ëlog(N+1)û-1。

证明:设一棵N个节点的左偏树距离为k，由定理1可知，N ≥ 2^(k+1)-1，因此k ≤ ëlog(N+1)û-1。

标程

《数字序列》程序