认识
提示
红黑树是一种自平衡（并不是绝对平衡）的二叉查找树，它除了满足二分查找树的特点外，还满足以下条件:
-
节点是红色或黑色
-
根节点必须是黑色节点
-
所有的叶子节点都必须是值为 NULL 的黑节点
-
如果一个节点是红色的，则它两个子节点都是黑色的（从每个叶子到根的所有路径上不能有两个连续的红色节点）
-
从任一节点到达它的每个叶子节点的所有的路径，都有相同数目的黑色节点（黑色平衡）
这些条件保证红黑树的自平衡，保证红黑树从根节点到达每一个叶子节点的最长路径不会超过最短路径的 2 倍。
红黑树与平衡二叉树（AVL）对比:
-
插入和删除操作，一般认为红黑树的删除和插入会比 AVL 树更快。因为，红黑树不像 AVL 树那样严格的要求平衡因子小于等于1，这就减少了为了达到平衡而进行的旋转操作次数，可以说是牺牲严格平衡性来换取更快的插入和删除时间
-
红黑树不要求有不严格的平衡性控制，但是红黑树的特点，使得任何不平衡都会在三次旋转之内解决。而 AVL 树如果不平衡，并不会控制旋转操作次数，旋转直到平衡为止。
-
查找操作，AVL树的效率更高。因为 AVL 树设计比红黑树更加平衡，不会出现平衡因子超过 1 的情况，减少了树的平均搜索长度。
一个红黑树对应一个 2-3-4 树，它们之间的的等价关系:
-
一个元素二节点：等价黑节点
-
两个元素三节点：等价上黑下红，有两种状态（红在黑左叫左倾，红在黑右叫右倾）
-
三个元素四节点：等价上中间黑，下两边红，有一种状态