问题

Questions in category: 数据结构 (Data Structure).

证明: 对于左式堆(Leftist Heap), 如果其右路径上有 $r$ 个结点, 则此左式树本身至少有 $2^r-1$ 个结点.

Posted by haifeng on 2013-05-02 10:58:54 last update 2013-05-02 11:14:35 | Answers (0) | 收藏

注: 左式树(leftist tree) 即为左式堆(leftist heap). Leftist tree 亦被翻译为左偏树 (参见 http://zh.wikipedia.org/wiki/左偏树 ).

Hint: 使用归纳法证明.