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

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

红黑树的高度

先证明高度是h的准红黑树至少有2「2h﹁+2﹂2h」-2个结点.再证明有n个结点的准红黑树的高度至多是2﹂log2(n+2)」+﹂log2(n+2lo)g-23﹂l-o1g2(n+2)」」-2.最后证明有n个结点的红黑树的高度至多是2﹂log2(n+2)」+﹂log2(n+2lo)g-23﹂l-og12(n+2)」」-2,该式比原来的2﹂log2(n+1)」+1准确.有n个结点的红黑树的高度在﹂log2(n+1)」和2﹂log2(n+2)」+﹂log2(n+2lo)g-23﹂l-og12(n+2)」」-2之间.此文进一步完善了红黑树的性质.