疯狂java笔记之树和二叉树

比眉伴天荒 2023-06-23 11:59 5阅读 0赞

# 树的概述 #

树是一种非常常用的数据结构，树与前面介绍的线性表，栈，队列等线性结构不同，树是一种非线性结构

### 1.树的定义和基本术语 ###

计算机世界里的树，是从自然界中实际的树抽象而来的，它指的是N个有父子关系的节点的有限集合。对于这个有限的节点集合而言，它满足如下条件：

*  当N=0时，改节点集合为空，这课树也被称为空树
 *  在任意的非空树中，有且仅有一个根(root)节点
 *  当N>1时，除根节点以外的其余节点可分为M个互为相交的有限集合T1,T2,...,Tm，其中的每个集合本身又是一棵树，并称其为根的子树（subtree）。

从上面定义可以发现树的递归特性：一棵树由根和若干棵子树组成，而每棵子树又由若干棵更小的子树组成。

树中任一节点可以有0或多个子节点，但只能有一个父节点。根节点是一个特例，根节点没有父节点，叶子节点没有子节点。树中每个节点既可以是其上一级节点的子节点，也可以是下一级节点的父节点，因此同一个节点既可以是父节点，也可以是子节点(类似于一个人—————他既是他儿子的父亲，又是他父亲的儿子)。

很显然，父子关系是一种非线性关系，所以树结构是非线性结构。

如果按节点是否包含子节点来分，节点可以分成以下两种:

*  普通节点：包含子节点的节点
 *  叶子节点：没有子节点的节点，因此叶子节点不可作为父节点

如果按节点是否具有唯一的父节点来分，节点有可分为如下两种：

*  根节点：没有父节点的节点，根节点不可作为子节点
 *  普通节点：具有唯一父节点的节点

一棵树只能有一个根节点，如果一棵树有了多个根节点，那么它已经不再是一棵树了，而是多棵树的集合，有时也被称为森林。示意图如下：

![format_png][]

与树有关的术语有如下一些：

*  节点：树的最基本组成单元，通常包括一个数据元素及若干指针用于指向其他节点。
 *  节点的度：节点拥有的子树的个数被称为节点的度（degree）
 *  树的度：树中所有节点的度的最大值就是该树的度
 *  叶子节点：度为0的节点被称为叶子节点或终端节点
 *  分支节点：度不为0的节点被称为分支节点或非终端节点
 *  子节点,父节点，兄弟节点：节点的子树的根被称为该节点的子节点，而该节点称为子节点的父节点(parent).具有相同父节点的子节点之间互称为兄弟节点。
 *  节点的层次(level):节点的层次从根开始算起，根的层次值为1，其余节点的层次值为父节点层次值加l。
 *  树的深度(depth):树中节点的最大层次值称为树的深度或高度。
 *  有序树与无序树:如果将树中节点的各棵子树看成从左到右是有序的(即不能互换),则称该树为有序树,否则称为无序树。
 *  祖先节点(ancestor)：从根到该节点所经分支上的所有节点
 *  后代节点(descendant):以某节点为根的子树中任一节点都称为该节点的后代节点。
 *  森林(forest):森林是；两颗或两颗以上互不相交的树的集合，删去一棵树的根，就得到一个森林。

### 树的基本操作 ###

如果需要实现一棵树，程序不仅要以合适的方式保存该树的所有节点，还要记录节点与节点之间的父子关系。接下来，还应该为树实现如下基本操作。

*  初始化:通常是一个构造器，用于创建一棵空树，或者以指定节点为根来创建树。
 *  为指定节点添加子节点
 *  判断树是否为空
 *  返回根节点
 *  返回指定节点（非根节点）的父节点
 *  返回指定节点（非叶子节点）的所有子节点
 *  返回指定节点（非叶子节点）的第i个子节点
 *  返回该树的深度
 *  返回指定节点的位置  
    为了实现树这种数据结构，程序必须能记录节点与节点之间的父子关系，为此有一下两种选择：
 *  父节点表示法:每个子节点都记录它的父节点。
 *  子节点链表示法:每个非叶子节点通过一个链表来记录它所有的子节点。

### 父节点表示法 ###

通过前面的介绍可以发现，树中除根节点之外的每个节点都有一个父节点。为了记录树中节点与节点之间的父子关系，可以为每个节点增加一个parent域，用以记录该节点的父节点。用如下图和如下表来表示

![format_png 1][]

<table> 
 <thead> 
  <tr> 
   <th>数组索引</th> 
   <th>data</th> 
   <th>parent</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>0</td> 
   <td>A</td> 
   <td>-1</td> 
  </tr> 
  <tr> 
   <td>1</td> 
   <td>B</td> 
   <td>0</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>C</td> 
   <td>0</td> 
  </tr> 
  <tr> 
   <td>3</td> 
   <td>D</td> 
   <td>0</td> 
  </tr> 
  <tr> 
   <td>4</td> 
   <td>E</td> 
   <td>1</td> 
  </tr> 
  <tr> 
   <td>5</td> 
   <td>F</td> 
   <td>3</td> 
  </tr> 
  <tr> 
   <td>6</td> 
   <td>G</td> 
   <td>3</td> 
  </tr> 
  <tr> 
   <td>7</td> 
   <td>H</td> 
   <td>4</td> 
  </tr> 
  <tr> 
   <td>8</td> 
   <td>I</td> 
   <td>4</td> 
  </tr> 
  <tr> 
   <td>9</td> 
   <td>J</td> 
   <td>4</td> 
  </tr> 
  <tr> 
   <td>10</td> 
   <td>K</td> 
   <td>6</td> 
  </tr> 
  <tr> 
   <td>...</td> 
   <td>...</td> 
   <td>...</td> 
  </tr> 
 </tbody> 
</table>

由此可见，只要用一个节点数组来保存树里的每个节点，并让每个节点记录其父节点在数组中的索引即可。

### 子节点链表表示法 ###

父节点表示法的思想是让每个节点“记住”它的父节点的索引，父节点表示法是从子节点着手的;反过来，还有另外一种方式:让父节点“记住”它的所有子节点口在这种方式下，由于每个父节点需要记住多个子节点，因此必须采用“子节点链”表示法。示意图如下：

![format_png 2][]

tree\_linked.PNG

# 二叉树 #

### 二叉树的定义和基本概念 ###

二叉树指的是每个节点最多只能有两个子树的有序树。通常左边的子树被称作“左子树”(left subtree)，右边的子树被称为“右子树”(right subtree).由此可见，二叉树依然是树，它是一种特殊的树。  
二叉树的每个节点最多只有来两颗树(不存在度大于2的节点)，二叉树的子树有左，右之分，次序不能颠倒。  
树和二叉树的两个重要区别如下：

*  树中节点的最大度数没有限制，而二叉树节点的最大度数为2，也就是说，二叉树是节点的最大度数为2的树。
 *  无序树的节点无左右之分，而二叉树的节点有左，右之分，也就是说，二叉树是有序树。

一棵深度为k的二叉树，如果它包含了

2^k-1

个节点，就把这棵二叉树称为满二叉树。满二叉树的特点是。每一层上的节点数都是最大节点数，即各层节点数分别为1,2,4,8, 16,...,满二叉树下图所示：

![format_png 3][]

two\_tree.PNG

一颗有n个节点的二叉树，按满二叉树的编号方式对它进行编号，若树中所有节点和满二叉树1~n编号完全一致，则称该树为完全二叉树。也就是说，如果一颗二叉树除最后一层外，其余层的所有节点都是满的，并且最后一层或者是满的，或者仅在右边缺少若干连续的节点，则此二叉树就是完全二叉树。

综上所述，二叉树大致有如下几个性质：

*  二叉树第i层上的节点数据至多为2的i-1次方
 *  深度为k的二叉树至多有2的k次方-1个节点.满二叉树的每层节点的数量依次为1, 2, 4,8,…,因此深度为k的满二叉树包含的节点数为公比为2的等比数列的前k项总和，  
    即2的k次方一1。
 *  在任何一棵二叉树中，如果其叶子节点的数量为n0,度为2的子节点数量为n2，则  
    n0=n2 + 1。这是因为:如果为任意叶子节点增加一个子节点，则原有叶子节点变成非叶子节点，新增节点变成叶子节点，上述等式不变;如果为任意叶子节点增加两个子节点，则原有叶子节点变成度为2的非叶子lto点，新增的两个节点变成叶子节点，上述等式依然不变。
 *  具有n个节点的完全二叉树的深度为log2(n+1)
 *

对于一颗具有n个节点的完全二叉树的节点按层自左向右编号，则对任一编号为i(n>=i>=1)的节点有下列性质。

*  当i==1时，节点i是二叉树的根；若i>1，则节点的父节点是i/2
 *  若2i<n,则节点i有左孩子，左孩子的编号是2i;否则，节点无左孩子，并且是叶子节点
 *  若2i+1<=n,则节点i有右孩子，右孩子的编号是2i+1;否则，节点无右孩子。
 *  1~n/2范围的节点都是有孩子节点的非叶子节点，其余的节点全部都是叶子节点。编号为n/2的节点可能只有左子节点，也可能即有左子节点，又有右子节点。

### 二叉树的基本操作 ###

二叉树记录其节点之间的父子关系更加简单，因为二叉树中的每个节点最多只能保存两个子节点。接下来，程序也需要为二叉树实现如下基本操作。

*  初始化：通常是一个构造器，用于创建一颗空树，或者以指定节点为根来创建二叉树。
 *  为指定节点添加子节点
 *  判断二叉树是否为空
 *  返回根节点
 *  返回指定节点(非根节点)的父节点
 *  返回指定节点(非叶子节点)的左子节点
 *  返回指定节点(非叶子节点)的右子节点
 *  返回该二叉树的深度
 *  返回指定节点的位置

要实现二叉树这种数据结构，有以下三种选择。

*  顺序存储:采用数组来记录二叉树的所有节点。
 *  二叉链表存储:每个节点保留一个left,right域，分别指向其左、右子节点。
 *  三叉链表存储:每个节点保留一个left, right,parent域，分别指向其左、右子节点和父节点。

### 二叉树的顺序存储 ###

顺序存储指的是充分利用满二叉树的特性:每层的节点数分别为1, 2, 4, 8,…,2的(i-1)2的i次方。一棵  
深度为i的二叉树最多只能包含2的i次方一1个节点，因此只要定义一个长度为2的i次方一1的数组即可存储这棵二叉树。

对于普通二叉树(不是满二叉树)，那些空出来的节点对应的数组元素留空就可以了。由此可见，二叉树采用顺序存储会造成一定的空间浪费。对于下图1所示的二叉树(完全二叉树)，采用下图2所示的数组来保存即可。

![format_png 4][]

图1.PNG

![format_png 5][]

图2.PNG

对于左图所示的二叉树，需使用右图所示的数组来保存。

![format_png 6][]

compare\_tree.PNG

当使用数组来存储二又树的所有节点时可能会产生一定的空间浪费，如果该二叉树是完全二叉树，就不会有任何空间浪费了;但如果该二叉树的所有节点都只有右子节点，那么就会产生相当大的空间浪费.

### 二叉树的二叉链表存储 ###

二叉链表存储的思想是让每个节点都能“记住”它的左，右两个子节点。为每个节点增加left,right两个指针，分别引用改节点的左，右两个子节点，因此二叉链表存储的每个节点有如下图结构：

![format_png 7][]

two\_fork\_tree.PNG

二叉链表存储的二叉树的节点大致有如下定义：

class Node{
        Object data;
        Node left;
        Node right;
    }

对于这种二叉链表存储的二叉树，如果程序需要，为指定节点添加子节点也非常容易，让父节点的left或right引用指向新节点即可。

### 二叉树的三叉链表存储 ###

三叉链表存储的思想是让每个节点不仅“记住”它的左右两个子节点，还要“记住”它的父节点，因此需要为每个节点增加left,right和parent三个指针，分别引用该节点的左，右两个子节点和父节点。因此，三叉链表存储的每个节点有如下图的结构：

![format_png 8][]

three\_tree.PNG

因此三叉链表存储的二叉树的节点大致如下：

class Node{
        Object data;
        Node left;
        Node right;
        Node parent;
    }

对于这种三叉链表存储的二叉树，如果程序需要，为指定节点添加子节点也非常容易，除了要维护父节点的left,right引用之外，还要维护新增节点的parent引用。

# 遍历二叉树 #

遍历二叉树指的是按某种规律依次访问二叉树的每个节点，对二叉树的遍历过程就是讲非线性结构的二叉树的节点排列成线性序列的过程。

如果采用顺序结构来保存二叉树，程序遍历二叉树非常容易，无须进行任何思考，直接遍历底层数组即可。如果采用链表来保存二叉树的节点，则有以下两种遍历方式。

*  深度优先遍历：这种遍历算法将先访问到树中最深层次的节点
 *  广度优先遍历：这种遍历算法将逐层访问每层的节点，先访问根（第一层）节点，然后访问第二层的节点.....一次类推。因此，广度优先遍历方法又被称为按层遍历。
 *  先（前）序遍历二叉树
 *  中序遍历二叉树
 *  后序遍历二叉树

如果L,D,W表示左子树、根、右子树，习惯上总是必须先遍历左子树，后遍历右子树，根据遍历根节点的顺序不同，上面三种算法可表示如下。

*  DLR:先序遍历
 *  LDR:中序遍历
 *  LRD:后序遍历

深度遍历的先序遥历、中序遍历、后序遍历这三种遍历方式的名称都是针对根节点(D)而言的。先处理根节点(D)时就称为先序遍历。其次处理根节点(D)时就称为中序遍历;最后处理根节点(D)时就称为后序遍历。

### 先序遍历 ###

先序遍历指先处理根节点，其处理顺序如下：  
(1) 访问根节点  
(2) 递归遍历左子树  
(3) 递归遍历右子树

### 中序遍历 ###

中序遍历指其次处理根节点.其处理顺序如下。  
(1) 递归遍历左子树  
(2) 访问根节点  
(3) 递归遍历右子树

### 后序遍历 ###

后序遍历指最后处理根节点，其处理顺序如下。  
(1) 递归遍历左子树  
(2) 递归遍历右子树  
(3) 访问根节点

### 广度优先(按层)遍历 ###

广度优先遍历又称为按层遍历，整个遍历算法是先遍历几叉树的第一层(根节点)，再遍历根节点的两个子’节点(第二层)……依此类推，逐层遍历二叉树的所有节点。

为了实现广度优先遍历，可以借助于具有FIFO特征的队列来实现。如下所示。

*  建一个队列(先进先出)，把树的根节点压入队列。
 *  从队列中弹出一个节点(第一个弹出的就是根节点)，然后把改节点的左，右节点压入队列，如果没有子节点，则说明已经达到叶子节点了。
 *  用循环重复执行2步，知道队列为空。当队列为空时，说明所有的叶子节点(深度最深的层)都已经经过了队列，也就完成了遍历。

# 转换方法 #

由于二叉树是一种更“确定”(它的每个节点最多只有两个子节点)的数据结构，因此不管是存储、增加、删除节点，还是遍历节点，程序都可以更简单、方便地实现口反之，由于树的每个节点具有个数不确定的节点，因此程序实现起来更复杂。

为了充分利用二义树的简单易用性，可以将普通树转换为二叉树，以二叉树的形式来保存柞通树，当程序需要树时，再将悦义树转换为普通树。

森林其实更简单，如果将一棵伶通树的根节点去掉，这棵树就变成了森林。或者可以转换一下思维，森林其实就是有多个根节点的树。

### 森林，树和二叉树的转换 ###

有序树，森林和二叉树之间有一一映射的关系，可以进行互相转换。

多叉树向二叉树的方法如下：

*  (1)加虚线：同一个父节点的相邻兄弟节点之间加虚线
 *  (2)抹实线：每个节点只保留它与最左子节点的连线，与其他字节点的连线都被抹掉。
 *  (3)虚改实:虚线改为实线

如图就是多叉图向二叉树转换的结果

![format_png 9][]

forest\_tree.PNG

图中的虚线就是新增的“父子”关系。这个转换结果来看，多叉树1转换为二叉树的方法的关键思想就是：所有子节点只保留子节点，其他子节点转为左子节点的右子节点链。

按照这个转换思路，森林也可转换为二叉树————只要把森林当成一颗根节点被删除的多叉树即可。下图示范了将森林转换为二叉树的结果。

![format_png 10][]

forest\_to\_tree.PNG

反过来，二叉树也可恢复出对应的多叉树，森林，恢复方法如下：

\-(1)加虚线：若某节点I是父节点的左子节点，则为该节点I的右孩子链的所有节点分别于节点I的父节点添加连线

*  (2)抹线：把有虚线的节点于原父节点的连线抹去
 *  (3)整理：虚改实并按层排列

把二叉树转换为多叉树

![format_png 11][]

two\_tree\_more\_tree.PNG

如果二叉树的根节点有右子节点————右子节点就代表根节点的兄弟节点，这种情况会转换得到森林。

把二叉树转换为森林

![format_png 12][]

tree\_to\_forest.PNG

### 树的链表存储 ###

根据上面介绍的理论，二义树可以和多叉树之间进行自由转换，因此可以得到普通树的另外一种保存方式:以二义树的形式保存多叉树，实际需要的时候再将二叉树转换为普通树。  
至于到底以哪种方式来保存二叉树，完全是自由的。通常会选择使用三叉链表存储方式来保存二叉树，这样得到的二叉树操作起来更方便，进行二叉树和多叉树之间转换时也更方便。

# 哈夫曼树 #

哈夫曼树又被称为最优二叉树，是一种带权路径最短的二叉树。哈夫曼树是二叉树的一种应用，在信息检索中很常用.

### 哈夫曼树的定义和基本概念 ###

在介绍哈夫曼树之前先来介绍一些相关的概念。

*  节点之间的路径长度：从一个节点到另一个节点之间的分支数量称为两个节点之间的路径长度
 *  树的路径长度：从根节点到树中的每一个节点的路径长度之和。

对于下图所示的而二叉树，该树的路径长度为17.即0+1+2+2+3+4+5==17.

![format_png 13][]

hafuman.PNG

*  节点的带权路径长度:从该节点到根节点之间的路径长度与节点的权的乘积
 *  树的带权路径长度：树中所有叶子节点的带权路径长度之和。带权路径如图：

![format_png 14][]

daiquan.PNG

对于哈夫曼树，有一个很重要的定理:对于具有对n个叶子节点的哈夫曼树，一共需要2乘以n-1个节点。因为对于二叉树来说，有三种类型节点，即度数为2的节点、度数为1的节点和度数为0的叶子节点，而哈夫曼树的非叶子节点都是由两个节点合并产生的，所以不会出现度  
数为1的节点。而生成的非叶子节点的个数为叶子节点个数-1因此n个叶子节点的哈夫曼树，一共需要Z乘以n-1个节点。

### 创建哈夫曼树 ###

创建哈夫曼树，可以按如下步骤进行：

*  根据给定的。个权值\{wl,w2,...,wn\}构造n棵二叉树的集合F=\{T1,T2,...,Tn\} \}，F集合中每棵二叉树都只有一个根节点。
 *  选取F集合中两棵根节点的权值最小的树作为左、右子树以构造一棵新的二叉树，且将新的二叉树的根节点的权值设为左、右子树上根节点的权值之和。
 *  将新的二叉树加入到F集合中，并删除第2步中被选中的两棵树。
 *  重复第2和3步，直到F集合中只剩下一棵树，这棵树就是哈夫曼树。

下图显示了创建哈夫曼树的过程。

![format_png 15][]

hafuman\_tree.PNG

### 哈夫曼编码 ###

根据哈夫曼树可以解决报文编码问题。假设需要对一个字符串如“a6cdabcaba”进行编码，将它转换为唯一的二进制码，但要求转换出来的二进制码的长度最小。

假设每个字符在字符串中出现的频率为W\}其编码长度为L，编码字符有n个，则编码后二进制码的总长度为W1L1+W2L2+W3L3+...+WnLn，这正好符合哈夫曼树的处理原则。因此可采用哈夫曼树的原理构造二进制编码，并使电文总长最短。

对于“abcdabcaba”字符串，总共只有a,b,c,d,这四个字符，它们出现的次数是4,3,2,1次\_\_这相当于它们的权值。于是，将a,b,c,d四个字符以出现的次数为权值构造哈夫曼树，得到如下图结构：

![format_png 16][]

hanfuman1.PNG

从哈夫曼树根节点开始，对左子树分配代码“0”，对右子树分配代码“1”，一直到达叶子节点。然后.将从树根沿每条路径到达叶子节点的代码排列起来，便得到了每个叶子节点的哈夫曼编码。下图显示了对a, b, c, d四个字符编码得到的哈夫曼编码。

![format_png 17][]

hanfuma2.PNG

# 排序二叉树 #

排序二叉树是一种特殊结构的二叉树，通过它可以非常方便地对树中的所有节点进行排序和检索

排序二叉树要么是一颗空二叉树，要么是具有下列性质的二叉树

*  若它的左子树不空，则左子树上所有的节点的值均小于它的根节点的值
 *  若它的右子树不空，则右子树上所有的节点均大于它的根节点的值
 *  它的左右子树分别为排序二叉树。
 *

下图显示了一棵排序二叉树.  
对于排序二叉树，若按中序遍历就可以得到由小到大的有序序列。中序遍历得:

\{2,3,4,8,9,9,10,13,15,18)

![format_png 18][]

sort\_tree.PNG

创建排序二义树的步骤，就是不断地向排序二义树添加节点的过程，几体如下。

*  以根节点为当前节点开始搜索
 *  拿新节点的值和当前节点开始搜索
 *  如果新节点的值更大，则以当前的右子节点作为新的当前节点的右子节点作为新的当前节点;如果新节点的值更小，则以当前节点的右子节点作为新的当前节点。
 *  重复第2和3两个步骤，直到搜索到合适的叶子节点。
 *  将新节点添加为第4步找到的叶子节点的子节点，如果新节点更大，则添加为右子节点;否则,添加为左子节点。

当程序从排序二叉树中删除一个节点之后，为了让它依然保持为排序哭叉树，必须对该排序二叉树进行维护。维护可分为如下几种情况。

*  被删除节点是叶子节点，只需将它从其父节点中删除。
 *  被删除转点p只有左子树或只有右子树，如果p是它的父节点的左子节点，则将p的左子树或右子树添加成p一节点的父节点的左子节点即可;如果p是它的父节点的右子节点，则将p的左子树或右子树添加成P节点的父节点的右子节点即可。简单来说，如果要侧除的节点只有一个子节点，即可用它的子节点来代替要侧除的节点。

被删除的节点只有左子树的情况

![format_png 19][]

delete\_only\_left\_tree.PNG

被删除节点只有右子树的情况

![format_png 20][]

delete\_only\_right\_tree.PNG

*  若被删除节点p的左、右子树均非空，则有以下两种做法。
 *  将pL设为P的父节点q的左或右子节点(取决于P是其节父点q的左、右子节点)，  
    将pR设为P节点的中序前趋节点s的右子节点(s是pL最右下的节点，也就是pL子树中最大的节点)。采用这种方式删除节点的示意图如下：
    
     
    
                                                                 ![format_png 21][]
    
                                                                                      delete\_left\_right.PNG

以P节点的中序前趋或后继替代P所指节点，然后从原排序二叉树中删除中序前趋或后继节点。简单来说，就是用大于p的最小节点或小于P的最大节点代替P节点点,采  
用这种方式删除节点的示意图如下图：

![format_png 22][]

delete\_left\_right\_center.PNG

# 红黑树 #

排序二叉树虽然可以快速检索，但在最坏的情况下，如果插入的节点集本身就是有序的，要么是由小到大排列，要么是由大到小排列，那么最后得到的排序二义树将变成链表:所有节点只有左节点(如果插入节点集合本身是由大到小排列的)，或者所有节点只有右节点(如果  
插入节点集合本身是由小到大排列的)。在这种情况下，排序二叉树就变成了普通链表，其检索效率就会很低。

为了改变排序二叉树存在的不足，对二叉树进行改进————红黑树，他将这种排序二叉树称为“对称二叉B树”。

红黑树是一个更高效的检索二叉树，因此常常用来实现关联数组。典型的，JDK提供的集合类TreeMap本身就是一颗红黑树的实现。  
红黑树在原有的排序二叉树上增加如下几个要求：

*  性质l:每个节点要么是红色，要么是黑色。
 *  性质2:根节点永远是黑色的。
 *  除质3:所有的叶子节点都是空节点(即null)，并且是黑色的。
 *  性质4:每个红色节点的两个子节点都是黑色的。(从每个叶子到根的路径上不会有两个连续的红色节点。)
 *  性质5:从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点。

java实现的红黑树结构如下图：

![format_png 23][]

red\_black\_tree.PNG

*  根据性质5，红黑树从根节点到每个叶子节点的路径都包含相同数量的黑色节点，因此从根节点到叶子节点的路径中包含的黑色节点数被称为树的“黑色高度(black-height)".
 *  性质4则保证了从根节点到叶子节点的最长路径的一长度不会超过任何其他路径的2倍。假如有一棵黑色高度为3的红黑树，从根节点到叶子节点的最短路径长度是2,该路径上全是黑色节点〔黑色节点-黑色节点-黑色节点)。最长路径也只可能为4,在每个黑色节点之间插入一个红色节点〔黑色节点-红色节点-黑色书点-红色节点-黑色节点)，性质4保证绝不可能插入更多的红色节点。由此可见，红黑树中最长的路径就是一条红黑交替的路径。

由此可以得出结论：对于给定的黑色高度为N的红黑树，从根到叶子节点的最短路径长度为N-1，最长路径长度为2\*(N-1).

红黑树通过上面这种限制来保证它大致是平衡的—因为红黑树的高度不会无限增高，这样能保证红黑树在最坏的情况下都是高效的，不会出现普通排序二叉树的情况。

由于红黑树只是一棵特殊的排序二叉树，因此对红黑树上的只读操作与普通排序二叉树上的只读操作完全相同，只是红黑树保持了大致平衡，因此检索性能更好.

但在红黑树上进行插入操作和删除操作会导致树不再符合红黑树的特征，因此插入操作和删除操作都需要进行一定的维护，以保证插入节点、删除节点后的树依然是红黑树。

### 插入操作 ###

插入操作按如下步骤进行:

*  以排序二叉树的方法插入新节点，并将它设为红色。
 *  进行颜色调换和树旋转

这种颜色调换和树旋转就比较复杂了，下面将分情况进行介绍。在介绍中，把新插入的节点定义为N节点，把N节点的父节点定义为P节点，把P节点的兄弟节点定义为U节点，把P节点的父节点定义为G节点。

1.  情形1：新节点N是树的根节点，没有父节点。

在这种情形下，直接将它设置为黑色以满足性质2。

1.  情形2：新节点的父节点P是黑色的

在这种情形下，新插入的节点是红色的，因此依然满足性质4。而且因为新节点N有两个黑色叶子节点，但是由于新节点N是红色的，通过它的每个子节点的路径依然保持相同的黑色节点数，因此依然满足性质5

3.情形3：父节点P和父节点的兄弟节点U都是红色的

在这种情形下，程序应该将P节点、U节点都设置为黑色，并将P节点的父节点设置为红色(用来保持性质5)。现在，新节点N有了一个黑色的父节点P。由于从P节点、U节点到根节点的任何路径都必须通过G节点，这些路径上的黑色节点数目没有改变(原来有叶子和G节点两个黑色节点，现在有叶子和P节点两个黑色节点)。

经过上面处理后，红色的G节点的父节点也有可能是红色的，这就违反了性质4，因此还需要对G节点递归地进行整个过程〔把G节点当成新插入的节点进行处理)。  
下图显示了处理过程：

![format_png 24][]

red\_black\_tree\_1.PNG

1.  情形4:父节点P是红色的，而其兄弟节点U是黑色的或缺少;且新节点N是父节点P的右子节点，而父节点P又是其父节点G的左子节点。

在这种情形下，对新节点和其父节点进行一次左旋转。接着，按情形5处理以前的父节点P(也就是把P当成新插入的节点)。这将导致某些路径通过它们以前不通过的新节点N或父节点P其中之一，但是这两个节点都是红色的，因此不会影响性质5。

![format_png 25][]

red\_black\_tree\_2.PNG

1.  情形5:父节点F是红色的，而其兄弟节点U是黑色的或缺少:且新节点N是其父节点的左子节点，而父节点F父是其父节点G的左子节点。

在这种情形下，需要对节点G进行一次右旋转口在旋转产生的树中，以前的父节点P现在是新节点N和节点G的父节点。由于以前的节点G是黑色的(否则父节点P就不可能是红色的)，切换以前的父节点P和节点G的颜色，使之满足性质4。性质5也仍然保持满足，因为通过这三个节点中任何一个的所有路径以前都通过节点G,现在它们都通过以前的父节点P。在各自的情形下，这都是三个节点中唯一的黑色节点。

![format_png 26][]

red\_black\_tree\_3.PNG

### 删除操作 ###

红黑树的删除操作比插入操作要稍微复杂一些，实际上也可按如下步骤进行：

*  以排序二叉树的方法删除指定节点。
 *  进行颜色调换和树旋转，使之满足红黑树特征。

文章  
  
作者：Jack921  
链接：https://www.jianshu.com/p/b378864bb8fc  
来源：简书  
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy85MjU1NzYtYmQ1ZTI2Y2Q1NDI4OGEyYy5QTkc?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy85MjU1NzYtZmZkMjk3ODUwNmQ1ZWZhNS5QTkc_aW1hZ2VNb2dyMi9hdXRvLW9yaWVudC9zdHJpcHxpbWFnZVZpZXcyLzIvdy8yNzUvZm9ybWF0L3dlYnA?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy85MjU1NzYtOWY3MGZjZjgzMjM2N2MxZC5QTkc_aW1hZ2VNb2dyMi9hdXRvLW9yaWVudC9zdHJpcHxpbWFnZVZpZXcyLzIvdy8zMTAvZm9ybWF0L3dlYnA?x-oss-process=image/format,png
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy85MjU1NzYtMTQzNDgxNjgzNDg4N2UwNy5QTkc_aW1hZ2VNb2dyMi9hdXRvLW9yaWVudC9zdHJpcHxpbWFnZVZpZXcyLzIvdy8yNzIvZm9ybWF0L3dlYnA?x-oss-process=image/format,png
[format_png 4]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy85MjU1NzYtYTE3Nzg1MmI0M2FmNDAxZi5QTkc_aW1hZ2VNb2dyMi9hdXRvLW9yaWVudC9zdHJpcHxpbWFnZVZpZXcyLzIvdy8yMzUvZm9ybWF0L3dlYnA?x-oss-process=image/format,png
[format_png 5]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy85MjU1NzYtZjk1YmI2MDE3MTdlMzZhMy5QTkc_aW1hZ2VNb2dyMi9hdXRvLW9yaWVudC9zdHJpcHxpbWFnZVZpZXcyLzIvdy8yNjcvZm9ybWF0L3dlYnA?x-oss-process=image/format,png
[format_png 6]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy85MjU1NzYtYzI4MzA3ZjA5ZGU5YjEzZC5QTkc_aW1hZ2VNb2dyMi9hdXRvLW9yaWVudC9zdHJpcHxpbWFnZVZpZXcyLzIvdy81MzEvZm9ybWF0L3dlYnA?x-oss-process=image/format,png
[format_png 7]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy85MjU1NzYtZDZjMTRjOTMxNTRmZmU3MC5QTkc_aW1hZ2VNb2dyMi9hdXRvLW9yaWVudC9zdHJpcHxpbWFnZVZpZXcyLzIvdy8yMTcvZm9ybWF0L3dlYnA?x-oss-process=image/format,png
[format_png 8]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy85MjU1NzYtNjY3MDg1ODljZDM1ODcxZi5QTkc_aW1hZ2VNb2dyMi9hdXRvLW9yaWVudC9zdHJpcHxpbWFnZVZpZXcyLzIvdy8xOTUvZm9ybWF0L3dlYnA?x-oss-process=image/format,png
[format_png 9]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy85MjU1NzYtYzgyMzA5YTExYjhhZjRmOS5QTkc_aW1hZ2VNb2dyMi9hdXRvLW9yaWVudC9zdHJpcHxpbWFnZVZpZXcyLzIvdy8zNjUvZm9ybWF0L3dlYnA?x-oss-process=image/format,png
[format_png 10]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy85MjU1NzYtODY3NDg0ZjQyNzJhODkxZC5QTkc_aW1hZ2VNb2dyMi9hdXRvLW9yaWVudC9zdHJpcHxpbWFnZVZpZXcyLzIvdy80MTYvZm9ybWF0L3dlYnA?x-oss-process=image/format,png
[format_png 11]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy85MjU1NzYtM2ZlMmNmM2UzZGFjODZkNC5QTkc_aW1hZ2VNb2dyMi9hdXRvLW9yaWVudC9zdHJpcHxpbWFnZVZpZXcyLzIvdy8yMzYvZm9ybWF0L3dlYnA?x-oss-process=image/format,png
[format_png 12]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy85MjU1NzYtNzU2N2U0Y2RiNTkxZWZjOC5QTkc_aW1hZ2VNb2dyMi9hdXRvLW9yaWVudC9zdHJpcHxpbWFnZVZpZXcyLzIvdy8yMTYvZm9ybWF0L3dlYnA?x-oss-process=image/format,png
[format_png 13]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy85MjU1NzYtYTZkNGZkOWYyMDBkYzNjYi5QTkc_aW1hZ2VNb2dyMi9hdXRvLW9yaWVudC9zdHJpcHxpbWFnZVZpZXcyLzIvdy8xNzkvZm9ybWF0L3dlYnA?x-oss-process=image/format,png
[format_png 14]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy85MjU1NzYtODRlMzFmZGM0ZWE2MjVhZi5QTkc_aW1hZ2VNb2dyMi9hdXRvLW9yaWVudC9zdHJpcHxpbWFnZVZpZXcyLzIvdy8yMDIvZm9ybWF0L3dlYnA?x-oss-process=image/format,png
[format_png 15]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy85MjU1NzYtMTA5OTBkNWYzNjI4NGRkYy5QTkc_aW1hZ2VNb2dyMi9hdXRvLW9yaWVudC9zdHJpcHxpbWFnZVZpZXcyLzIvdy80OTEvZm9ybWF0L3dlYnA?x-oss-process=image/format,png
[format_png 16]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy85MjU1NzYtMTM0NzQyZGQyNGE2MDZlMy5QTkc_aW1hZ2VNb2dyMi9hdXRvLW9yaWVudC9zdHJpcHxpbWFnZVZpZXcyLzIvdy8xODQvZm9ybWF0L3dlYnA?x-oss-process=image/format,png
[format_png 17]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy85MjU1NzYtOWI2Zjc5YTU0NGI1MGJkZS5QTkc_aW1hZ2VNb2dyMi9hdXRvLW9yaWVudC9zdHJpcHxpbWFnZVZpZXcyLzIvdy8xODcvZm9ybWF0L3dlYnA?x-oss-process=image/format,png
[format_png 18]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy85MjU1NzYtMjA1MThiN2I3Y2NiZGExMi5QTkc_aW1hZ2VNb2dyMi9hdXRvLW9yaWVudC9zdHJpcHxpbWFnZVZpZXcyLzIvdy8yNzAvZm9ybWF0L3dlYnA?x-oss-process=image/format,png
[format_png 19]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy85MjU1NzYtZGY5ODU0MjFhNDZlYjIzOS5QTkc_aW1hZ2VNb2dyMi9hdXRvLW9yaWVudC9zdHJpcHxpbWFnZVZpZXcyLzIvdy8zNDAvZm9ybWF0L3dlYnA?x-oss-process=image/format,png
[format_png 20]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy85MjU1NzYtOTJlNGQ5NjBhNmFiNzFjOS5QTkc_aW1hZ2VNb2dyMi9hdXRvLW9yaWVudC9zdHJpcHxpbWFnZVZpZXcyLzIvdy8zNjcvZm9ybWF0L3dlYnA?x-oss-process=image/format,png
[format_png 21]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy85MjU1NzYtNGU4OTNmZGU1MGY4ZWQ1Zi5QTkc_aW1hZ2VNb2dyMi9hdXRvLW9yaWVudC9zdHJpcHxpbWFnZVZpZXcyLzIvdy8zODYvZm9ybWF0L3dlYnA?x-oss-process=image/format,png
[format_png 22]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy85MjU1NzYtNTQ5YWVhOGRjNTE0YjVlMy5QTkc_aW1hZ2VNb2dyMi9hdXRvLW9yaWVudC9zdHJpcHxpbWFnZVZpZXcyLzIvdy8zNTUvZm9ybWF0L3dlYnA?x-oss-process=image/format,png
[format_png 23]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy85MjU1NzYtZGQ0NDk4MjM5NzMwOTM2My5QTkc_aW1hZ2VNb2dyMi9hdXRvLW9yaWVudC9zdHJpcHxpbWFnZVZpZXcyLzIvdy80MDAvZm9ybWF0L3dlYnA?x-oss-process=image/format,png
[format_png 24]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy85MjU1NzYtNDk2ODM5M2YxMGZhN2FjNi5QTkc_aW1hZ2VNb2dyMi9hdXRvLW9yaWVudC9zdHJpcHxpbWFnZVZpZXcyLzIvdy8zNjAvZm9ybWF0L3dlYnA?x-oss-process=image/format,png
[format_png 25]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy85MjU1NzYtOGUyMGIwN2NiMzhiMDk4Yi5QTkc_aW1hZ2VNb2dyMi9hdXRvLW9yaWVudC9zdHJpcHxpbWFnZVZpZXcyLzIvdy8zNzQvZm9ybWF0L3dlYnA?x-oss-process=image/format,png
[format_png 26]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy85MjU1NzYtNDBhYTY3ZTcyMDc4MGMyYy5QTkc_aW1hZ2VNb2dyMi9hdXRvLW9yaWVudC9zdHJpcHxpbWFnZVZpZXcyLzIvdy8zOTAvZm9ybWF0L3dlYnA?x-oss-process=image/format,png