| 一种新的删除红黑树的结点的算法 |
| |
| 引用本文： | 唐自立.一种新的删除红黑树的结点的算法[J].计算机应用与软件,2006,23(1):139-141. |
| |
| 作者姓名： | 唐自立 |
| |
| 作者单位： | 苏州大学计算机科学与技术学院,江苏,苏州,215006 |
| |
| 摘 要： | 提出一种新的删除红黑树的结点的算法，其主要思想是先自上而下处理某些子树再删除结点，不涉及自下而上的后退。证明新算法是正确的。设n是红黑树的内部结点的个数。执行新算法时进行O（1）次旋转。新算法的时间复杂性是O（log2n）。实验结果表明新算法的平均执行时间比Tarjan的算法和Guibas-Sedgewick算法的短。新算法的空间复杂性是O（1）。
|
| 关 键 词： | 红黑树 对称二叉B-树 2-3-4树 准红黑树 黑高度 结点 删除 旋转 |
| 收稿时间： | 05 17 2004 12:00AM |
| 修稿时间： | 2004-05-17 |
A NEW ALGORITHM FOR DELETING A NODE FROM A RED-BLACK TREE |
| |
| Tang Zili.A NEW ALGORITHM FOR DELETING A NODE FROM A RED-BLACK TREE[J].Computer Applications and Software,2006,23(1):139-141. |
| |
| Authors: | Tang Zili |
| |
| Affiliation: | School of Computer Science and Technology, Soochow University, Suzhou Jiangsu 215006, China |
| |
| Abstract: | A new algorithm for deleting a node from a red-black tree is presented,whose main idea is to process certain subtrees from above to below first and then to delete the node,without relating to the backtracking from below to above.The new algorithm is proved correct.Let n be the number of internal nodes of a red-black tree.O(1) rotations are performed during the execution of the new algorithm.The time com- plexity of the new algorithm is O(log_2n).Experimental results show that the average execution time of the new algorithm is shorter than that of both Tarjan's algorithm and the Guibas-Sedgewick algorithm.The space complexity of the new algorithm is O(1). |
| |
| Keywords: | Red-black tree Symmetric binary B-tree 2-3-4 tree Almost-red-black tree Black-height Node Deletion Rotation |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
