红黑树是一种常见的自平衡二叉查找树，常用于关联数组、字典，在各种语言的底层实现中被广泛应用，Java 的 TreeMap 和 TreeSet 就是基于红黑树实现的。
5.2.1、红黑树的定义和性质
红黑树::红黑树是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。它是在1972年由鲁道夫·贝尔发明的，称之为"对称二叉B树"，它现在的名字来自Leo J. Guibas 和 Robert Sedgewick 于1978年写的一篇论文中。
红黑树是具有如下性质的二叉查找树：
（1）每个节点是黑色或者红色
（2）根节点是黑色。
（3）每个叶子节点是黑色。
（4）从任意一个节点到叶子节点，所经过的黑色节点数目必须相等
（5） 空节点被认为是黑色的
5.2.2、红黑树的平衡调整方法
作为一种平衡二叉树，红黑树的自平衡调整方法和AVL类似。关键也是在旋转。旋转同样也是左旋和右旋。找到了两个左旋和右旋的动图。
和AVL树不同的是，红黑树还有颜色性质，所以还会进行变色来平衡红黑树。
5.2.2、红黑树的插入
红黑树的插入和AVL树类似，同样是插入节点后需要对二叉树的平衡性进行修复。
新插入的节点是红色的，插入修复操作如果遇到父节点的颜色为黑则修复操作结束。也就是说，只有在父节点为红色节点的时候是需要插入修复操作的。
插入修复操作分为以下的三种情况，而且新插入的节点的父节点都是红色的：
叔叔节点也为红色。
叔叔节点为空，且祖父节点、父节点和新节点处于一条斜线上。
叔叔节点为空，且祖父节点、父节点和新节点不处于一条斜线上。