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

楊勇

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

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

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

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

1 背景

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

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

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

3 圖元文件上繪制圖形

3.1 圖元文件

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

圖元文件的操作通過(guò)調(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類指針，指出圖元文件（長(zhǎng)方形）的大小，表達(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)用畫(huà)圖函數(shù)繪制圖形，要注意的是，由于參考設(shè)備句柄hdcRef設(shè)定為打印機(jī)的句柄，因此各種畫(huà)圖函數(shù)中傳入的坐標(biāo)應(yīng)為打印機(jī)的像素點(diǎn)坐標(biāo)。為了讓圖形適應(yīng)各種分辨率的屏幕或者打印機(jī)，畫(huà)圖函數(shù)的坐標(biāo)都應(yīng)以相對(duì)繪圖區(qū)域大小的比例值來(lái)設(shè)定。

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

3.2 將紅黑樹(shù)繪制在圖元文件上

紅黑樹(shù)的創(chuàng)建、插入、刪除寫在紅黑樹(shù)類RedBlackTree中。紅黑樹(shù)對(duì)象建立后，畫(huà)圖函數(shù)RBtreeShow將紅黑樹(shù)繪制在圖元文件上。畫(huà)圖函數(shù)RBtreeShow以遞歸后序遍歷的方式訪問(wèn)節(jié)點(diǎn)數(shù)據(jù)，每一個(gè)節(jié)點(diǎn)畫(huà)一個(gè)圓表示，圓內(nèi)是節(jié)點(diǎn)數(shù)據(jù)。節(jié)點(diǎn)顏色由圓的顏色代表，整個(gè)紅黑樹(shù)節(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ù)的繪制以繪制函數(shù)RBtreeShow的遞歸調(diào)用來(lái)完成，父子節(jié)點(diǎn)位置坐標(biāo)的關(guān)系在遞歸調(diào)用時(shí)以參數(shù)傳遞，函數(shù)偽代碼如下：

RBtreeShow （節(jié)點(diǎn)指針，畫(huà)布總寬度，節(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);

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

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

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

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

}

紅黑樹(shù)變化時(shí)將畫(huà)出多張圖元文件，為便于圖元文件的管理，設(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（）將圖元文件畫(huà)在Image的畫(huà)布上，Image則顯示于它的父窗體Panel上：

void ? TViewPage：：DrawPage（）

{

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

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

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

pImage->Visible = true; ? //畫(huà)完后，顯示圖片，設(shè)為false則可以隱藏圖片

}

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

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

首先建立一個(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)用畫(huà)圖函數(shù)：

void __fastcall TForm1：：TreeShow（ TMessage& msg）

{

if（Combtreename->Text=="紅黑樹(shù)"）

{

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

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

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

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

}

}

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

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

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ù)攜帶，隨消息一起傳送。消息通知模式使紅黑樹(shù)操作模塊與顯示模塊耦合度很低，可以很容易地?cái)U(kuò)展應(yīng)用到其他類型二叉樹(shù)的動(dòng)態(tài)演示上，以這種模式，還實(shí)現(xiàn)了AVL樹(shù)，最小堆等數(shù)據(jù)結(jié)構(gòu)的動(dòng)態(tài)演示。圖3～圖7展示了圖1中節(jié)點(diǎn)8的插入和修正細(xì)節(jié)，圖片全部由程序自動(dòng)生成。

5 結(jié)束語(yǔ)

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

參考文獻(xiàn)：

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

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

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

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

[5] 陳廣，伍德鵬.一種紅黑樹(shù)的改進(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)編輯：謝媛媛】