基于圖元文件實(shí)現(xiàn)紅黑樹插入刪除過程的動(dòng)態(tài)演示

楊勇

摘要：紅黑樹是按照一定規(guī)則建立起來的平衡二叉查找樹。為滿足平衡條件，節(jié)點(diǎn)元素在插入和刪除后，要進(jìn)行顏色和位置的修正。修正過程相當(dāng)復(fù)雜，給學(xué)習(xí)研究紅黑樹帶來困難。通過在圖元文件上畫出紅黑樹，以圖形方式，把插入和刪除過程中的變化細(xì)節(jié)記錄下來，使紅黑樹的操作可視化，從而給紅黑樹的理解和研究帶來極大的便利。

關(guān)鍵詞：紅黑樹;圖元文件;平衡二叉樹

中圖分類號(hào)：TP311.11 ? ? ?文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2021）35-0166-03

1 背景

二叉查找樹（binary search tree）是一種重要的數(shù)據(jù)結(jié)構(gòu)。其特點(diǎn)是，對(duì)于樹中的每個(gè)節(jié)點(diǎn)，它的左子樹所有節(jié)點(diǎn)值小于它，而右子樹中所有節(jié)點(diǎn)值大于它。二叉樹建立后，如果各節(jié)點(diǎn)子樹的深度相差不多，則可以實(shí)現(xiàn)對(duì)節(jié)點(diǎn)數(shù)據(jù)的快速查找，平均運(yùn)行時(shí)間能夠達(dá)到O（logN）的時(shí)間復(fù)雜度。實(shí)際上，以上述規(guī)則建立起來的二叉查找樹往往子樹深度不能平衡。需要對(duì)樹的節(jié)點(diǎn)位置進(jìn)行調(diào)整，才能滿足快速查找的要求。目前主要有兩種方法能建立起近似平衡的二叉查找樹，一種是AVL樹，它保證樹中每個(gè)節(jié)點(diǎn)左子樹和右子樹高度最多差1。另一種是紅黑樹（red black tree），它通過設(shè)定節(jié)點(diǎn)的顏色條件和數(shù)量，達(dá)到子樹的近似平衡。紅黑樹的平衡程度比AVL樹稍微低一點(diǎn)，數(shù)據(jù)查找時(shí)間復(fù)雜度相對(duì)要大，但是紅黑樹節(jié)點(diǎn)的插入和刪除過程不涉及遞歸運(yùn)算，比AVL樹速度要快[1]。因此在軟件工程實(shí)踐中，紅黑樹得到了廣泛的應(yīng)用[2-5]，C++標(biāo)準(zhǔn)模板庫中的容器類map，set以及Java JDK中的 treemap 等，都是采用紅黑樹結(jié)構(gòu)實(shí)現(xiàn)的。但是，紅黑樹節(jié)點(diǎn)的插入，刪除過程非常復(fù)雜，既有節(jié)點(diǎn)的旋轉(zhuǎn)，也有節(jié)點(diǎn)顏色的變化，難于理解，給紅黑樹的學(xué)習(xí)、研究、應(yīng)用帶來不小的困難。如果能把插入刪除過程中節(jié)點(diǎn)位置顏色變化細(xì)節(jié)以圖示化的方法展示出來，則非常有助于理解紅黑樹的實(shí)現(xiàn)原理。當(dāng)我們應(yīng)用紅黑樹的原理開發(fā)應(yīng)用軟件時(shí)，還能夠幫助我們查找程序中的錯(cuò)誤。

2 紅黑樹的建立規(guī)則

紅黑樹是按以下規(guī)則建立起來的二叉查找樹：1）每個(gè)節(jié)點(diǎn)或者是紅色，或者是黑色（紅黑只是對(duì)節(jié)點(diǎn)的一種區(qū)別標(biāo)志）;2）根節(jié)點(diǎn)必須是黑色;3）任何有父子關(guān)系的兩個(gè)節(jié)點(diǎn)不能都是紅色;4）從任一節(jié)點(diǎn)出發(fā)的所有路徑必須包含相同數(shù)目的黑節(jié)點(diǎn)。

圖1顯示了一棵紅黑樹，其中的黑色節(jié)點(diǎn)用雙圓圈表示。規(guī)則4確保紅黑樹從任一節(jié)點(diǎn)出發(fā)的子樹長度差不會(huì)超過一倍。圖1中左子樹只比右子樹多一層。當(dāng)對(duì)紅黑樹插入新的節(jié)點(diǎn)時(shí)，同樣要遵循紅黑樹的建立規(guī)則，因此，按排序二叉樹的方式插入之后，要進(jìn)行節(jié)點(diǎn)位置和顏色的調(diào)整。例如， 對(duì)圖1中的紅黑樹新插入一個(gè)節(jié)點(diǎn)6 ，首先按排序二叉樹的要求，以紅色節(jié)點(diǎn)插入節(jié)點(diǎn)5下成為5的右兒子，然后5的父節(jié)點(diǎn)3左旋，再節(jié)點(diǎn)5變黑色，節(jié)點(diǎn)3變紅色。整個(gè)插入過程有4個(gè)步驟。紅黑樹節(jié)點(diǎn)愈多，插入刪除時(shí)節(jié)點(diǎn)的旋轉(zhuǎn)和變色就更復(fù)雜，通過想象或者手工畫圖已經(jīng)很難把變化細(xì)節(jié)全部弄清楚。本文采取在圖元文件上畫出紅黑樹變化的方法，實(shí)現(xiàn)了紅黑樹插入刪除細(xì)節(jié)的可視化演示。

3 圖元文件上繪制圖形

3.1 圖元文件

圖元文件是一種矢量圖形，它與位圖（bitmap）的記錄方法不同。位圖由像素組成，保存位圖文件要同時(shí)記錄每個(gè)像素的位置和顏色值，需要較大的存儲(chǔ)空間。當(dāng)位圖放大時(shí)，像素呈方塊狀而使得圖形邊緣出現(xiàn)鋸齒。而圖元文件僅僅記錄圖形繪制的各種操作要素，如設(shè)備、文件大小、調(diào)色板、字體、填充區(qū)域等和繪制圖形的函數(shù)。由于圖元文件只記錄圖形繪制命令，由操作系統(tǒng)按文件記錄的命令畫圖，因而圖像縮放時(shí)不會(huì)有鋸齒現(xiàn)象，失真度比較小，同時(shí)圖元文件占用的存儲(chǔ)空間也比位圖文件小很多，因而能夠快速處理大量圖片，非常適合在windows窗體程序中畫圖。圖元文件可以以文件形式存到磁盤上，也可以臨時(shí)存儲(chǔ)在內(nèi)存中[6]。

圖元文件的操作通過調(diào)用幾個(gè)windows gdi函數(shù)實(shí)現(xiàn)。首先是圖元文件創(chuàng)建函數(shù)：CreateEnhMetaFile（hdcRef，szFilename，lpRect，lpDescription）;

第一個(gè)參數(shù)hdcRef是參考設(shè)備描述表句柄，如果取NULL值，默認(rèn)設(shè)備句柄為顯示屏，不同的參考設(shè)備意味著不同的DPI，DPI表示每英寸能容納的像素點(diǎn)，繪圖函數(shù)以像素點(diǎn)為單位，為了讓圖元文件能夠在打印機(jī)上打印輸出，選取打印機(jī)的設(shè)備句柄，由于打印機(jī)的DPI遠(yuǎn)比顯示器DPI高，圖元文件顯示到屏幕時(shí)不會(huì)產(chǎn)生清晰度損失。第二個(gè)參數(shù)是文件名，取NULL值時(shí)圖元文件創(chuàng)建在內(nèi)存中，本程序中圖元文件首先在內(nèi)存中創(chuàng)建，根據(jù)需要可以記錄到磁盤上。第三個(gè)參數(shù)lpRect是一個(gè)Rect類指針，指出圖元文件（長方形）的大小，表達(dá)圖元文件大小的單位是0.01m， 因此，創(chuàng)建圖元文件顯示到屏幕上時(shí)，不能直接用屏幕像素點(diǎn)作為單位，要把圖像的像素點(diǎn)大小換算成對(duì)應(yīng)的圖元文件大小。換算公式是：

[圖像的像素點(diǎn)大小屏幕每英寸像素點(diǎn)數(shù)×25.4*100]（1英寸=25.4毫米）

第四個(gè)參數(shù)描述該圖元文件的字符串，一般設(shè)為NULL。CreateEnhMetaFile 函數(shù)返回一個(gè)特定的設(shè)備描述表句柄，利用這個(gè)句柄，可以在其上調(diào)用畫圖函數(shù)繪制圖形，要注意的是，由于參考設(shè)備句柄hdcRef設(shè)定為打印機(jī)的句柄，因此各種畫圖函數(shù)中傳入的坐標(biāo)應(yīng)為打印機(jī)的像素點(diǎn)坐標(biāo)。為了讓圖形適應(yīng)各種分辨率的屏幕或者打印機(jī)，畫圖函數(shù)的坐標(biāo)都應(yīng)以相對(duì)繪圖區(qū)域大小的比例值來設(shè)定。

繪圖結(jié)束后，調(diào)用GDI函數(shù)CloseEnhMetaFile表明圖元文件創(chuàng)建完成，函數(shù)會(huì)返回一個(gè)指向圖元文件的句柄hMetaFile。將hMetaFile傳遞給PlayEnhMetaFile函數(shù)，可以將圖元文件畫到窗體指定區(qū)域中。將句柄hMetaFile傳遞給 CopyEnhMetaFile函數(shù)，可以將內(nèi)存中的圖元文件保存到磁盤上。

3.2 將紅黑樹繪制在圖元文件上

紅黑樹的創(chuàng)建、插入、刪除寫在紅黑樹類RedBlackTree中。紅黑樹對(duì)象建立后，畫圖函數(shù)RBtreeShow將紅黑樹繪制在圖元文件上。畫圖函數(shù)RBtreeShow以遞歸后序遍歷的方式訪問節(jié)點(diǎn)數(shù)據(jù)，每一個(gè)節(jié)點(diǎn)畫一個(gè)圓表示，圓內(nèi)是節(jié)點(diǎn)數(shù)據(jù)。節(jié)點(diǎn)顏色由圓的顏色代表，整個(gè)紅黑樹節(jié)點(diǎn)在窗體矩形區(qū)域內(nèi)位置布局如圖2所示。

圖中L為布局區(qū)域總寬度，節(jié)點(diǎn)在每一層上等距離分布，節(jié)點(diǎn)橫坐標(biāo)以相對(duì)于L的比例計(jì)算，以分式表示。由圖2可知，每一層節(jié)點(diǎn)，與下一層左、右兩個(gè)兒子節(jié)點(diǎn)橫坐標(biāo)的關(guān)系是：

節(jié)點(diǎn)左兒子橫坐標(biāo)=[節(jié)點(diǎn)坐標(biāo)分子*2-1節(jié)點(diǎn)坐標(biāo)分母*2-1L]

節(jié)點(diǎn)右兒子橫坐標(biāo)=[節(jié)點(diǎn)坐標(biāo)分子*2節(jié)點(diǎn)坐標(biāo)分母*2-1L]

整個(gè)紅黑樹的繪制以繪制函數(shù)RBtreeShow的遞歸調(diào)用來完成，父子節(jié)點(diǎn)位置坐標(biāo)的關(guān)系在遞歸調(diào)用時(shí)以參數(shù)傳遞，函數(shù)偽代碼如下：

RBtreeShow （節(jié)點(diǎn)指針，畫布總寬度，節(jié)點(diǎn)坐標(biāo)分子，節(jié)點(diǎn)坐標(biāo)分母，節(jié)點(diǎn)縱坐標(biāo)）

{

計(jì)算當(dāng)前節(jié)點(diǎn)坐標(biāo)

計(jì)算左兒子節(jié)點(diǎn)坐標(biāo);

計(jì)算右兒子節(jié)點(diǎn)坐標(biāo);

如果有左兒子，畫左連接線，遞歸調(diào)用RBtreeShow;

如果有右兒子，畫右連接線，遞歸調(diào)用RBtreeShow;

在當(dāng)前節(jié)點(diǎn)坐標(biāo)處輸出節(jié)點(diǎn)數(shù)據(jù);

根據(jù)節(jié)點(diǎn)顏色，在節(jié)點(diǎn)數(shù)據(jù)上畫圓;

}

紅黑樹變化時(shí)將畫出多張圖元文件，為便于圖元文件的管理，設(shè)計(jì)了TViewPage類和TMetalFileView類，TViewPage類負(fù)責(zé)處理單個(gè)圖元文件：

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為圖元文件的載體，成員函數(shù)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; ? //畫完后，顯示圖片，設(shè)為false則可以隱藏圖片

}

DrawPage（）調(diào)用PlayEnhMetaFile函數(shù)在Image上畫出圖元文件。在Image上畫圖的優(yōu)勢(shì)是，可以通過控制Image的屬性Visible將圖片顯示或隱藏，從而可以交替顯示不同的圖片，將紅黑樹的變化過程動(dòng)態(tài)展示出來。TViewPage中的成員num和sub_num 則記錄圖片的主序號(hào)和子序號(hào)，對(duì)同一個(gè)節(jié)點(diǎn)操作的所有圖片主序號(hào)num相同，操作細(xì)節(jié)過程圖片以子序號(hào)sub_num區(qū)別。

TMetalFileView負(fù)責(zé)TViewPage類的創(chuàng)建，管理和查找。成員vector < TViewPage > ViewArray數(shù)組負(fù)責(zé)存儲(chǔ)TViewPage對(duì)象。NewViewPage（int num，int sub_num）函數(shù)負(fù)責(zé)創(chuàng)建TViewPage對(duì)象，并記錄圖片的主序號(hào)和子序號(hào)。EndViewDoc（）函數(shù)結(jié)束圖元文件的創(chuàng)建。ShowPage（int step，int sub_step）函數(shù)顯示主序號(hào)為step，子序號(hào)為sub_step的圖片。

4 紅黑樹節(jié)點(diǎn)插入過程動(dòng)態(tài)演示

紅黑樹在修正時(shí)有多個(gè)中間形態(tài)，我們需要展示這些中間形態(tài)來研究變化細(xì)節(jié)。如何在修正過程中通知主窗體把紅黑樹畫到圖片上？本程序利用消息傳遞函數(shù)SendMessage給主窗口發(fā)消息，通知主窗口，調(diào)用畫圖函數(shù)畫出圖片。

首先建立一個(gè)自定義的消息 #define ? WM_SHOW ?WM_USER+1 。然后用消息映射宏命令BEGIN_MESSAGE_MAP，建立消息和消息處理函數(shù)之間的映射：

BEGIN_MESSAGE_MAP

VCL_MESSAGE_HANDLER（WM_SHOW， TMessage， TreeShow）;

END_MESSAGE_MAP（TForm）;

WM_SHOW 是消息常量，TMesage是接收消息的結(jié)構(gòu)，TreeShow是消息處理函數(shù)。在TreeShow函數(shù)中再調(diào)用畫圖函數(shù)：

void __fastcall TForm1：：TreeShow（ TMessage& msg）

{

if（Combtreename->Text=="紅黑樹"）

{

pView->NewViewPage（step，++sub_step）; //建立一個(gè)新的圖元文件

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

String S= （char*）（msg.LParam）; //接收傳遞來的變化信息字符串

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

}

}

然后在紅黑樹插入、刪除和修正函數(shù)中需要畫圖的位置插入SendMessage函數(shù)，發(fā)送畫圖指令：

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

String str=" 節(jié)點(diǎn)："+IntToStr（node->key）+" 插入";

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

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

SendMessage第一個(gè)參數(shù)是接收消息的窗體句柄，第二參數(shù)為自定義的消息號(hào)WM_SHOW，第三，四個(gè)參數(shù)分別是wParam， lParam，可以傳遞附加信息，把節(jié)點(diǎn)的變化細(xì)節(jié)信息寫入字符串str中，由lParam參數(shù)攜帶，隨消息一起傳送。消息通知模式使紅黑樹操作模塊與顯示模塊耦合度很低，可以很容易地?cái)U(kuò)展應(yīng)用到其他類型二叉樹的動(dòng)態(tài)演示上，以這種模式，還實(shí)現(xiàn)了AVL樹，最小堆等數(shù)據(jù)結(jié)構(gòu)的動(dòng)態(tài)演示。圖3～圖7展示了圖1中節(jié)點(diǎn)8的插入和修正細(xì)節(jié)，圖片全部由程序自動(dòng)生成。

5 結(jié)束語

應(yīng)用在內(nèi)存圖元文件上畫圖的方法，將紅黑樹插入，刪除操作時(shí)，各節(jié)點(diǎn)的變化過程以圖示方式顯示出來，直觀地展示了節(jié)點(diǎn)變化的每一步細(xì)節(jié)，便于我們深入學(xué)習(xí)和研究紅黑樹的構(gòu)造原理。采用類似的方法，還可以實(shí)現(xiàn)多種數(shù)據(jù)結(jié)構(gòu)建立過程的可視化，例如平衡二叉樹、B樹、二叉堆等。

參考文獻(xiàn)：

[1] Weiss M A.數(shù)據(jù)結(jié)構(gòu)與算法分析：C++語言描述[M]. 馮舜璽，譯.北京：電子工業(yè)出版社，2016.

[2] 馬博韜，孫鵬，朱小勇.紅黑樹算法研究綜述[J].網(wǎng)絡(luò)新媒體技術(shù)，2018，7（4）：56-62.

[3] 唐自立.一種新的刪除紅黑樹的結(jié)點(diǎn)的算法[J].計(jì)算機(jī)應(yīng)用與軟件，2006，23（1）：139-141.

[4] 李征宇，孫平，王鳳英.基于集合的紅黑樹結(jié)點(diǎn)刪除算法的實(shí)現(xiàn)[J].長春大學(xué)學(xué)報(bào)，2012，22（4）：426-428，436.

[5] 陳廣，伍德鵬.一種紅黑樹的改進(jìn)算法[J].內(nèi)蒙古師范大學(xué)學(xué)報(bào)（教育科學(xué)版），2012，25（12）：75-79.

[6] Petzold C.Windows程序設(shè)計(jì)[M].北京博彥科技發(fā)展有限公司，譯.北京：北京大學(xué)出版社，2009.

【通聯(lián)編輯：謝媛媛】