数据结构之二叉树（四）红黑树
1.0 简介
红黑树（Red Black Tree）
是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。
2.0 前提
要想学会红黑树 一定要有这即个树的基础 按顺序来
- 二叉排序树 也及时AVL树 也叫二叉查找树
- 2-3树
好了 我们知道了2-3树 也就知道了红黑树
红黑树就是把2-3树中的3节点 也就是含有两个关键码的结点转换红链接
什么是红链接呢？如图所示
这样就构成了 红黑树 红黑树可以看成是对2-3树种3节点的优化
至于操作 就是把对2-3树的操作之后吧3节点换为 红链接
有个完整的红黑树的构造如图
性质：
性质1. 节点是红色或黑色。
性质2. 根节点是黑色。
性质3 每个叶节点（NIL节点，空节点）是黑色的。
性质4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
性质5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。