树，是计算机中最复杂的一种数据结构，它形式多变，有各种各样复杂的树被人创造并在计算机的各个地方使用，如红黑树、B+树等。
一、引入
二叉树：树是计算机中最为复杂的一种数据结构，它形式多变且有多个变种，其中最为常见和理解的是二叉树，其有一下几个性质：
- 二叉树的第i层上至多有2i-1（i≥1）个节点
- 深度为h的二叉树中至多含有2h-1个节点
- 若在任意一棵二叉树中，有n0个叶子节点，有n2个度为2的节点，则必有n0=n2+1
- 具有n个节点的完全二叉树深为log2x+1(其中x表示不大于n的最大整数)
- 若对一棵有n个节点的完全二叉树进行顺序编号（1≤i≤n），那么，对于编号为i（i≥1）的节点：
二叉排序树：为了快速的插入、删除、查找而出现了二叉查找树，也称为二叉排序树，其要满足以下几个条件：
- 若左子树不空，则左子树上所有结点的值均小于它的根结点的值
- 若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值
- 左、右子树也分别为二叉排序树
- 没有键值相等的结点
极端情况下二叉查找树会退化成链表从而影响查找的效率
AVL数：为了解决二叉排序树极端情况下退化成链表的问题而出现了平衡二叉树，也称为AVL树，其需要满足以下几个条件：
- 本身首先是一棵二叉搜索树
- 每个结点的左右子树的高度之差的绝对值最多为1
AVL树严格遵守左右子树高度差不能超过1，查找效率比较高，平衡速度慢，即插入删除效率比较低。
红黑树：终于聊到本文的主题——红黑树，
Red-Black Tree，简称RBT，是一个自平衡(不是绝对的平衡)的二叉查找树，其要满足一下几个条件：- 节点是红色或黑色
- 根节点是黑色
- 所有叶子都是黑色
- 每个红色节点的两个子节点都是黑色，或者换一种说法，不能有两个相邻的红色节点
- 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点
后期出现的B+树是为文件存储而生的
当数据量少时可在内存中实现排序，用红黑树实现效率高效
当数据量大时则须将数据保存在外存上，为了减少IO次数多使用B+数实现
二、过程分析
为了满足以上红黑树的各个条件，构造一颗红黑树主要进行以下两种操作：recolor(重新标记黑色或红色)和rebalance(重新维护平衡，主要通过旋转进行)。
recolor
TODO
rebalance
TODO
三、应用场景
- 操作系统的进程调度
- IO多路复用epoll的实现采用红黑树组织管理sockfd
- Ngnix中用红黑树管理timer
- Java中TreeMap，JDK1.8以后的HashMap的实现
- 在JDK1.7以前HashMap是以数组加链表的形式实现的
- C++中STL的map和set的实现