基于集合的紅黑樹結點刪除算法的實現

李征宇，孫 平，王鳳英

(沈陽建筑大學 a.信息學院; b.理學院，沈陽 110168)

基于集合的紅黑樹結點刪除算法的實現

李征宇a，孫 平b，王鳳英a

(沈陽建筑大學 a.信息學院; b.理學院，沈陽 110168)

通過分析紅黑樹的定義和結點刪除算法的具體步驟及實現細節，針對實際應用中存在的運用前臺邏輯刪除結點效率低下的問題，采用直接在后臺實現刪除操作來提高效率;并以面向集合的Transact-SQL語言為工具，在SQL SERVER 2005數據庫上實現了紅黑樹結點刪除算法。

紅黑樹;結點刪除算法;Transact-SQL

0 引言

紅黑樹即對稱二叉B-樹和2-3-4樹，紅黑樹是由Bayer在1972年提出來的。

定義 滿足下述性質的二叉搜索樹稱為紅黑樹:

(1)每個結點或者為黑色或者為紅色;

(2)根結點為黑色;

(3)每個葉結點也即NULL指針都是黑色的;

(4)若某個結點是紅色的，那么它的兩個子結點均是黑色的;

(5)任意結點到其所有子孫葉結點的路徑所包含的黑結點數量必須相等。

1 紅黑樹結點刪除原理

紅黑樹結點刪除分兩步走:首先，按照二叉搜索樹的刪除操作刪除結點;然后，對于最終刪除結點的后繼者相關的子樹進行平衡調整。二叉搜索樹的刪除操作可分成三種情況:

(1)要刪除的結點沒有子結點，直接刪除之。若是根結點，則此樹變空樹;否則，將其父結點中對應的孩子指針賦為NULL。

(2)要刪除的結點有一個子結點，直接刪除之。若是根結點，則子結點變為根結點;否則，其父結點中對應的孩子指針賦為被刪除結點的孩子的指針。

(3)要刪除的結點有兩個子結點，首先，找到這個結點的邏輯后繼;然后，依此邏輯后繼的數據覆蓋要刪除結點的數據;最后，刪除邏輯后繼。

若最終刪除的結點是紅色的，則刪除成功，無須平衡調整;否則對于最終刪除結點的后繼者相關子樹進行平衡調整。平衡調整具體情形如下:

(1)后繼者是紅色的，或者它是樹的根，或者兼而有之;調整方案:將后繼者染成黑色，平衡調整完畢。

(2)后繼者是黑色的，其兄弟結點以及兩個侄子結點都是黑色的;調整方案:將其兄弟結點染成紅色，將其父結點作為新的后繼者，繼續調整。

(3)后繼者是黑色的，其兄弟結點是紅色的;調整方案:將其父兄結點旋轉，同時交換他們的顏色;后繼者結點不變;繼續調整。

(4)后繼者是黑色的，其兄弟結點是黑色的，并至少有一個侄子結點是紅色的;調整方案:若存在遠紅侄的情形，旋轉后繼者的父兄結點，并交換他們的顏色同時遠紅侄變黑，平衡調整完畢。若只存在近紅侄的情形，旋轉近紅侄和其父結點，并交換他們的顏色，變成遠紅侄的情形;繼續調整。

2 基于集合的思想

在實際工作中，經常存在樹形結點較多的情形或者出于數據統一管理的需要，樹形數據經常存放在數據庫中。若按以往使用前臺代碼來處理樹形數據的策略，必然存在前臺頻繁和后臺交換數據，或者將大批量數據導入內存的情形，勢必導致整個系統效率的降低。若在后臺數據庫中可以直接實現對紅黑樹結點的刪除，將大大的提升系統效率。Transact-SQL語言是基于集合思想的，對于批量數據的操作具有優勢，另外在實現的細節上有別于一般的面向對象的程序開發語言。下面以SQL SERVER 2005為例，使用的T-SQL語言來實現紅黑樹的結點刪除算法。

3 紅黑樹結點刪除算法的實現

(2)簡單旋轉的實現，建立存儲過程simple_rotate，輸入參數為參與旋轉父子結點@parent_id和@child_id，完成左旋轉或者右旋轉。代碼如下:

4 結語

通過在后臺數據庫建立的紅黑樹結點刪除的存儲過程，開發人員可以方便的在前臺直接進行調用，而不必在前臺程序中附加相應的結點刪除的邏輯代碼，在提高了處理數據效率的同時，也更方便代碼的維護。

［1］嚴蔚敏，吳偉民.數據結構(C語言版)［M］.北京:清華大學出版社，1997.

［2］薩師煊，王珊.數據庫系統概論［M］.3版.北京:高等教育出版社，2000.

［3］高慶，姜凡.紅黑樹算法及其應用［J］.軟件導刊，2008(9):40－41.

Implement of Set-based Node Deletion Algorithm of Red-black Tree

LI Zheng-yua，SUN Pingb，WANG Feng-yinga

(a.College of Information;b.College of Science，Shenyang Jianzhu University，Shenyang 110168，China)

Through analyzing the definition of red-black tree，concrete steps of node deletion algorithm and implement details，this paper puts forward an idea of improving efficiency by direct deletion operation in background to solve the problem that it is inefficient to delete in foreground in practical application.By set-oriented Transact-SQL language，it implements the node deletion algorithm of redblack tree in SQL SERVER 2005 database.

red-black tree;node deletion algorithm;Transact-SQL

TP312

A

1009－3907(2012)04－0426－03

2012-02-18

沈陽建筑大學基礎學科基金資助項目(2009305)

李征宇(1980-)，男，江蘇無錫人，講師，碩士，主要從事數據庫、數據結構方面研究;孫平(1980-)，女，吉林德惠人，講師，碩士，主要從事數據結構、代數學方面的研究。

責任編輯:程艷艷