杨勇

摘要：红黑树是按照一定规则建立起来的平衡二叉查找树。为满足平衡条件，节点元素在插入和删除后，要进行颜色和位置的修正。修正过程相当复杂，给学习研究红黑树带来困难。通过在图元文件上画出红黑树，以图形方式，把插入和删除过程中的变化细节记录下来，使红黑树的操作可视化，从而给红黑树的理解和研究带来极大的便利。

关键词：红黑树;图元文件;平衡二叉树

中图分类号：TP311.11      文献标识码：A

文章编号：1009-3044（2021）35-0166-03

1 背景

二叉查找树（binary search tree）是一种重要的数据结构。其特点是，对于树中的每个节点，它的左子树所有节点值小于它，而右子树中所有节点值大于它。二叉树建立后，如果各节点子树的深度相差不多，则可以实现对节点数据的快速查找，平均运行时间能够达到O（logN）的时间复杂度。实际上，以上述规则建立起来的二叉查找树往往子树深度不能平衡。需要对树的节点位置进行调整，才能满足快速查找的要求。目前主要有两种方法能建立起近似平衡的二叉查找树，一种是AVL树，它保证树中每个节点左子树和右子树高度最多差1。另一种是红黑树（red black tree），它通过设定节点的颜色条件和数量，达到子树的近似平衡。红黑树的平衡程度比AVL树稍微低一点，数据查找时间复杂度相对要大，但是红黑树节点的插入和删除过程不涉及递归运算，比AVL树速度要快[1]。因此在软件工程实践中，红黑树得到了广泛的应用[2-5]，C++标准模板库中的容器类map，set以及Java JDK中的 treemap 等，都是采用红黑树结构实现的。但是，红黑树节点的插入，删除过程非常复杂，既有节点的旋转，也有节点颜色的变化，难于理解，给红黑树的学习、研究、应用带来不小的困难。如果能把插入删除过程中节点位置颜色变化细节以图示化的方法展示出来，则非常有助于理解红黑树的实现原理。当我们应用红黑树的原理开发应用软件时，还能够帮助我们查找程序中的错误。

2 红黑树的建立规则

红黑树是按以下规则建立起来的二叉查找树：1）每个节点或者是红色，或者是黑色（红黑只是对节点的一种区别标志）;2）根节点必须是黑色;3）任何有父子关系的两个节点不能都是红色;4）从任一节点出发的所有路径必须包含相同数目的黑节点。

图1显示了一棵红黑树，其中的黑色节点用双圆圈表示。规则4确保红黑树从任一节点出发的子树长度差不会超过一倍。图1中左子树只比右子树多一层。当对红黑树插入新的节点时，同样要遵循红黑树的建立规则，因此，按排序二叉树的方式插入之后，要进行节点位置和颜色的调整。例如， 对图1中的红黑树新插入一个节点6 ，首先按排序二叉树的要求，以红色节点插入节点5下成为5的右儿子，然后5的父节点3左旋，再节点5变黑色，节点3变红色。整个插入过程有4个步骤。红黑树节点愈多，插入删除时节点的旋转和变色就更复杂，通过想象或者手工画图已经很难把变化细节全部弄清楚。本文采取在图元文件上画出红黑树变化的方法，实现了红黑树插入删除细节的可视化演示。

3 图元文件上绘制图形

3.1 图元文件

图元文件是一种矢量图形，它与位图（bitmap）的记录方法不同。位图由像素组成，保存位图文件要同时记录每个像素的位置和颜色值，需要较大的存储空间。当位图放大时，像素呈方块状而使得图形边缘出现锯齿。而图元文件仅仅记录图形绘制的各种操作要素，如设备、文件大小、调色板、字体、填充区域等和绘制图形的函数。由于图元文件只记录图形绘制命令，由操作系统按文件记录的命令画图，因而图像缩放时不会有锯齿现象，失真度比较小，同时图元文件占用的存储空间也比位图文件小很多，因而能够快速处理大量图片，非常适合在windows窗体程序中画图。图元文件可以以文件形式存到磁盘上，也可以临时存储在内存中[6]。

图元文件的操作通过调用几个windows gdi函数实现。首先是图元文件创建函数：CreateEnhMetaFile（hdcRef，szFilename，lpRect，lpDescription）;

第一個参数hdcRef是参考设备描述表句柄，如果取NULL值，默认设备句柄为显示屏，不同的参考设备意味着不同的DPI，DPI表示每英寸能容纳的像素点，绘图函数以像素点为单位，为了让图元文件能够在打印机上打印输出，选取打印机的设备句柄，由于打印机的DPI远比显示器DPI高，图元文件显示到屏幕时不会产生清晰度损失。第二个参数是文件名，取NULL值时图元文件创建在内存中，本程序中图元文件首先在内存中创建，根据需要可以记录到磁盘上。第三个参数lpRect是一个Rect类指针，指出图元文件（长方形）的大小，表达图元文件大小的单位是0.01m， 因此，创建图元文件显示到屏幕上时，不能直接用屏幕像素点作为单位，要把图像的像素点大小换算成对应的图元文件大小。换算公式是：

[图像的像素点大小屏幕每英寸像素点数×25.4*100]（1英寸=25.4毫米）

第四个参数描述该图元文件的字符串，一般设为NULL。CreateEnhMetaFile 函数返回一个特定的设备描述表句柄，利用这个句柄，可以在其上调用画图函数绘制图形，要注意的是，由于参考设备句柄hdcRef设定为打印机的句柄，因此各种画图函数中传入的坐标应为打印机的像素点坐标。为了让图形适应各种分辨率的屏幕或者打印机，画图函数的坐标都应以相对绘图区域大小的比例值来设定。

绘图结束后，调用GDI函数CloseEnhMetaFile表明图元文件创建完成，函数会返回一个指向图元文件的句柄hMetaFile。将hMetaFile传递给PlayEnhMetaFile函数，可以将图元文件画到窗体指定区域中。将句柄hMetaFile传递给 CopyEnhMetaFile函数，可以将内存中的图元文件保存到磁盘上。

3.2 将红黑树绘制在图元文件上

红黑树的创建、插入、删除写在红黑树类RedBlackTree中。红黑树对象建立后，画图函数RBtreeShow将红黑树绘制在图元文件上。画图函数RBtreeShow以递归后序遍历的方式访问节点数据，每一个节点画一个圆表示，圆内是节点数据。节点颜色由圆的颜色代表，整个红黑树节点在窗体矩形区域内位置布局如图2所示。

图中L为布局区域总宽度，节点在每一层上等距离分布，节点横坐标以相对于L的比例计算，以分式表示。由图2可知，每一层节点，与下一层左、右两个儿子节点横坐标的关系是：

节点左儿子横坐标=[节点坐标分子*2-1节点坐标分母*2-1L]

节点右儿子横坐标=[节点坐标分子*2节点坐标分母*2-1L]

整个红黑树的绘制以绘制函数RBtreeShow的递归调用来完成，父子节点位置坐标的关系在递归调用时以参数传递，函数伪代码如下：

RBtreeShow （节点指针，画布总宽度，节点坐标分子，节点坐标分母，节点纵坐标）

{

计算当前节点坐标

计算左儿子节点坐标;

计算右儿子节点坐标;

如果有左儿子，画左连接线，递归调用RBtreeShow;

如果有右儿子，画右连接线，递归调用RBtreeShow;

在当前节点坐标处输出节点数据;

根据节点颜色，在节点数据上画圆;

}

红黑树变化时将画出多张图元文件，为便于图元文件的管理，设计了TViewPage类和TMetalFileView类，TViewPage类负责处理单个图元文件：

class  TViewPage

{

TControl* AOwner;

public：

HENHMETAFILE   hMetaFile;

TImage *       pImage;

int num;

int sub_num;

TViewPage（TComponent* AOwner，int width，int height，int num=0，int sub_num=0）;

void DrawPage（）;

void SetPagePos（int x，int y）;

};

TViewPage 以Image为图元文件的载体，成员函数DrawPage（）将图元文件画在Image的画布上，Image则显示于它的父窗体Panel上：

void   TViewPage：：DrawPage（）

{

pImage->Canvas->Brush->Color=clWhite;

pImage->Canvas->Rectangle（0，0，pImage->Width，pImage->Height）; //畫布填入白色背景

PlayEnhMetaFile（ pImage->Canvas->Handle， hMetaFile，&（pImage->ClientRect） ）;

pImage->Visible = true;   //画完后，显示图片，设为false则可以隐藏图片

}

DrawPage（）调用PlayEnhMetaFile函数在Image上画出图元文件。在Image上画图的优势是，可以通过控制Image的属性Visible将图片显示或隐藏，从而可以交替显示不同的图片，将红黑树的变化过程动态展示出来。TViewPage中的成员num和sub_num 则记录图片的主序号和子序号，对同一个节点操作的所有图片主序号num相同，操作细节过程图片以子序号sub_num区别。

TMetalFileView负责TViewPage类的创建，管理和查找。成员vector < TViewPage > ViewArray数组负责存储TViewPage对象。NewViewPage（int num，int sub_num）函数负责创建TViewPage对象，并记录图片的主序号和子序号。EndViewDoc（）函数结束图元文件的创建。ShowPage（int step，int sub_step）函数显示主序号为step，子序号为sub_step的图片。

4 红黑树节点插入过程动态演示

红黑树在修正时有多个中间形态，我们需要展示这些中间形态来研究变化细节。如何在修正过程中通知主窗体把红黑树画到图片上？本程序利用消息传递函数SendMessage给主窗口发消息，通知主窗口，调用画图函数画出图片。

首先建立一个自定义的消息 #define   WM_SHOW  WM_USER+1 。然后用消息映射宏命令BEGIN_MESSAGE_MAP，建立消息和消息处理函数之间的映射：

BEGIN_MESSAGE_MAP

VCL_MESSAGE_HANDLER（WM_SHOW， TMessage， TreeShow）;

END_MESSAGE_MAP（TForm）;

WM_SHOW 是消息常量，TMesage是接收消息的结构，TreeShow是消息处理函数。在TreeShow函数中再调用画图函数：

void __fastcall TForm1：：TreeShow（ TMessage& msg）

{

if（Combtreename->Text=="红黑树"）

{

pView->NewViewPage（step，++sub_step）; //建立一个新的图元文件

RBtreeShow（pRBTree->root->node， pView->PrnPageW-15，1，2，ROOT_Y，pView->Canvas） ;

String S= （char*）（msg.LParam）; //接收传递来的变化信息字符串

ShowTextOnCanvas_Memo（pView->Canvas，S， 11）; //变化信息字符串显示在图像左上方

}

}

然后在红黑树插入、删除和修正函数中需要画图的位置插入SendMessage函数，发送画图指令：

//*****************************

String str=" 节点："+IntToStr（node->key）+" 插入";

SendMessage（Form1->Handle，WM_SHOW，0，（LPARAM）str.c_str（））;

//*****************************

SendMessage第一个参数是接收消息的窗体句柄，第二参数为自定义的消息号WM_SHOW，第三，四个参数分别是wParam， lParam，可以传递附加信息，把节点的变化细节信息写入字符串str中，由lParam参数携带，随消息一起传送。消息通知模式使红黑树操作模块与显示模块耦合度很低，可以很容易地扩展应用到其他类型二叉树的动态演示上，以这种模式，还实现了AVL树，最小堆等数据结构的动态演示。图3～图7展示了图1中节点8的插入和修正细节，图片全部由程序自动生成。

5 结束语

应用在内存图元文件上画图的方法，将红黑树插入，删除操作时，各节点的变化过程以图示方式显示出来，直观地展示了节点变化的每一步细节，便于我们深入学习和研究红黑树的构造原理。采用类似的方法，还可以实现多种数据结构建立过程的可视化，例如平衡二叉树、B树、二叉堆等。

参考文献：

[1] Weiss M A.数据结构与算法分析：C++语言描述[M]. 冯舜玺，译.北京：电子工业出版社，2016.

[2] 马博韬，孙鹏，朱小勇.红黑树算法研究综述[J].网络新媒体技术，2018，7（4）：56-62.

[3] 唐自立.一种新的删除红黑树的结点的算法[J].计算机应用与软件，2006，23（1）：139-141.

[4] 李征宇，孙平，王凤英.基于集合的红黑树结点删除算法的实现[J].长春大学学报，2012，22（4）：426-428，436.

[5] 陳广，伍德鹏.一种红黑树的改进算法[J].内蒙古师范大学学报（教育科学版），2012，25（12）：75-79.

[6] Petzold C.Windows程序设计[M].北京博彦科技发展有限公司，译.北京：北京大学出版社，2009.

【通联编辑：谢媛媛】