权重平衡树有很多定义。我很困惑该遵循哪一个，并且很难理解给出的定义。
A node is balanced if weight[n.left] ≥ weight[n] and weight[n.right] ≥ weight[n]
Number of nodes in the left and right sub tree must be equal
A weight-balanced tree is a binary tree in which for each node, the number of nodes in the left sub tree is at least half and at most twice the number of nodes in the right sub tree.
有人可以解释一下哪个是正确的吗？
最佳答案
据我了解，wbt 中节点 n 的余额 p() 由下式给出:
p(n) = s(n.l)/s(n) = 1 - s(n.r)/s(n)
其中s是后代叶子的数量。您现在可以开始使用旋转和双旋转操作来重新平衡树。现在，如果叶子的数量为偶数，则对于每个节点，左侧节点和右侧节点的子节点数量相等，这一说法为真。这仅适用于平衡 WBT。这并不总是可能的，如果你有 6 个叶子，你如何平衡它以使该陈述成立？
重新平衡会降低 wbt 的高度。
示例:您有一个 wbt，左侧节点有 100 万个叶子，右侧节点有几个叶子。现在可以开始旋转叶子，使左子树的叶子数量为
at least half and at most twice the number of nodes in the right sub tree
一个声明是:
The tree is of bounded balance a if for every node
a <= p(n) <= 1-a
关于algorithm - 权重平衡树的确切定义是什么？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/32263870/