基于圖元文件實現紅黑樹插入刪除過程的動態演示

楊勇

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

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

中圖分類號：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.

【通聯編輯：謝媛媛】