专注于Java领域优质技术，欢迎关注

作者：JasonGaoH

之前在公司组内分享了红黑树的工作原理，今天把它整理下发出来，希望能对大家有所帮助，对自己也算是一个知识点的总结。

这篇文章算是我写博客以来画图最多的一篇文章了，没有之一，我希望尽可能多地用图片来形象地描述红黑树的各种操作的前后变换原理，帮助大家来理解红黑树的工作原理，下面，多图预警开始了。

在讲红黑树之前，我们首先来了解下下面几个概念：二叉树，排序二叉树以及平衡二叉树。

二叉树指的是每个节点最多只能有两个字数的有序树。通常左边的子树称为左子树 ，右边的子树称为右子树 。这里说的有序树强调的是二叉树的左子树和右子树的次序不能随意颠倒。

二叉树简单的示意图如下：

代码定义：

class Node {

T data;

Node left;

Node right;

}

所谓排序二叉树，顾名思义，排序二叉树是有顺序的，它是一种特殊结构的二叉树，我们可以对树中所有节点进行排序和检索。

性质

• 若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
• 若她的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
• 具有递归性，排序二叉树的左子树、右子树也是排序二叉树。

排序二叉树简单示意图：

排序二叉树退化成链表

排序二叉树的左子树上所有节点的值小于根节点的值，右子树上所有节点的值大于根节点的值，当我们插入一组元素正好是有序的时候，这时会让排序二叉树退化成链表。

正常情况下，排序二叉树是如下图这样的：