数据结构中的重量倾向左倾树

这里我们将介绍左倾树的另一种变体。这里我们将考虑子树中的节点数，而不是从根到外部节点的最短路径长度。这里我们将定义节点 x 的权重 w(x)，即以 x 为根的子树中内部节点的数目。如果 x 是外部节点，那么权重为 0。如果 x 是内部节点，那么权重将比其子节点权重的总和多 1。

以下是一个重量倾向左倾树 (WBLT) 的示例−

假设二叉树如下−

如果我们计算每个节点的 w(x) 值，它将如下−

现在 WBLT 的定义如下−

如果且仅当树中每个内部节点的左子节点的 w(x) 大于或等于右子节点的 w(x)，那么一棵二叉树称为重量平衡左倾树。最大 (最小) WBLT 是一棵最大 (最小) 树，同时也是一棵 WBLT。

更新日期：2020-08-11

1000+ 浏览量

开启你的职业生涯

完成课程获得认证

开始学习
广告