avl树示例我对avl树很困惑。我的教科书上说“avl树是一个bst，它具有高度平衡属性，并且在插入或删除节点时执行特定的操作来重新平衡树。这一部分论述了资产负债的性质；另一节讨论操作。如果对于任何节点，节点的左子树和右子树的高度仅相差0或1，则bst是高度平衡的？是不是因为第二个，从a到f的高度是2？从a到c，再从c到e，再从e到f。我很困惑，原来我以为他们的意思是高度上下。左边的高度是3，右边的高度是2
cbwuti441#
简单地说，我们可以说，如果特定节点的左侧最大的边缘（一个漫长的步行，直到我们到达叶节点） l 和右侧最大边 r 如果他们满足以下等式
l
r
| l - r | <= 1
那么这个节点就平衡了。如果bst中的所有节点都是平衡的，那么该bst就是一个平衡的节点。在avl树示例中，每封信你可以检查如下d-->| 2-1 |=1个平衡节点c-->| 1-0 |=1平衡节点一个-->| 0-0 |=0平衡节点e-->| 0-0 |=0平衡节点在not avl树示例中d-->| 3-2 |=1个平衡节点c-->| 2-0 |=2不平衡节点e-->| 0-1 |=1平衡节点一个-->| 0-1 |=1个平衡节点b-->| 0-0 |=0平衡节点f-->| 0-0 |=0平衡节点当我们至少有一个不平衡的节点，这意味着bst是不平衡的。
1条答案
按热度按时间cbwuti441#
简单地说，我们可以说，如果特定节点的左侧最大的边缘（一个漫长的步行，直到我们到达叶节点）
l和右侧最大边r如果他们满足以下等式那么这个节点就平衡了。如果bst中的所有节点都是平衡的，那么该bst就是一个平衡的节点。
在avl树示例中，
每封信你可以检查如下
d-->| 2-1 |=1个平衡节点
c-->| 1-0 |=1平衡节点
一个-->| 0-0 |=0平衡节点
e-->| 0-0 |=0平衡节点
在not avl树示例中
d-->| 3-2 |=1个平衡节点
c-->| 2-0 |=2不平衡节点
e-->| 0-1 |=1平衡节点
一个-->| 0-1 |=1个平衡节点
b-->| 0-0 |=0平衡节点
f-->| 0-0 |=0平衡节点
当我们至少有一个不平衡的节点，这意味着bst是不平衡的。