动态演示红黑树

动态演示红黑树，面试必备

满足以下两个条件的树就是二叉树：

本身是有序树(若将树中每一个结点的各子树看成是从左到右有次序的(

即不能互换)，则称该树为有序树(OrderedTree))。

树中包含的各个节点的度小能超过2,即只能是0、1或者2。

简约地理解，二叉树(Binarylre)e是每一个节点最多只要两个分支(即不存

在分支度大于2的节点)的树结构。通常分支被称作左“子树”或者右“子树”。

二叉查找树

要了解红缥树之前，免不了先看下一叉查找树是什么.

维基百科上的定义：二叉查找树(英语：BinarySearchTr)ee,也称为二义

搜索树、有序二叉树(orderedbinarytr)e或排序二叉枕(sortedbinarytrc)e,

是指一棵空树或者具有下列性质的二叉树。

若任意节点的左子树不空，则左子树上全部节点的值均小于它的根节点的

值；若任意节点的右子树不空，则右子树上全部节点的值均大于或者等于

它的根节点的值；任意节点的左、右子树也分别为二叉查找树。

图示理解：

上图为查找值为29的节点，有以卜步骤：

查看根节点41。

由于41>29,所以查看41的左孩子20。

由于20<29,所以查看20的右孩子29,发觉其正好是要查看的节点。

退化

二叉杳找树有个分外严峻的问题，假如数据的插入是从大到小插入的，或者

者是从小到大插入的话，会导致二叉查找树退化成单链表的方式，俗称痛

子。

**左痛子：竹例如，插入数据挨次为｛5,4,32（1｝从大到小），则如下图所示

©

**右痛子：**例如，插入数据挨次为｛123,4.5｝从小到大），则如下图所示:

o

为了处理该问题，泯灭了一些处理方法，即平衡，能够使得树趋向平衡，

这种自平衡的树叫做平衡树。

平衡树

平衡树（BalanceTre,eBT）指的是，任意节点的子树的高度差都小于等于1。

常见的符合平衡树的有AVL树（二叉平衡搜索树），B树（多路平衡搜索

树，2-3树，2-3-4树中的一种），红黑树等。

AVL树

AVL树（由创造者Adelson-Velsk和Landis的首字母缩写命名），是指任意

节点的两个子树的高度差不超过1的平衡树。又称自平衡二叉搜索树。

AVL树能处理上文二义查找树中的右揣子问题，例如，插入数据挨次为

（1,2,3,4,期从小到大），则如下图所示：

o

AVL树会对不符合高度差的结构进行调整，从而使得二叉树趋向平衡

2・3树

2-3树，是指每一个具有子节点的节点（内部节点，internalnod）e要末有两

个子节点和一个数据元素，要末有三个子节点和两个数据元素的自平衡的

树，它的全部叶子节点都具有相同的高度。

简约点讲，2-3树的非叶子节点都具有两个分叉或者三个分叉，所以，称作

2叉-3叉树更简约理解。

此外一种说法，具有两个子节点和一个数据元素的节点又称作2节点，具

有三个子节点和两个数据元素的节点又称作3节点，所以，整颗树叫做2-3

树。

8

全部叶子点都在树的同一层，一样高:

性质1：满足二叉搜索树的性质。

性质2：节点可以存放一个或者两个元素。

性质3：每一个节点有两个或者三个子节点。

创建2-3树的规章

插入操作如下：

向2-节点中插入元素:

向一颗只含有一个3-节点的树中插入元素:

2-3-4树

含义如下:

**2节点：**包含两个子节点和一个数据元素。

**3节点：**包含三个子节点和一个数据元素。

**4节点：**包含四个子节点和一个数据元素。

2-3-4树，它的每一个非叶子节点，要末是2节点，要末是3节点，要末是4

节点，且可以自平衡，所以称作2-3-4树。

规章如下：

**规章1：**加入新节点时，不会往空的位置添加节点，而是添加到最

终一个叶子节点上。

**规章2：**四节点可以被分解三个2-节点组成的树，并且分解后新树

的根节点需要向上和父节点融合。

插入操作

本来的2-3-4树，如下图:

对于上图的2-3-4树，插入一个节点17,由于规章1,节点17不会加入节

点［16,18,20的］子树，而是与该节点融合。

由于规章2,节点［16,17.18,2是0］一个4节点，将该节点进行拆解成新的

此时树暂时得到了平衡，我们需要将拆分后的子树的根节点向上进行融

合。

6101418

同理可得，由于规章2,节点［6,10.14,1是8］一个4节点，将该节点进行拆

总结了下插入节点的过程，无非也就为了符合两条规章，那末，2-3树，2-

34树都有了，那是不是也有2-3-4-树5,2-345-..树.-的存在呢？

现实上是有的，世人把这一类树称为一个名字：B树。

B树

B树，表示的是一类树，它允许一个节点可以有多于两个子节点，同时，也

是自平衡的，叶子节点的高度都是相同的。

所以，为了更好地区分一颗B树到底属于哪一类树，我们给它一个新的属

性：度（Degree）：一个节点能有多少箭头指向其他节点。

具有度为3的B树，表示一个节点最多有三个子节点，也就是2-3树的定

义。具有度为4的B树，表示一个节点最多有四个子节点，也就是2-3-4树

的定义。

图为4的B树的示例图：

R-BTree,全称是Red-BlackTr,ee乂称为红“黑树”，它一种特殊的二又查找树。

红黑树的每一个节点上都有存储位表示节点的颜色，可以是红（Red）或

者黑（Black）。

如何理解红黑树

如其次张图所示，将该红黑树与上文讲到的2-3-4树定照，能否发觉，红黑

树就是一个2-3-4树：

每一个节点或者是黑色，或者是红色。

根节点是黑色。

每一个叶子节点（NIL）是黑色。留意：这里叶子节点，是指为空（NIL

或者NULL）的叶子节点！

假如一个节点是红色的，则它的子节点必需是黑色的。由于红黑树的每

个节点都是由2・3-4树转化而来的，从而红色节点不能连续两个泯灭，

不然会泯灭4节点的情况，导致违反了规章2。

而且纤黑树的每一个黑节点都是3节点中的最两头的那个值,或者是2

节点中其中一个值。

从一个节点到该节点的子孙节点的全部路径上包含相同数目的黑节点。

**原由：**红黑树这些黑色节点在2-3-4树中代表的是由1节点的一个2-3-

4树，而2・3-4树是同二个子树的深度是相同的，平衡的，所以从二个节点

到该节点的子孙节点的全部路径上包含相同数目的黑节点。

如下图所示，蓝色代表是黑色节点：

留意如下几点:

特性（3）中的叶子节点，是只为空（NIL或者null）的节点。

特性（5）,确保没有一条路径会比其他路径长出俩倍。于是，红黑树

是相对是接近平衡的二叉树。

红黑树虽然本质上是一棵二又查找树，但它在二义查找树的基础上添加

了着色和相关的性质使得红黑树相对平衡，从而保证了红黑树的查找、

插入、删除的时间简单度最坏为O（logn。）

由上面的例子所示，我们只需把红黑树当做是2-3-4树来处理，并且对应的

颜色进行转变或者进行左旋右旋的操作，即可达到使得红黑树平衡的目标。

如何保持红黑树的结构

当我们插入一个新的节点的时候，如何保证红黑树的结构照旧能够符合上

面的五个特性呢？

树的旋转分为左旋和右旋，下面借助图来引见一下左旋和右旋这两种操

作。

①左旋

本来的形态：

E4ndSthan$

过程图:

rotateEl«fl

(b«for«)

结束图:

rot4it«EHrft

(•her)

如上图所示