基于集合的红黑树结点删除算法的实现

李征宇，孙 平，王凤英

(沈阳建筑大学 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-)，女，吉林德惠人，讲师，硕士，主要从事数据结构、代数学方面的研究。

责任编辑:程艳艳