红黑树与平衡二叉树

红黑树

红黑树是一种特殊的排序二叉树

什么是红黑树

1. 每个节点要么是红色，要么是黑色
2. 根节点永远是黑色的
3. 所有的叶节点都是空节点（即 null），并且是黑色的
4. 每个红色节点的两个子节点都是黑色
5. 从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点

性质

1. 对于给定的黑色高度为 N 的红黑树，从根到叶子节点的最短路径长度为 N-1，最长路径长度为 2 * (N-1)
2. 红黑树上的插入/删除都会改变红黑树特性，必须进一步进行维护

平衡二叉树

平衡二叉树是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

平衡二叉树与红黑树的区别

平衡二叉树的追求的是全局均衡，如在做插入，删除操作时，需要调整整棵树，显然这是费时的，因此希望在做调整时，是局部调整，因此提出了红黑树，这样一种高效的数据结构(也是最变态的一种数据结构)。

红黑树和平衡二叉树（AVL树）类似，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。

红黑树和AVL树的区别在于它使用颜色来标识结点的高度，它所追求的是局部平衡而不是AVL树中的非常严格的平衡。