为什么产生红黑树
- 动态规模比平衡二叉树（AVL）小；（动态规模指：对二叉树进行查找后进行修改或删除操作等）；
- 因为AVL对平衡度要求严格，导致动态查找规模很大，而红黑树在动态规模小的情况下也可以达到相对平衡；
- 静态查找（只查找不操作）相对比ACL要慢；
- 一种特殊的二叉排序树；
特性
- 每个结点要么红色要么黑色；
- 根结点是黑色；
- 每个叶子结点都是
黑色； - 红色结点其孩子是黑色；
4.1 不会出现连续红色结点；
4.2 红色结点的父与子都是黑色； - 从任意一个结点到叶子结点的简单路径中黑色结点数量相同（黑高度）；
- 最长简单路径 / 最短简单路径 < 2;
<img src="https://raw.githubusercontent.com/liangxifeng833/my_program/master/images/datastruct/red_black.png" width="558" />
