Как реализовать функцию OS-Rank() для моего двоичного дерева в Python?

Question

Я пытаюсь реализовать функцию OS-Rank() для моего двоичного дерева, которое я построил. OS-Rank помечает узел с количеством меньших узлов из дерева и сохраняет его в node.size. Это позволяет OS-Select легко выбирать i-й наименьший узел за время O(nlgn).

Вот псевдокод:

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}, я получаю это:

LL 1 (1) U 2 (1) U 5 (1) RL 6 (3) U 7 (3) UU

(L / U / R описывает обходы, а число в скобках равно node.size или rank). Я думаю, что я ожидаю что-то вроде этого:

LL 1 (1) U 2 (2) U 5 (5) RL 6 (1) U 7 (2) UU

Любой совет?

Answer 1

Смущающе, я неправильно понял цель OS-Rank(). Я думал, что он устанавливает значение размера каждого узла, но, похоже, это действительно делается при вставке. OS-Rank() возвращает ранг узла, используя это значение размера.

Нет больше 2 утра кодирования, я обещаю!