Zhuoli's Blog在HashMap那篇文章讲过，在Java8中，HashMap是通过数组 + 链表 + 红黑树组织的，当链表中元素个数大于8时，会将链表转化成红黑树。而且Java API中TreeMap也是通过红黑树实现的，所以讲解红黑树，对于我们更好的了解源码实现有着重要的意义。红黑树也是一种特殊的排序二叉树，所以本篇文章先来介绍一下排序二叉树这一数据结构的相关细节，然后再用一片文章介绍一下红黑树数据结构以及Java API中红黑树的实现。
1. 基本概念
1.1 树
树(Tree)是一种抽象数据类型或是实现这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它是由n(n>0)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：
- 每个节点有零个或多个子节点；
- 没有父节点的节点称为根节点；
- 每一个非根节点有且只有一个父节点；
- 除了根节点外，每个子节点可以分为多个不相交的子树
在树中，存在以下术语：
- 节点的度：一个节点含有的子树的个数称为该节点的度
- 树的度：一棵树中，最大的节点的度称为树的度
- 叶节点或终端节点：度为零的节点
- 非终端节点或分支节点：度不为零的节点
- 父亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点
- 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点
- 兄弟节点：具有相同父节点的节点互称为兄弟节点
- 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推
- 深度：对于任意节点n,n的深度为从根到n的唯一路径长，根的深度为0
- 高度：对于任意节点n,n的高度为从n到一片树叶的最长路径长，所有树叶的高度为0
- 堂兄弟节点：父节点在同一层的节点互为堂兄弟
- 节点的祖先：从根到该节点所经分支上的所有节点
- 子孙：以某节点为根的子树中任一节点都称为该节点的子孙
- 森林：由m（m>=0）棵互不相交的树的集合称为森林
1.2 二叉树
二叉树(Binary tree)是每个节点最多只有两个分支（即不存在分支度大于2的节点）的树结构。通常分支被称作“左子树”或“右子树”。二叉树的分支具有左右次序，不能随意颠倒。
1.3 排序二叉树
排序二叉树(sorted binary tree)，也称为二叉查找树、二叉搜索树、有序二叉树，是指一棵空树或者具有下列性质的二叉树：
- 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
- 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
- 任意节点的左、右子树也分别为二叉查找树；
- 没有键值相等的节点。
2. 基本算法
基于上述排序二叉树的特点，下面看一下排序二叉树的基础算法。
2.1 遍历
2.1.1 二叉树遍历
二叉树的遍历可分为深度优先遍历和广度优先遍历，深度优先遍历又可以细分为前序遍历、中序遍历和后序遍历。如果把左节点和右节点的位置固定不动，那么根节点放在左节点的左边，称为前序（pre-order）、根节点放在左节点和右节点的中间，称为中序（in-order）、根节点放在右节点的右边，称为后序（post-order）。对广度优先而言，遍历没有前序中序后序之分：给定一组已排序的子节点，其“广度优先”的遍历只有一种唯一的结果。
深度优先遍历
- 前序遍历(Pre-Order Traversal)
指先访问根，然后访问子树的遍历方式，如下图所示：
上图前序遍历结果为：F、B、A、D、C、E、F、G、I、H
- 中序遍历(In-Order Traversal)
指先访问左子树，然后访问根，最后访问右子树的遍历方式
上图中序遍历结果为：A、B、C、D、E、F、G、H、I
- 后序遍历(Post-Order Traversal)
指先访问子树，然后访问根的遍历方式
上图中序遍历结果为：A、C、E、D、B、H、I、G、F
广度优先遍历
和深度优先遍历不同，广度优先遍历会先访问离根节点最近的节点，二叉树的广度优先遍历又称按层次遍历。
上图广度优先遍历结果为：F、B、G、A、D、I、C、E、H
2.1.2 排序二叉树遍历
对于排序二叉树的遍历，我们一般指上面讲的中序遍历，通过遍历可以得到一个从小到大的序列。算法如下：
- 访问左子树
- 访问当前节点
- 访问右子树
比如，遍历访问下面的二叉树：
从根节点开始，但先访问根节点的左子树，一直到最左边的节点，所以第一个访问的是1，1没有右子树，返回上一层，访问3，然后访问3的右子树，4没有左子树，所以访问4，然后是4的右子树6，依次类推，访问顺序就是有序的：1、3、4、6、7、8、9。
2.2 查找
排序二叉树查找比较方便，根据排序二叉树左子树元素总是小于父节点，右子树元素总是大于父节点的特点，在二叉搜索树b中查找x的过程为：
- 若b是空树，则搜索失败，否则：
- 若x等于b的根节点的数据域之值，则查找成功；否则：
- 若x小于b的根节点的数据域之值，则搜索左子树；否则：
- 查找右子树。
这个步骤与在数组中进行二分查找或者说折半查找的思路是类似的，如果二叉树是比较平衡的，类似上图中左边的二叉树，则每次比较都能将比较范围缩小一半，效率很高。此外，在排序二叉树中，可以方便的查找最小最大值，最小值即为最左边的节点，从根节点一路查找左孩子即可，最大值即为最右边的节点，从根节点一路查找右孩子即可。
2.3 插入
在排序二叉树中，插入元素首先要找插入位置，即新节点的父节点，向一个二叉搜索树b中插入一个节点s的算法，过程为：
- 若b是空树，则将s所指节点作为根节点插入，否则：
- 若s->data等于b的根节点的数据域之值，则返回，否则：
- 若s->data小于b的根节点的数据域之值，则把s所指节点插入到左子树中，否则：
- 把s所指节点插入到右子树中。（新插入节点总是叶子节点）
依次插入7, 3, 4, 1, 9, 6, 8的过程，这个过程如下图所示：
2.4 删除
在二叉查找树删去一个结点，分三种情况讨论：
- 若*p结点为叶子结点，即PL（左子树）和PR（右子树）均为空树。由于删去叶子结点不破坏整棵树的结构，则只需修改其双亲结点的指针直接删除即可
- 若*p结点只有左子树PL或右子树PR，此时只要令PL或PR直接成为其双亲结点*f的左子树（当*p是左子树）或右子树（当*p是右子树）即可，作此修改也不破坏二叉查找树的特性。
- 若*p结点的左子树和右子树均不空。在删去*p之后，为保持其它元素之间的相对位置不变，可按中序遍历保持有序进行调整，可以有两种做法：其一是令*p的左子树为*f的左/右（依*p是*f的左子树还是右子树而定）子树，*s为*p左子树的最右下的结点，而*p的右子树为*s的右子树；其二是令*p的直接前驱（in-order predecessor）或直接后继（in-order successor）替代*p，然后再从二叉查找树中删去它的直接前驱（或直接后继）。
下面分别来看一下
如果节点为叶子节点，则很简单，可以直接删掉，修改父节点的对应孩子为空即可。
如果节点只有一个孩子节点，则替换待删节点为孩子节点，或者说，在孩子节点和父节点之间直接建立链接。比如说，在下图中，左边二叉树中删除节点4，就是让4的父节点3与4的孩子节点6直接建立链接。
如果节点有两个孩子，则首先找该节点的后继（根据之前介绍的后继算法，后继为右子树中最小的节点，这个后继一定没有左孩子），找到后继后，替换待删节点为后继的内容，然后再删除后继节点。后继节点没有左孩子，这就将两个孩子的情况转换为了叶子节点或只有一个孩子的情况。
比如说，在下图中，从左边二叉树中删除节点3，3有两个孩子，后继为4，首先替换3的内容为4，然后再删除节点4。
3. 平衡排序二叉树
从前面的描述中可以看出，排序二叉树的形状与插入和删除的顺序密切相关，极端情况下，排序二叉树可能退化为一个链表，比如说，如果插入顺序为：1 3 4 6 7 8 9，则排序二叉树形状为：
退化为链表后，排序二叉树的优点就都没有了，即使没有退化为链表，如果排序二叉树高度不平衡，效率也会变的很低。所以为了解决这种问题，平衡二叉排序树就出现了。平衡二叉排序树（Balanced Binary Tree）是一种结构平衡的二叉排序树，即叶节点高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。最早被发明的平衡二叉搜索树为AVL树（名字源于它的发明者G.M. Adelson-Velsky 和 E.M. Landis)，在他们的算法中，在插入和删除节点时，通过一次或多次旋转操作来重新平衡树。初次之外，常见的平衡排序二叉树还有：
在TreeMap的实现中，用的并不是AVL树，而是红黑树，与AVL树类似，红黑树也是一种平衡的排序二叉树，也是在插入和删除节点时通过旋转操作来平衡的，但它并不是高度平衡的，而是大致平衡的，所谓大致是指，它确保，对于任意一条从根到叶子节点的路径，没有任何一条路径的长度会比其他路径长过两倍。红黑树减弱了对平衡的要求，但降低了保持平衡需要的开销，在实际应用中，统计性能高于AVL树。对于红黑树的算法细节及Java中的实现，会在下篇文章中讲解。
4. 排序二叉树特点
- 排序二叉树保持了元素的顺序，而且是一种综合效率很高的数据结构，基本的保存、删除、查找的效率都为O(h)，h为树的高度，在树平衡的情况下，h为log2(N)，N为节点数
- 基本的排序二叉树不能保证树的平衡，可能退化为一个链表，平衡排序二叉树可以保证二叉树平衡，避免二叉树退化为链表这种情况的产生。Java API中TreeMap就是通过红黑树实现的。
参考链接