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

李征宇，孙 平，王凤英

(沈阳建筑大学 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)要删除的结点有两个子结点，首先，找到这个结点的逻辑后继;然后，依此逻辑后继的数据覆盖要删除结点的数据;最后，删除逻辑后继。……