基本定义
- 叶子节点不存储任何数据
- 除了叶子节点之外，其他节点下面一定会有两个子节点
- 红黑树也是二叉搜索树
- 红黑树在插入、删除节点的过程中是自平衡的
红黑平衡规则
- 每一条路径上的黑节点的数量一定是一致的
- 没有两个红色节点是连接在一起的
- 根节点一定是黑色
红黑树插入
基本规则
- 当树是空树时，插入根节点一定是黑色（规则 7）
- 接下来每次插入红节点（为了满足规则：每一条路径上的黑节点的数量一定是一致的，只有插入红节点才能不打破这种平衡）
要插入的节点父节点为黑
直接插入
要插入的节点是 80
要插入的节点是 80
要插入的节点父亲、叔叔节点为红
父亲、叔叔的颜色和爷爷的颜色调换**（注意根节点一定是黑色）**
要插入的节点是 100，变换的时候一定是父亲、叔叔都为红，才能变换，否则会打破红黑平衡
要插入的节点是 100，变换的时候一定是父亲、叔叔都为红，才能变换，否则会打破红黑平衡