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

李征宇，孫 平，王鳳英

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

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

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

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

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

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

0 引言

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

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

(1)每個(gè)結(jié)點(diǎn)或者為黑色或者為紅色;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 基于集合的思想

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

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

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

4 結(jié)語

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

［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é)科基金資助項(xiàng)目(2009305)

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

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