python - 如何在 Python 中为我的二叉树实现 OS-Rank() 函数？

Question

我正在尝试为我构建的二叉树实现 OS-Rank() 函数。 OS-Rank 使用树中较小节点的计数来标记节点，并将其存储在 node.size 中。这使得 OS-Select 能够在 O(nlgn) 时间内轻松选择第 i 个最小的节点。

这是伪代码:

OS-RANK(x)
    r = x.left.size + 1
    y = x
    while y != T.root
        if y == y.parent.right
            r = r + y.parent.left.size + 1
        y = y.parent
    return r

这是我的代码:

def osrank(self, root):
    r = 0
    if self.left != None:
        r = self.left.size + 1
    else:
        r += 1
    y = self
    while y != root:
        if y == y.parent.right:
            if y.parent.left != None:
                r = r + y.parent.left.size + 1
            else:
                r += 1
        y = y.parent
    self.size = r

没什么不同，只是我必须处理节点为空的情况。

但是，当我在插入 {5,2,7,1,6} 后打印出按顺序遍历时，我得到以下结果:

L L 1(1) U 2(1) U 5(1) R L 6(3) U 7(3) U U

(L/U/R描述遍历，括号中的数字是node.size，或者rank)。我想我期待这样的事情:

L L 1(1) U 2(2) U 5(5) R L 6(1) U 7(2) U U

有什么建议吗？

Answer 1

令人尴尬的是，我误解了 OS-Rank() 的用途。我认为它设置了每个节点的大小值，但看起来实际上是在插入时完成的。 OS-Rank() 使用该大小值返回节点的排名。

我保证不再凌晨 2 点编码!