如何确定平衡或完美平衡的二进制搜索树(仅从图片中)

Question

我不确定如何确定树是平衡的,完美平衡的,或者如果我将它作为图片而不是代码则不然

例如,如果我有这棵树我怎样才能检查它是否平衡,完美平衡或不平衡？并且有人能给我一个完美平衡树的例子吗？

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

很明显,如果它是这样的话,我可以说这棵树是不平衡的:

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

但是,如果它与上面的那个非常类似,我不知道如何得到它

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

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

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

Answer 1

完美平衡的树应该如下所示:

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

平衡:你可以说它是平衡的,因为每个节点的左右子树的高度相差1或更小(在这种情况下为0),

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

在你的例子中,第一棵树是平衡的,但不完美,第二棵树不平衡也不完美.第三个是平衡的,因为每个节点上左右子树的深度在1或更小时不同,但它并不完美,因为根据完美的树方程,当它应该是7时节点的数量是5.

编辑:

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

希望能帮助到你!