[TOC]
概念
红黑树是自平衡的二叉查找树
性质
性质1：每个节点要么是红色，要么是黑色。
性质2：根节点永远是黑色的。
性质3：所有的叶子节点都是空节点（即null），并且是黑色的。
性质4：每个红色节点的两个子节点都是黑色。（从每个叶子到根的路径上不会有两个连续的红色节点。）
性质5：从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点。
操作
插入
红黑树的插入主要分两步：
首先和二叉查找树的插入一样，查找、插入
然后调整结构，保证满足红黑树状态
对结点进行重新着色
以及对树进行相关的旋转操作
一般情况下，红黑树中新插入的节点都是红色的。因为我们从性质5中知道，当前红黑树中从根节点到每个叶子节点的黑色节点数量是一样的，此时假如新的黑色节点的话，必然破坏规则，但加入红色节点却不一定，除非其父节点就是红色节点，因此加入红色节点，破坏规则的可能性小一些。
旋转
LL
LR（插入节点的父节点是左节点，插入节点是右节点）
RR
RL
应用场景
IO多路复用epoll的实现采用红黑树组织管理sockfd，以支持快速的增删改查.
ngnix中,用红黑树管理timer,因为红黑树是有序的,可以很快的得到距离当前最小的定时器.
java中TreeMap，jdk1.8的hashmap的实现.
与平衡树的区别
1.红黑树是为了解决平衡树在插入、删除等操作需要频繁调整的情况。红黑树放弃了追求完全平衡，追求大致平衡
2.平衡二叉树,每次插入新节点之后需要旋转的次数不能预知。
平衡树的概念
平衡二叉树必须是排序二叉树
左子树和右子树的深度之差的绝对值不超过1。