Java 如何确定平衡或完美平衡的二叉搜索树（仅从图片中）

how to determine a balanced or perfectly balanced Binary search tree ( just from the picture )

提问by rullzing

I am not sure how to determine if a tree is balanced, perfectly balanced, or neither if I have it as a picture not a code

我不知道如何确定一棵树是平衡的，完全平衡的，或者如果我把它作为图片而不是代码

For example if I have this tree How can I check if it's balanced, perfectly balanced, or unbalanced? and can someone give me an example of a perfectly balanced tree?

例如，如果我有这棵树，我如何检查它是平衡的、完全平衡的还是不平衡的？有人能给我一个完美平衡树的例子吗？

    [o]
   /   \
 [b]   [p]
   \    / \
  [d]  [m] [r]

Clearly I can tell that the tree is unbalanced if it was something like this:

很明显，如果树是这样的，我可以说树是不平衡的：

      [b]
        \
        [d]
         \
          [r]
           \
           [c]

However, if it was something very similar to the one above I don't know how to get it

但是，如果它与上面的非常相似，我不知道如何获得它

This is a perfectly balanced and balanced tree:

这是一个完美平衡和平衡的树：

        [k]
       /   \
      [A]   [p]
            /  \
           [N]  [R]

Can someone please explain it to me?

有人可以向我解释一下吗？

采纳答案by Sergio Ayestarán

A perfectly balanced tree should look like this:

一个完美平衡的树应该是这样的：

       [ R ]
      /     \
    [a]      [b]
   /   \     /  \
 [c]   [d] [e]  [f]

Balanced: You can say it is balanced because the height of the left and right subtrees from every node differ by 1 or less (0 in this case),

Balanced：你可以说它是平衡的，因为每个节点的左右子树的高度相差 1 或更少（在这种情况下为 0），

Perfect: You can say it is perfect because the number of nodes is equal to 2^(n+1)-1 with n being the height of the tree, in this case (2^3) - 1 = 7

完美：你可以说它是完美的，因为节点数等于 2^(n+1)-1，n 是树的高度，在这种情况下 (2^3) - 1 = 7

In your examples the 1st tree is balanced, but not perfect, the second is not balanced nor perfect. The third one is balanced because the depth for the left and right subtree on every node differ on 1 or less, but it is not perfect because the number of nodes is 5 when it should be 7 according to the perfect tree equation.

在您的示例中，第一棵树是平衡的，但并不完美，第二棵树既不平衡也不完美。第三个是平衡的，因为每个节点上左右子树的深度相差 1 或更少，但它并不完美，因为根据完美树方程应该是 7 时节点数是 5。

EDIT:

编辑：

Regarding your lasts comments, the fact that you got it in an exam doesn't mean the answer was right in every sense. The notion of perfect tree is related to the notion of completeness, a complete tree is sometimes called a "perfect" tree, and it means the number of children for every node except the leafs is 2 what i gave you is an equation to calculate it. The third tree is balanced because what matters is the depth of the left and right subtrees for every node, not the number of children in the left and right subtrees. In this case from node A the depth of left subtree is 0 and the depth of right subtree is 0 -> 0 - 0 = 0, from P both depth are 1 -> 1 - 1 = 0 and from the root the depth from the left subtree is 1 and from the right subtree is 2 -> 2 - 1 = 1 <- it is balanced, since the difference should be 1 or less.

关于你最后的评论，你在考试中得到它的事实并不意味着答案在任何意义上都是正确的。完美树的概念与完整性的概念有关，完整的树有时被称为“完美”树，这意味着除了叶子之外的每个节点的子节点数是 2 我给你的是一个计算它的方程. 第三棵树是平衡的，因为重要的是每个节点的左右子树的深度，而不是左右子树中子树的数量。在这种情况下，从节点 A 开始，左子树的深度为 0，右子树的深度为 0 -> 0 - 0 = 0，从 P 开始，两个深度都是 1 -> 1 - 1 = 0，从根开始的深度为左子树是 1，从右子树是 2 -> 2 - 1 = 1 <- 它是平衡的，因为差异应该是 1 或更小。

Hope it helps!

希望能帮助到你！

回答by Edward Bamber

A perfectly balanced AVL tree will have a height difference of no more than 1 between the left subtree and the right subtree

完美平衡的 AVL 树的左子树和右子树之间的高度差不会超过 1

回答by wwwayne

The question should be about binary trees (BTs) in general, not just binary search trees (BSTs), since the order of the data in the nodes has nothing to do with whether or not the tree is balanced. One place to start is https://en.wikipedia.org/wiki/Binary_tree, but it has some problems since it is a bit of a mish-mosh of various possible definitions, some from CS and some from graph theory. Probably the most useful, non-contradictory set of definitions is:

问题应该是关于二叉树 (BT)，而不仅仅是二叉搜索树 (BST)，因为节点中数据的顺序与树是否平衡无关。一个开始的地方是https://en.wikipedia.org/wiki/Binary_tree，但它有一些问题，因为它是各种可能定义的混合体，一些来自 CS，一些来自图论。可能最有用、最不矛盾的一组定义是：

A BT is perfector height-balancedif every leaf is at the same level, which is equivalent to every path from a given node to a leaf being the same length; it is fullif every internal (non-leaf) node has 2 children; it is completeif it is perfect and full; it is almost completeor nearly completeif is perfect and all levels but the last are full, and in the last level leaves are as far left as possible (so any "vacancies" are to the right); it is degenerateif every non-leaf node has just one child (and as a graph it is a path from the root to the one leaf).

如果每个叶子都在同一级别，则BT 是完美的或高度平衡的，这相当于从给定节点到叶子的每条路径都具有相同的长度；如果每个内部（非叶）节点都有 2 个子节点，则它是满的；它是完整的，如果它是完美的，完整的; 如果是完美的，并且除最后一层以外的所有级别都已满，则几乎完成或接近完成，并且最后一层的叶子尽可能向左（因此任何“空缺”都在右侧）；如果每个非叶子节点只有一个子节点（并且作为图，它是从根到一个叶子的路径），则它是退化的。

Using these definitions: your first tree is perfect but not full, so not complete--node [b] is missing a left child, and adding it would make the tree complete; your second tree is degenerate(a path); your third tree is full(every node but the leaves has two children) and 1-height-balancedbut neither "perfectly balanced (= perfect?)" or "balanced (meaning 0-height-balanced)"as you claim, since not every path from the root to a leaf is the same length.

使用这些定义：你的第一棵树是完美的但不完整，所以不完整--node [b] 缺少左孩子，添加它会使树完整；你的第二棵树退化了（一条路径）；你的第三棵树是满的（每个节点，但叶子有两个孩子）和1-height-balanced但既不是“完美平衡（=完美？）”或“平衡（意味着 0 高度平衡）”，因为不是从根到叶子的每条路径的长度都相同。

In your first tree, if [b] had two children but [p] had only a left child, then it would be almost complete(perfect and full except for some missing children in the last level and the vacancies as far right at possible)--and these are important for storing binary heaps in arrays.

在你的第一棵树中，如果 [b] 有两个孩子，而 [p] 只有一个左孩子，那么它几乎是完整的（除了最后一层缺少一些孩子和尽可能最右边的空缺之外，它是完美的和完整的） --这些对于在数组中存储二进制堆很重要。

Sergio's example is complete(perfect or height-balanced, and full). (And note that it's not nice and can only cause confusion to use "balanced" to mean "1-height-balanced", or "perfect" as a synonym for "complete".)

塞尔吉奥的例子是完整的（完美的或高度平衡的，完整的）。（请注意，使用“平衡”来表示“1-高度平衡”或“完美”作为“完整”的同义词是不好的，只会引起混淆。）

Something less strict than being perfect (or perfectly-balanced) is being k-height-balanced, which means that the lengths of all paths from a given node to a leaf differ by at most k, which is equivalent to the difference in height of each node's left- and right-subtrees being at most k. For example, an AVL tree is 1-height-balanced.

比完美（或完美平衡）更不严格的是 k 高度平衡，这意味着从给定节点到叶子的所有路径的长度最多相差 k，这相当于高度的差异每个节点的左子树和右子树最多为 k。例如，一棵 AVL 树是 1 高度平衡的。

The reason "height" is needed in these definitions is that there is a different concept of "weight-balanced BT", which has various definitions depending upon the use, with one being that for each node the number of nodes in the left sub-tree is the same as in the right sub-tree, and another being that 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.

这些定义中之所以需要“高度”，是因为“权重平衡BT”有不同的概念，根据用途不同有不同的定义，一个是每个节点左子节点的节点数。树与右子树中的相同，另一个是左子树中的节点数至少是右子树中节点数的一半，最多两倍。