上一篇：浅谈二叉树节点删除之道 | 带你学《Java语言高级特性》之四十

在上一节的学习中不难发现，二叉树节点增减后，其结构可能会发生左右子树不平衡的问题，导致其查找效率大打折扣。本节将为读者介绍红黑树的概念及其对于二叉树来说增加的内容与节点规则。

【本节目标】
通过阅读本节内容，你将进一步认识二叉树，对其简单的节点增减工作带来的“后遗症”有一个明确的认识，了解到红黑树的基本概念与其节点结构的特点，初步理解其能够实现二叉树的调整平衡的方法。

红黑树原理分析

通过整个二叉树的实现相信已经可以清楚二叉树的主要特点：数据查询的时候可以提供更好的查询性能，但是这种原始的二叉树结构是有明显缺陷的，例如，当二叉树结构改变的时候（增加或删除）就有可能出现不平衡的问题。

传统二叉树问题

之前所谓的解决二叉树性能问题的方式最终全部都变为了null，也就是说如果要想要达到最良好效果的二叉树，那么它首先是一个平衡二叉树，同时所有节点的层次深度都应该相同。

均衡二叉树

如果所有的数据按照以上的结构进行保存，那么二叉树的检索操作执行效率一定是最高的，可是树就需要忍受住频繁的增加或者是删除操作，所以针对于二叉树有了进一步的要求。

红黑树本质上是一种二叉查找树，但它在二叉查找树的基础上额外添加了一个标记（颜色），同时具有一定的规则。这些规则使红黑树保证了一种平衡，插入、删除、查找的最坏时间复杂度都为“O(logn)”。
红黑树是在1972年由Rudolf Bayer发明的，当时被称为平衡二叉B树（symmetric binary B-trees）。后来，在1978年被Leo J.Guibas和Robert Sedgewick修改为如今的“红黑树”。

红黑树的本质就是在节点上追加了一个表示颜色的操作信息而已。

enum Color{
    RED,BLACK;
}
class BinaryTree<T> {
     private class Node {
          private T data;
          private Node parent;//父节点
          private Node left;//左子树
          private Node right;//右子树
          private Color color;//节点颜色
     }
}

class BinaryTree<T> {
     private class Node {
          private T data;
          private Node parent;//父节点
          private Node left;//左子树
          private Node right;//右子树
          private boolean color;//节点颜色
     }
}

对于Node节点中的颜色标记可以使用true或false来实现，不一定非要使用枚举类。
一个标准的红黑树的结构如下所示：

红黑树基本结构

红黑树特点（规则）
1、每个节点或者是黑色，或者是红色；
2、根节点必须是黑色；
3、每个叶子节点是黑色；
  |- Java实现的红黑树将使用null来代表空节点，因此遍历红黑树时将看不到黑色的叶子节点，反而看到每个叶子节点都是红色的；
4、如果一个节点时红色的，则它的子节点必须是黑色的；
  |- 从每个根到节点的路径上不会有两个连续的红色节点，但黑色节点是可以连续的。若给定黑色节点的个数N，最短路径情况是连续的N个黑色，树的高度为N-1；最长路径的情况为节点红黑相间，树的高度为2(N-1)；
5、从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点数量；
  |- 成为红黑树最主要的条件，后序的插入、删除操作都是为了遵守这个规定；

红色节点之后绝对不可能是红色节点，但是没有说黑色节点之后不允许是黑色节点，允许黑-黑连接。

主要是利用红色节点与黑色节点实现均衡控制。简单点理解红黑树的结构就是为了可以进行左旋和右旋控制以保证树的平衡性。

红黑存在的意义

但是对于平衡性，还需要考虑数据增加的平衡以及数据删除的平衡，增加和删除都是需要对树进行平衡修复。

想学习更多的Java的课程吗？从小白到大神，从入门到精通，更多精彩不容错过！免费为您提供更多的学习资源。
本内容视频来源于阿里云大学

下一篇：使用红黑树实现节点增减的平衡修复 | 带你学《Java语言高级特性》之四十二
更多Java面向对象编程文章查看此处