14 |红黑树

一、什么是“平衡二叉查找树”

平衡二叉树的严格定义是这样的：二叉树中任意一个节点的左右子树的高度相差不能大于 1。完全二叉树、满二叉树都是平衡二叉树，但是非完全二叉树也有可能是平衡二叉树。
平衡二叉查找树中“平衡”的意思，其实就是让整棵树左右看起来比较“对称”、比较“平衡”，不要出现左子树很高、右子树很矮的情况。这样就能让整棵树的高度相对来说低一些，相应的插入、删除、查找等操作的效率高一些。

二、红黑树

红黑树，Red-Black Tree 「RBT」是一个自平衡(不是绝对的平衡)的二叉查找树(BST)。

一.红黑树的定义

合格的红黑树需要满足以下几个要求

1、 根节点是黑色的（树顶是黑色的）；

2、 每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存储数据（树根是黑色的，所有结点的叶子节点都是黑色的，但是黑色的并不都是叶子节点，叶子节点不存储数据）；
3、 任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的；（红色节点的父亲一定不能是红色节点，但是黑色节点的父亲可以是黑色节点）；
4、 每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点（这个其实可以用一张图来表示，一棵红黑树，在去掉所有红节点之后剩下的黑节点是等高的）；

要求2图解

要求4图解

二.红黑树的平衡操作

1、旋转操作（使树达到平衡的关键操作）