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

Question

为什么平衡二叉树很重要

Answer 1

二叉树的平衡由称为偏度的属性控制。如果树的偏差更大，则访问二叉树的元素的时间复杂度会增加。比如说一棵树

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

上面的也是一个二叉树，但是是右偏的。它有7个元素，所以理想的二叉树需要O(Log7)=3次查找。但在最坏的情况下，您需要进行更深一层=4次查找。所以这里的偏斜度是一个常数1，但考虑一下如果树有数千个节点。在这种情况下，偏斜度将更加显著。因此，保持二叉树的平衡很重要。

但偏度再次成为争论的主题，因为对随机二叉树的概率分析表明，random binary tree with n elements is 4.3 log n的平均深度。因此，这实际上是平衡与偏斜的问题。

更有趣的是，计算机科学家甚至发现了这种不对称的优势，并提出了一种称为skew heap的不对称数据结构

Answer 2

假设有一棵树看起来像这样：

  A
   \
    B
     \
      C
       \
        D
         \
          E

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

Answer 3

为了保证log(n)搜索时间，您需要将每个分支的下级节点总数除以2。例如，如果您有一个线性树，从不从根到叶节点分支，那么搜索时间将是线性的，就像在链表中一样。