问平衡树的定义

EN

这两件事没有区别。想想看。

让我们来看一个更简单的定义，“一个正数是偶数，如果它是零，或者负二是偶数。”这是不是说，如果6是偶数，8也是偶数？或者说，如果6、4、2和0是偶数，那么8是偶数吗？

这没什么区别。如果它说8即使6是偶数，它也说6是偶数如果4是偶数。因此它也说4是偶数，如果2是偶数。因此它说2是偶数，如果0是偶数。因此，如果它说8是偶数，如果6是偶数，它(间接)说8是偶数，如果6，4，2和0是偶数。

这里也是一样的。任何间接子树都可以通过直接子树链找到。因此，即使它只直接应用于直接子树，它仍然间接应用于所有子树(因此也适用于所有节点)。

平衡树是一种树，其高度是log(树中元素的数量)的数量级。

height = O(log(n))
O, as in asymptotic notation i.e. height should have same or lower asymptotic
growth rate than log(n)
n: number of elements in the tree

给出的定义是“一棵树是平衡的，每个子树都是平衡的，两个子树的高度最多相差一个”，随后是AVL树。

由于AVL树是平衡的，但并不是所有的平衡树都是AVL树，所以平衡树不具有这个定义，并且内部节点可能是不平衡的。但是，AVL树需要平衡所有内部节点。

平衡树的目标是以最小的遍历(最小高度)到达树叶。树的度数是分支数减1。平衡树可能不是二进制的。