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

Question

为什么平衡二叉树很重要

Answer 1

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

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

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

但偏度再次成为争论的话题，因为随机二叉树的概率分析表明 random binary tree with n elements is 4.3 log n 的平均深度.所以这真的是平衡与偏度的问题。

更有趣的是，计算机科学家甚至发现了偏态的优势，并提出了一种名为 skew heap的偏态数据结构。