红黑树（英语：Red-black tree）是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型用途是实现关联数组（又称映射Map、字典Dictionary）。红黑树的结构复杂，但它的操作有着良好的最坏情况运行时间，并且在实践中高效：它可以在 $O(logn)$ 时间内完成查找、插入和删除，这里的 n 是树中元素的数目。

学习红黑树，你需要具备的知识点：

• 二叉查找树（BST）

• 平衡二叉树（AVL）

红黑树系列文章目录

红黑树：开篇（本文）

红黑树：插入操作的分析

红黑树的定义

红黑树有以下定义：

• 性质1：每个结点要么是黑色，要么是红色

• 性质2：根结点是黑色

• 性质3：每个叶子结点（Nil）是黑色

• 性质4：每个红色结点的两个子结点一定都是黑色

• 性质5：任意一结点到每个子结点的路径都包含数量相同的黑结点

约定

在进入正文之前，需要对后面用到的一些词汇进行约定，保证概念不混淆。

红黑树作为一种自平衡的二叉查找树，需要一些手段来做到自平衡：变色、左旋和右旋：

• 变色：结点颜色由红变黑或由黑变红

• 左旋：以当前结点作为支点（旋转结点），其右子结点作为旋转结点的父结点，右子结点的左结点变为旋转结点的右子结点（见下图）
  

• 右旋：以当前结点作为支点（旋转结点），其左子结点作为旋转结点的父结点，左子结点的右结点变为旋转结点的左子结点（见下图）
  

红黑树中，空结点也被识别成一个结点，并作为叶子结点，颜色涂为黑色。但是普通编程时，我们把没有子树的结点称为叶子结点。为了避免混淆，在本文中，没有子树的结点称为叶子结点（颜色不定），叶子结点的两个 Nil 子树，称为空结点（黑色）。

红黑树作为一颗二叉查找树，其查找操作和其他树没有太大区别，而插入和删除则依靠旋转和变色，在后面的文章，我们将分别讨论插入结点和删除结点，根据每种情况分别分析。

下一篇：红黑树：插入操作的分析

参考文章

Java 全栈知识体系 树 - 红黑树(R-B Tree)(by pdai)

30张图带你彻底理解红黑树(by 安卓大叔)

红黑树(一)之 原理和算法详细介绍(by skywang12345)