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

Question

我正在为我构建的二叉树实现一个叫做OS-Rank()的功能。OS-Rank的作用是给树中的每个节点标记一个数字，这个数字表示比这个节点小的节点数量，并把这个数字存储在节点的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表示遍历的方向，括号里的数字是节点的size，也就是排名。

我原本期待的结果是这样的：

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()是通过这个大小值来返回一个节点的排名。

我保证以后不再凌晨两点写代码了！