为什么二叉树平衡很重要？

Question

为什么二元树要平衡很重要

Answer 1

想象一下这样的树:

  A
   \
    B
     \
      C
       \
        D
         \
          E

这是一个有效的二叉树,但现在大多数操作都是O(n)而不是O(lg n).

Answer 2

二叉树的平衡由称为偏斜的属性控制.如果树更倾斜,则访问二叉树的元素的时间复杂度增加.说一棵树

                1
               / \
              2   3
              \    \
               7    4
                     \
                      5
                       \
                        6

以上也是一棵二叉树,但右倾斜.它有7个元素,因此理想的二叉树需要O(log 7)= 3个查找.但是在最坏的情况下,你需要再深一级= 4次查找.所以这里的偏度是常数1.但请考虑树是否有数千个节点.在这种情况下,偏斜将更加可观.因此保持二叉树平衡很重要.

但是,随机二叉树的可能性分析表明,具有n个元素的随机二叉树的平均深度为4.3 log n,因此偏差再次成为辩论的主题.所以这实际上是平衡与偏斜的关系.

另一个有趣的事情是,计算机科学家甚至发现了偏斜的优势,并提出了一种称为倾斜堆的倾斜数据结构