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

楊勇

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

關鍵詞：紅黑樹;圖元文件;平衡二叉樹

中圖分類號：TP311.11 ? ? ?文獻標識碼：A

文章編號：1009-3044（2021）35-0166-03

1 背景

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

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

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

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

3 圖元文件上繪制圖形

3.1 圖元文件

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

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

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

[圖像的像素點大小屏幕每英寸像素點數×25.4*100]（1英寸=25.4毫米）

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

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

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

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

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

節(jié)點左兒子橫坐標=[節(jié)點坐標分子*2-1節(jié)點坐標分母*2-1L]

節(jié)點右兒子橫坐標=[節(jié)點坐標分子*2節(jié)點坐標分母*2-1L]

整個紅黑樹的繪制以繪制函數RBtreeShow的遞歸調用來完成，父子節(jié)點位置坐標的關系在遞歸調用時以參數傳遞，函數偽代碼如下：

RBtreeShow （節(jié)點指針，畫布總寬度，節(jié)點坐標分子，節(jié)點坐標分母，節(jié)點縱坐標）

{

計算當前節(jié)點坐標

計算左兒子節(jié)點坐標;

計算右兒子節(jié)點坐標;

如果有左兒子，畫左連接線，遞歸調用RBtreeShow;

如果有右兒子，畫右連接線，遞歸調用RBtreeShow;

在當前節(jié)點坐標處輸出節(jié)點數據;

根據節(jié)點顏色，在節(jié)點數據上畫圓;

}

紅黑樹變化時將畫出多張圖元文件，為便于圖元文件的管理，設計了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上畫圖的優(yōu)勢是，可以通過控制Image的屬性Visible將圖片顯示或隱藏，從而可以交替顯示不同的圖片，將紅黑樹的變化過程動態(tài)展示出來。TViewPage中的成員num和sub_num 則記錄圖片的主序號和子序號，對同一個節(jié)點操作的所有圖片主序號num相同，操作細節(jié)過程圖片以子序號sub_num區(qū)別。

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

4 紅黑樹節(jié)點插入過程動態(tài)演示

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

首先建立一個自定義的消息 #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函數，發(fā)送畫圖指令：

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

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

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

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

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

5 結束語

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

參考文獻：

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

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

[3] 唐自立.一種新的刪除紅黑樹的結點的算法[J].計算機應用與軟件，2006，23（1）：139-141.

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

[5] 陳廣，伍德鵬.一種紅黑樹的改進算法[J].內蒙古師范大學學報（教育科學版），2012，25（12）：75-79.

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

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