一、问题描述

实现3种树中的两种：红黑树，AVL树，Treap树

二、算法原理

（1）红黑树

红黑树是一种二叉查找树，但在每个结点上增加一个存储位表示结点的颜色，可以是red或black。红黑树满足以下五个性质：

1) 每个结点或是红色或是黑色

2) 根结点是黑色

3) 每个叶结点是黑的

4)如果一个结点是红的，则它的两个儿子均是黑色

5) 每个结点到其子孙结点的所有路径上包含相同数目的黑色结点

本实验主要实现红黑树的初始化，插入和删除操作。当对红黑树进行插入和

删除操作时，可能会破坏红黑树的五个性质。为了保证红黑树的性质，需要进行修改颜色和指针结构等。指针结构的修改是通过旋转操作完成。因此这里首先描述红黑树的旋转操作。

A．旋转操作

旋转操作主要分为左旋和右旋操作。当在某个节点x上进行左旋操作时，假设x的右孩子y不是nil[T]，左旋以x到y之间的链为轴进行，使得y成为该子树新的根，x成为y的左孩子，而y的左孩子则成为x的右孩子。右旋类似。

B．插入操作

红黑树的插入操作主要有两个步骤。

a) 首先以二叉查找树的方式插入一个红色结点；

b) 然后对新的二叉树进行修复，即进行颜色调整或旋转操作，以此满足红

黑树的五个性质。

在对红黑树进行插入修复操作时，循环进入条件是当前结点的父结点为红色

即性质4破坏。在修复函数中主要考虑以下三种情况：

情况1：插入结点z的父结点为红色，而z的叔叔结点y是红色

 此时z的父结点的父结点一定存在，而且必为黑色结点，否则插入前即不是红黑树。这种情况的主要思路就是修改z的父结点和叔叔结点y的颜色为黑色，z的祖父结点的颜色修改为红色，目的就是红色上移，然后当前结点指针指向祖父结点，循环进行修复操作

情况2：z的父结点为红色，而z的叔叔结点y是黑色，而且z是右孩子

此时将当前节点的z的父结点设为新的当前节点，并以新当前节点为支点左旋。将情况2转化为情况3。

情况3：z的父结点为红色，而z的叔叔结点y是黑色，而且z是左孩子

此时将z的父节点修改为黑色，祖父节点变为红色，并以祖父节点为支点进行右旋操作。此时一行中不再有两个连续的红色结点，红黑树所有性质调整完成，因此所有的处理到此完毕。

C．删除操作

类似插入，红黑树的删除操作主要有两个步骤。

c)     首先以二叉查找树的方式删除一个指定结点；

d)     然后对新的二叉树进行修复，即进行颜色调整或旋转操作，以此满足红

黑树的五个性质。

在对红黑树进行删除修复操作时，循环进入条件是当前结点x为非根结点并

且是双重黑结点。在修复函数中主要考虑以下四种情况：

情况1：x的兄弟结点w是红色的

此时需把父结点修改成红色，把兄弟结点w修改成黑色。然后，针对父结点进行左旋操作，此时红黑树性质5不变。将情况1转化为其他情况。

情况2：x的兄弟w是黑色的，而且w的两个孩子都是黑色的

此时需从当前结点x和兄弟节点w去掉一重黑色，从而x只有一重黑色而w是红色。同时为了补偿去掉的一重黑色，需在x的父结点上增加一重黑色，并把x的父结点作为新的当前节点，重新进入循环。

情况3：x的兄弟w是黑色的，w的左孩子是红色的，右孩子是黑色的

此时需把兄弟结点w修改成红色，兄弟w的左孩子修改成黑色，然后以兄弟结点w作为支点进行右旋操作，之后重新进入算法。将情况5转化为情况6。

情况4：x的兄弟w是黑色的，而且w的右孩子是红色的

此时需将兄弟结点w修改成x的父结点的颜色，然后将x的父结点修改成黑色，兄弟结点w的右孩子修改成黑色，然后以x的父结点为支点进行左旋操作。此时算法结束，红黑树所有性质调整完成。

D．计算根结点到叶结点所有路径对应的黑高度

对红黑树进行插入或删除结点时，为了能够保持红黑树的性质会进行对应的修复操作。为了能更直观的测试经过该修复操作后红黑树的性质是否正确的得到满足，在本次实验的结果中将依次输出根结点到叶结点的所有路径并输出该路径上所有黑色结点的个数。因此需要实现一个输出路径并计算对应黑高度的方法。

该方法的主要原理就是利用递归思想，在函数内部维护一个记录路径结点的数组path[]。每访问一个结点时，首先判断该结点是否为哨兵结点。若为哨兵，则表示该路径已扫描结束。此时需把路径输出，并输出对应黑高度。若该结点不是哨兵结点，此时需把该结点关键字值记录到path[]数组中。同时如果该结点为黑色，则将表示黑高度的变量值加1.做完这些操作之后，则一次递归调用该结点的左右子树。实现该操作的主要代码如下：

E．打印树的结构

在对红黑树进行插入或删除操作之后，为了能够更加直观的观察当前红黑树的特点，本实验将在结果中输出当前红黑树的结构。实现该操作的主要原理就是利用树的结构特点，优先打印出右子树，然后打印根结点值和该结点的颜色，最后打印出左子树，在函数中通过空格来控制最后的显示效果。主要代码如下：

（2）AVL树

AVL树是一种高度平衡的二叉查找树。它或者是一颗空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。在AVL树中的每个结点都有一个平衡因子bf，它表示这个结点的左、右子树的高度差，即左子树的高度减去右子树的高度。AVL树上所有结点的平衡因子只能是-1、0、1。

实现AVL树的关键在于维持树的平衡性。每当进行插入或删除操作时都有可能破坏了树的平衡性。因此首先检查是否破坏了树的平衡性，如果因插入结点而破坏了二叉查找树的平衡，则找出离插入点最近的不平衡结点，然后将该不平衡结点为根的子树进行旋转操作。旋转操作主要分为：LL型、RR型、LR型、RL型等。

A．旋转操作

a)     LL型

由于在A的左子树根结点B的左子树上插入结点，使A的平衡因子由1增至2而失去平衡。故需进行一次向右顺时针旋转操作。 即将A的左孩子B向右上旋转代替A作为根结点，A向右下旋转成为B的右子树的根结点。而原来B的右子树则变成A的左子树。

b)     RR型

由于在A的右子树根结点B的右子树上插入结点，使A的平衡因子由-1增至-2而失去平衡。故需进行一次向左顺时针旋转操作。

c)     LR型

由于在A的左子树根结点B的右子树上插入结点，使A的平衡因子由1增至2而失去平衡。故需进行两次旋转操作，先左旋再右旋。

d)     RL型

由于在A的右子树根结点B的左子树上插入结点，使A的平衡因子由-1增至-2而失去平衡。故需进行两次旋转操作，先左旋再右旋。

B．插入操作

在AVL树上插入一个新的数据元素e的递归算法可描述如下：　

(1)若BBST为空树，则插入一个数据元素为e的新结点作为BBST的根结点，树的深度增1；

(2)若e的关键字和BBST的根结点的关键字相等，则不进行；

(3)若e的关键字小于BBST的根结点的关键字，而且在BBST的左子树中不存在和e有相同关键字的结点，则将e插入在BBST的左子树上，并且当插入之后的左子树深度增加（+1）时，分别就下列不同情况处理之：

a、BBST的根结点的平衡因子为-1（右子树的深度大于左子树的深度，则将根结点的平衡因子更改为0，BBST的深度不变；

b、BBST的根结点的平衡因子为0（左、右子树的深度相等）：则将根结点的平衡因子更改为1，BBST的深度增1；

c、BBST的根结点的平衡因子为1（左子树的深度大于右子树的深度）：若BBST的左子树根结点的平衡因子为1：则需进行单向右旋平衡处理，并且在右旋处理之后，将根结点和其右子树根结点的平衡因子更改为0，树的深度不变；

(4)若e的关键字大于BBST的根结点的关键字，而且在BBST的右子树中不存在和e有相同关键字的结点，则将e插入在BBST的右子树上，并且当插入之后的右子树深度增加（+1）时，分别就不同情况处理之。

C．删除操作

假设被删结点x的父结点为y, 如果删除的是y的左子树, 则y的平衡因子bf减1, 否则y的平衡因子bf加1. 根据y的平衡因子的值分为以下三种情况：

情况一：

如果结点y的新的平衡因子bf等于0,则表示删除前y的平衡因子等于1 或者-1, 此时高度减1, 需改变父节点和其他祖父节点的平衡因子

情况二：

如果结点y的新的平衡因子bf等于1或者-1,则表示删除前y的平衡因子等于0, 左右子树高度一样, 此时高度不变, 需改变父节点和其他某些祖父节点的平衡因子.

情况三：

如果结点y新的平衡因子bf等于-2或2, 则表示删除前y的平衡因子1等于或-1, 左右子树高度不相同, 此时树在结点y是不平衡的, 需要做平衡化处理

三、实验数据

（1）输入：

红黑树实验和AVL树实验采用的数据均是随机生成的20个关键字值。然后依次将这些关键字利用插入算法插入到相应树中。在进行删除操作时，删除的数据是随机选取的3个关键字值，然后依次删除对应结点。

（2）输出：

对于红黑树，在进行插入和删除操作后，将输出对应树的结构，并标明结点的颜色（red或black），然后计算根结点到叶结点所有路径的黑高度并依次输出显示。

四、源代码

下载链接：http://download.csdn.net/detail/zhh1992/8359301

红黑树和AVL树的实现与比较-----算法导论