摘要
提出一种新的删除红黑树的结点的算法,其主要思想是先自上而下处理某些子树再删除结点,不涉及自下而上的后退。证明新算法是正确的。设 n 是红黑树的内部结点的个数。执行新算法时进行 O(1)次旋转。新算法的时间复杂性是 O(log_2n)。实验结果表明新算法的平均执行时间比 Tarjan 的算法和 Cuibas-sedgewick 算法的短。新算法的空间复杂性是 O(1)。
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 complexity of the new algorithm is O（log2n）. 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 ）.
出处
《计算机应用与软件》
CSCD
北大核心
2006年第1期139-141,共3页
Computer Applications and Software
关键词
红黑树
对称二叉B-树
2-3-4树
准红黑树
黑高度
结点
删除
旋转
Red-black tree Symmetric binary B-tree 2-3-4 tree Almost-red-black tree Black-height Node Deletion Rotation
