为什么平衡二叉树很重要
问问题
11125 次
5 回答
10
想象一棵看起来像这样的树：
A
\
B
\
C
\
D
\
E
这是一个有效的二叉树，但现在大多数操作都是 O(n) 而不是 O(lg n)。
于 2012-07-16T04:05:27.073 回答
7
二叉树的平衡由称为偏度的属性控制。如果一棵树更偏斜，那么访问二叉树元素的时间复杂度就会增加。说一棵树
1 / \ 2 3 \ \ 7 4 \ 5 \ 6
上面也是一棵二叉树，但是是右偏的。它有 7 个元素，因此理想的二叉树需要 O(log 7) = 3 次查找。但是在最坏的情况下，您需要再深入一层 = 4 次查找。所以这里的偏度是一个常数 1。但是考虑一下树是否有数千个节点。在这种情况下，偏度将更加显着。所以保持二叉树平衡很重要。
但是，偏度再次成为争论的话题，因为随机二叉树的概率分析表明，具有 n 个元素的随机二叉树的平均深度为 4.3 log n。所以这实际上是平衡与偏度的问题。
更有趣的是，计算机科学家甚至发现了偏度的优势，并提出了一种偏斜的数据结构，称为skew heap
于 2012-07-16T12:15:45.240 回答
4
为确保 log(n) 搜索时间，您需要将每个分支的下层节点总数除以 2。例如，如果你有一棵线性树，从不从根节点分支到叶节点，那么搜索时间将是线性的，就像在链表中一样。
于 2012-07-16T04:05:34.713 回答
1
一棵非常不平衡的树，例如所有节点都链接到左侧的树，这意味着您仍然在找到最后一个节点之前搜索每个节点，这根本不是树的点，并且与链表相比没有任何好处. 与 O(n) 相比，平衡树可以获得更好的搜索时间 O(log(n))。
于 2012-07-16T04:07:03.563 回答
0
正如我们所知，二叉搜索树上的大多数操作都与树的高度成正比，因此希望保持高度较小。它确保搜索时间严格到 O(log(n)) 的复杂性。
而不是大多数可用的树平衡技术更多地适用于完全完整或接近完美平衡的树木。
最后，您需要树的简单性，并选择最好的二叉树，如红黑树或 avl
于 2020-02-02T01:33:39.820 回答