红黑树是一种近似平衡的二叉搜索树（Binary Search Tree），它能够确保任何一个结点的左右子树的高度差小于两倍。具体来说，红黑树是满足如下条件的二叉搜索树：
• 每个结点要么是红色，要么是黑色
• 根节点是黑色
• 每个叶节点（NIL节点，空节点）都是黑色的。 （每个叶子节点都是黑色的空节点（NIL），即叶子节点不存储数据，它主要是为了简化红黑树的代码实现而设置的）
• 不能有相邻接的两个红色节点。 （任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的）
• 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。（每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点；）
关键性质：
从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。
为什么说红黑树是“近似平衡”的？
平衡二叉查找树的初衷，是为了解决二叉查找树因为动态更新导致的性能退化问题。所以，“平衡”的意思可以等价为性能不退化。“近似平衡”就等价为性能不会退化的太严重。
红黑树的性能分析
二叉查找树很多操作的性能都跟树的高度成正比。一棵极其平衡的二叉树（满二叉树或完全二叉树）的高度大约是 log2n 。所以如果要证明红黑树是近似平衡的，只需分析红黑树的高度是否比较稳定地趋近 log2n 就好了。
将红色节点从红黑树中去掉，那单纯包含黑色节点的红黑树的高度是多少呢？
红色节点删除之后，有些节点就没有父节点了，它们会直接拿这些节点的祖父节点（父节点的父 节点）作为父节点。所以，之前的二叉树就变成了四叉树。
从任意节点到可达的叶子节点的每个路径包含相同数目的黑色节点。从四叉树中取出某些节点，放到叶节点位置，四叉树就变成了完全二叉树。所以，仅包含黑色节点的四叉树的高度，比包含相同节点个数的完
全二叉树的高度还要小。
完全二叉树的高度近似 log2n，这里的四叉“黑树”的高度要低于完全二叉树， 所以去掉红色节点的“黑树”的高度也不会超过 log2 n。
我们现在知道只包含黑色节点的“黑树”的高度，那现在把红色节点加回去，高度会变成多少呢？
在红黑树中，红色节点不能相邻，也就是说，有一个红色节点就要至少有一个黑色节点，将它跟其他红色节点隔开。红黑树中包含最多黑色节点的路径不会超过log2n，所以加入红色节点之后，最长路径不会超过 2log2 n，也就是说，红黑树的高度近似 2log2 n。
所以，红黑树的高度只比高度平衡的AVL 树的高度（log2 n）仅仅大了一倍，在性能上，下降得并不多。这样推导出来的结果不够精确，实际上红黑树的性能更好。
• AVL trees provide faster lookups than Red Black Trees because they are more strictly balanced. • Red Black Trees provide faster insertion and removal operations than AVL trees as fewer rotations are done due to relatively relaxed balancing. • AVL trees store balance factors or heights with each node, thus requires storage for an integer per node whereas Red Black Tree requires only 1 bit of information per node. • Red Black Trees are used in most of the language libraries like map, multimap, multisetin C++ whereas AVL trees are used in databases where faster retrievals are required.