关于左偏树的最大深度

@GK0328 2021-02-23 18:20 回复

左偏树最近叶子节点的深度为 $\log n$

那么关于左偏树的最大深度是否为 $\log n$？

@lgswdn 2021-02-23 18:28 回复 举报

@GK0328 左偏树只是最近的叶子深度为log吧

@破忆  2021-02-23 18:31 回复 举报

最近外节点的距离为 $\log n$，外节点是指左子树或右子树为空的节点

最大深度可以达到 $n$，此时的左偏树是一条向左的链

@GK0328 2021-02-23 18:38 回复 举报

@破忆

但是左偏树在合并的时候应该不可能合并出这样一条链吧？

@JacderZhang  2021-02-23 21:33 回复 举报

@GK0328 左偏树不都是合并出来的吗？插入不也是新建一个1个节点的然后合并？

@GK0328 2021-02-23 21:41 回复 举报

@JacderZhang

所以不会出现链吧？