如何从图片中确定一棵平衡的或完全平衡的二叉搜索树

Question

如果我只有一张图片而不是代码，该如何确定一棵树是否平衡、完全平衡或者不平衡呢？

例如，如果我有这棵树，如何检查它是否平衡、完全平衡或不平衡？能否给出一个完全平衡的树的例子？

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

显然，如果树长成这样，我可以确定它是不平衡的：

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

然而，如果它与上面的内容非常相似，我不知道如何获取它。

这是一棵完美平衡的树：

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

请问有人能为我解释一下吗？

- rullzing

---

虽然BST代表二叉“搜索”树，除了搜索和返回布尔值之外，它仍然可以作为一种非常快速的数据类型来插入、删除、以排序方式读取数据块。然而，正如您在最后一个片段中所展示的那样，AVL并不是完全平衡的二叉树，因为它只考虑到最大级别差异为1。一个完全平衡的二叉树（PBBT）应该关心左右大小差异最大为1，以便在除搜索之外的任务中更加高效。 - Redu

Answer 1

一棵完美平衡的树应该长成这样：

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

平衡树: 你可以说它是平衡的，因为每个节点的左右子树高度差不超过1（在此情况下为0）。

完美树: 你可以说它是完美的，因为节点数量等于2^(n+1)-1，其中n为树的高度，在此情况下(2^3) - 1 = 7。

在你的例子中，第一个树是平衡的，但不完美；第二个既不平衡也不完美。第三个树是平衡的，因为每个节点的左右子树深度相差不超过1，但它不完美，因为节点数为5，而按照完美树的方程应该是7。

编辑：

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

希望能对你有所帮助！

- Sergio Ayestarán

---

谢谢回答。只是想确认一下。 所以因为b有1个子节点，而p有2个子节点，这样它就是平衡的了，对吗？ - rullzing

请注意，完美平衡树意味着它必须满足平衡规则和完美规则。也许你的意思是你有一棵平衡树，请将其添加到问题中吗？ - Sergio Ayestarán

当然。我刚刚把它添加到问题中了。 - rullzing

我非常确定第三个是完全平衡的，因为我在考试中得到了这个答案。我还发现了另一棵完全平衡的树，但它不符合规则：2^(n+1) -1。所以我想知道是否有另一种方法适用于所有情况。 - rullzing

它怎么平衡，既然A没有子节点而P有两个呢？ - rullzing

Answer 2

一个完美平衡的AVL树左子树和右子树的高度差不超过1。

- Edward Bamber

---

我知道定义，但不确定如何应用它。 - rullzing

“完美平衡”不就是零的差异吗？ - committedandroider

这是不正确的... 在左右子树之间高度差不超过1的情况下，AVL树被称为平衡AVL树。 - Maderas

Answer 3

问题应该是关于二叉树（BT）的一般性内容，而不仅仅是二叉搜索树（BST），因为节点中数据的顺序与树是否平衡无关。一个起点是https://en.wikipedia.org/wiki/Binary_tree，但它存在一些问题，因为它是对各种可能定义的混合，一些来自计算机科学，一些来自图论。可能最有用、不矛盾的定义集如下：

一个二叉树是“完美的”或“高度平衡的”，如果每个叶子节点在相同的层级，这等价于从给定节点到叶子节点的每条路径长度相同；它是“满的”，如果每个内部（非叶子）节点有2个子节点；它是“完整的”，如果它是完美和满的；它是“几乎完整的”或“近乎完整的”，如果它是完美的，并且除了最后一层之外的所有层都是满的，并且在最后一层中，叶子节点尽可能靠左（因此任何“空缺”都在右边）；它是“退化的”，如果每个非叶子节点只有一个子节点（并且作为图形，它是从根到一个叶子的路径）。

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

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

Sergio的例子是完整的（完美或高度平衡，且完整）。 （请注意，使用“平衡”表示“1高度平衡”，或使用“完美”作为“完整”的同义词，这样做并不好，只会引起混淆。）

“比完美（或完美平衡）更宽松的是k高度平衡，这意味着从给定节点到叶子的所有路径长度最多相差k，这等价于每个节点的左右子树高度差最多为k。例如，AVL树是1高度平衡的。”

“这些定义需要“高度”的原因在于有一个不同的概念叫做“权重平衡BT”，具体定义取决于用途，其中之一是对于每个节点，左子树中的节点数与右子树中的节点数相同，另一个定义是左子树中的节点数至少是右子树中节点数的一半且最多是两倍。”

- wwwayne