红黑树特性

• 每个节点或者是黑色，或者是红色。
• 根节点是黑色。
• 每个叶子节点（NIL）是黑色。 （注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点）
• 如果一个节点是红色的，则它的子节点必须是黑色的。
• 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点，并且确保没有一条路径会比其他路径长出俩倍。

因而，红黑树是相对是接近平衡的二叉树。

红黑树相关定理

一棵含有n个节点的红黑树的高度至多为2log(n+1)

红黑树的添加操作

• 第一步: 将红黑树当作一颗二叉查找树，将节点插入。
• 第二步：将插入的节点着色为"红色"。
• 第三步: 通过一系列的旋转或着色等操作，使之重新成为一颗红黑树。