红黑树与AVL树究竟有何本质区别？

本文共计1452个文字，预计阅读时间需要6分钟。

原文：原文由编程笔记改编

改编后：编程笔记摘录

本文由编程笔记#自由互联小编为大家整理，主要介绍了详解AVL树和红黑树的区别相关的知识，希望对你有一定的参考价值。 本文由编程笔记#自由互联小编为大家整理，主要介绍了详解 AVL 树和红黑树的区别相关的知识，希望对你有一定的参考价值。

（点击上方公众号，可快速关注）

61mon.com/index.php/archives/221/

前面已经分别介绍了两种平衡二叉树：AVL 树和红黑树，先让我们来简单回顾下。

AVL 树，规定其任一结点下左右子树高度不超过 1。

红黑树，规定其必须满足四个性质：

每个结点要么是红的，要么是黑的；

根结点是黑色的；

如果一个结点是红色的，则它的两个孩子都是黑色的；

对于任意一个结点，其到叶子结点的每条路径上都包含相同数目的黑色结点。

对比之下，我们发现：AVL 树可以说是完全平衡的平衡二叉树，因为它的硬性规定就是左右子树高度差不超过 1；而红黑树，更准确地说，它应该是 "几于平衡" 的平衡二叉树，在最坏情况下，红黑相间的路径长度是全黑路径长度的 2 倍。