李征宇，孫 平，王鳳英

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

基于集合的紅黑樹結(jié)點刪除算法的實現(xiàn)

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

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

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

紅黑樹;結(jié)點刪除算法;Transact-SQL

0 引言

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

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

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

(2)根結(jié)點為黑色;

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

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

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

1 紅黑樹結(jié)點刪除原理

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

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

(2)要刪除的結(jié)點有一個子結(jié)點，直接刪除之。若是根結(jié)點，則子結(jié)點變?yōu)楦Y(jié)點;否則，其父結(jié)點中對應(yīng)的孩子指針賦為被刪除結(jié)點的孩子的指針。

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

若最終刪除的結(jié)點是紅色的，則刪除成功，無須平衡調(diào)整;否則對于最終刪除結(jié)點的后繼者相關(guān)子樹進(jìn)行平衡調(diào)整。平衡調(diào)整具體情形如下:

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

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

(3)后繼者是黑色的，其兄弟結(jié)點是紅色的;調(diào)整方案:將其父兄結(jié)點旋轉(zhuǎn)，同時交換他們的顏色;后繼者結(jié)點不變;繼續(xù)調(diào)整。

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

2 基于集合的思想

在實際工作中，經(jīng)常存在樹形結(jié)點較多的情形或者出于數(shù)據(jù)統(tǒng)一管理的需要，樹形數(shù)據(jù)經(jīng)常存放在數(shù)據(jù)庫中。若按以往使用前臺代碼來處理樹形數(shù)據(jù)的策略，必然存在前臺頻繁和后臺交換數(shù)據(jù)，或者將大批量數(shù)據(jù)導(dǎo)入內(nèi)存的情形，勢必導(dǎo)致整個系統(tǒng)效率的降低。若在后臺數(shù)據(jù)庫中可以直接實現(xiàn)對紅黑樹結(jié)點的刪除，將大大的提升系統(tǒng)效率。Transact-SQL語言是基于集合思想的，對于批量數(shù)據(jù)的操作具有優(yōu)勢，另外在實現(xiàn)的細(xì)節(jié)上有別于一般的面向?qū)ο蟮某绦蜷_發(fā)語言。下面以SQL SERVER 2005為例，使用的T-SQL語言來實現(xiàn)紅黑樹的結(jié)點刪除算法。

3 紅黑樹結(jié)點刪除算法的實現(xiàn)

(2)簡單旋轉(zhuǎn)的實現(xiàn)，建立存儲過程simple_rotate，輸入?yún)?shù)為參與旋轉(zhuǎn)父子結(jié)點@parent_id和@child_id，完成左旋轉(zhuǎn)或者右旋轉(zhuǎn)。代碼如下:

4 結(jié)語

通過在后臺數(shù)據(jù)庫建立的紅黑樹結(jié)點刪除的存儲過程，開發(fā)人員可以方便的在前臺直接進(jìn)行調(diào)用，而不必在前臺程序中附加相應(yīng)的結(jié)點刪除的邏輯代碼，在提高了處理數(shù)據(jù)效率的同時，也更方便代碼的維護。

［1］嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)(C語言版)［M］.北京:清華大學(xué)出版社，1997.

［2］薩師煊，王珊.數(shù)據(jù)庫系統(tǒng)概論［M］.3版.北京:高等教育出版社，2000.

［3］高慶，姜凡.紅黑樹算法及其應(yīng)用［J］.軟件導(dǎo)刊，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

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

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

責(zé)任編輯:程艷艷