一种新的删除红黑树的结点的算法

• 作者: 唐自立
• 来源期刊: 计算机应用与软件
• 学科: 工学
• 关键词: 红黑树 对称二叉B-树 2-3-4树 准红黑树 黑高度 结点 删除 旋转
• 年，卷（期）: 2006,（1）
• 所属期刊栏目: 信息技术交流
• 页码范围: 139-141
• 页数: 3页
• 分类号: TP3
• 字数: 3784字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-386X.2006.01.052

摘要

提出一种新的删除红黑树的结点的算法,其主要思想是先自上而下处理某些子树再删除结点,不涉及自下而上的后退.证明新算法是正确的.设n是红黑树的内部结点的个数.执行新算法时进行O(1)次旋转.新算法的时间复杂性是O(log2n).实验结果表明新算法的平均执行时间比Tarjan的算法和Guibas-Sedgewick算法的短.新算法的空间复杂性是O(1).

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	唐自立	苏州大学计算机科学与技术学院	13	66	5.0	8.0