为什么说 AVL 树是严格平衡的，而红黑树不是严格平衡的

[linxiaoziruo]

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

[lttzzlll]

严格平衡的定义 任意左右子树高度差不超过 1。其余都是非严格平衡。

[lttzzlll]

叶节点，非任意。

[yidinghe]

红黑树是根据自己那套规则来判断要不要旋转，旋转完之后即使没有达到严格平衡，只要符合规则就处理结束了。这是在执行效率方面所做的取舍。

[linxiaoziruo]

@lttzzlll 没明白你的意思。平衡树的定义不就是“任意左右子树高度差不超过 1 ”吗？

[linxiaoziruo]

@linxiaoziruo 红黑树是平衡树的一种。什么才是严格平衡呢？红黑树又为什么不是严格平衡呢？

[GuuJiang]

这个在红黑树的定义里已经写得很清楚了吧，红黑树的平衡只是保证了各子树的黑高度相等，而由黑高度的定义可以看出最坏情况下最高子树的高度是最低子树高度的两倍

[linxiaoziruo]

@GuuJiang 弄明白了。红黑树不是平衡树，只是接近平衡树。

[mortonnex]

建议楼主顺便了解下:
1.hashmap 中红黑树的使用
2.MySQL 中索引为什么要用 B+树

学习 avl 树可以串联起很多知识

[linxiaoziruo]

各位大佬们，多谢了！工作四五年，从没正儿八经写过这些数据结构，最近在自己重新写，收益颇丰。

[linxiaoziruo]

@GuuJiang 大佬，我看到一篇文章，内容是把 2-3 树演化成“红黑树”，但是这里红色和黑色标志的是“链接”，不是“节点”。红黑树还能这么定义的吗？给链接着色生成的红黑树，和给节点着色产生的红黑树都是红黑树吗？还是说给链接着色的红黑树只不过时作者意淫出来的。