为什么说AVL树是严格平衡的,而红黑树不是严格平衡的
发布于 6 年前 作者 linxiaoziruo 3037 次浏览 来自 问答

为什么说AVL树是严格平衡的,而红黑树不是严格平衡的?红黑树经过旋转不也是平衡树吗?怎么还说红黑树不是严格平衡的呢?

1 回复

是否严格平衡,看任意分支的高度差,如果我没有记错的话 AVL:各个分支之间的高度差最多是1,整棵树是绝对平衡。 RBT:最长的分支(红黑节点间隔出现)比最短的分支(纯黑节点)长一倍。分支之间的高度差比较大,但是树整体上大致平衡。

回到顶部