二叉搜索树在插入的时候存在问题，红黑树为了解决二叉搜索树多次插入新节点会导致不平衡，极端情况下会退化成链表，有可能使得查找的时间复杂度变为 O(n)。

平衡二叉树的严格定义是这样的：二叉树中任意一个节点的左右子树的高度相差不能大于 1。

发明平衡二叉查找树这类数据结构的初衷是，解决普通二叉查找树在频繁的插入、删除等动态更新的情况下，出现时间复杂度退化的问题。

红黑树是一种自平衡的二叉查找树。它具有除了二叉查找树不具备的特性：

• 节点由红黑色组成
• 根节点是黑色的
• 每个叶子节点都是黑色的空节点
• 每个红色节点的两个子节点都是黑色的（从每个叶子到根的所有路径不能有两个连续的红色节点）
• 从任意节点到它每个叶子节点的所有路径都包含相同数目的黑色节点

红黑树从根到叶子的最长路径不会超过最短路径的2倍。

调整的方法：变色和旋转，旋转又分为左旋转和右旋转。

左旋转

逆时针旋转红黑树的两个节点，使得父节点被自己的右孩子取代，而自己成为自己的左孩子。

右旋转

顺时针旋转红黑树的两个节点，使得父节点被自己的左孩子取代，而自己成为自己的右孩子。

参考

漫画：什么是红黑树？