Функция альтернативного ранга RBTree (красное черное дерево)

Question

У меня есть статистика, дополненная красно-черным деревом.

это работает по большей части. но мне нужно реализовать быструю функцию (O(LG N)), которая в основном возвращает место узла в отсортированном порядке. как функция OS-rank из моего учебника. но с одним поворотом: возвращаемое значение, если два узла имеют одинаковую оценку, должно быть одинаковым. здесь - функция os-rank (в псевдокоде для данного узла x, где root - корень дерева).

OS-Rank(x)
r=x.left.size+1
y=x
while y!=root
  if y==y.p.right
    r+=y.p.left.size+1
y=y.p
return r

Но: то, что мне нужно, это то, где, если A имеет ключ 1, а узел B имеет ключ 1, функция возвращает 1 для обоих. и так далее. Я попробовал себя с чем-то вроде этого.

rank(x)
start with value r=1
check that x.right is not Nil
  case x.right has the same key as x
    add x.right.#nodeswithkeyhigher(x.key) to r
  other cases: add x.right.size to r
y=x
while y != root
  if y.parent.left == y
    case y.parent.right.key>x.key
      add y.parent.right to r
    other cases
      add y.parent.right.#nodeswithkeyhigher(x.key) to r
  y=y.parent
return r

Угадайте, что: тестовый случай не удался. Я хотел бы знать, является ли это правильным способом выполнения действий, или, возможно, я допустил какую-то ошибку, которую не вижу (в противном случае ошибка в функции Node.# Nodewithkeyhigher(key)).

Answer 1

Редактировать: последний абзац для ответа, спасибо Sticky.

tl; dr: пропустить до последних параграфов

Это та же проблема, с которой у меня проблемы. (Да, ДС, а также). Пока что все трассы, кроме 5, правильные. Я протестировал несколько вещей, одна из которых очень проста: просто поменяйте местами влево и вправо в OSRank. В некоторых случаях это дало правильный ответ, но в более тяжелых случаях это было совсем немного. О, я также добавил, что если y.score == y.parent.score, я добавляю только правильный размер y.parent, если нет, я добавляю правильный размер + 1.

public int OSRank(Node x)
    {
        int r = x.Right.Size + 1;
        Node y = x;
        while (y != root)
        {
            if (y == y.Parent.Left)
            {
                if (y.Score == y.Parent.Score)
                    r = r + y.Parent.Right.Size;
                else
                    r = r + y.Parent.Right.Size + 1;
            }
            y = y.Parent;
        }
        return r;
    }

Давайте сначала проверим этот метод на дереве на странице 340 (рисунок 14.1). Мы будем искать ранг 38 (который должен вернуть 4, потому что 39, 47 и 41 выше):

1. r = 1 + 1 = 2 // Правая сторона + 1
2. r = 2 // ничего не происходит, потому что мы правильный ребенок
3. r = r + 1 + 1 = 4 // мы левый ребенок, ключ нашего родителя больше и parent.Right.size = 1
4. r = 4 // ничего не происходит, потому что мы правильный ребенок

Так что в этом случае результат верный. Но что, если мы добавим еще один узел с ключом 38 в наше дерево? Это немного меняет наше дерево, теперь правая часть узла 26 выглядит так:

(Я не могу добавлять изображения, так что смотрите здесь:http://i47.tinypic.com/358ynhh.png)

Если бы мы использовали тот же алгоритм, мы получили бы следующий результат (выбрав красный):

1. r = 0 + 1 = 1 // нет правой стороны
2. r = 1 // мы правильный ребенок
3. r = 1 // мы правильный ребенок
4. r = 1 + 3 + 1 = 5 // Размер 3 равен размеру узла 41.
5. r = 5 // мы правильный ребенок

Хотя мы ожидаем 4 место здесь. Пока я печатал это, я заметил, что мы проверяем y.Score == y.Parent.Score, но я полностью забыл y изменения. Таким образом, в строке 4 предложение "y.Score == y.Parent.Score" было ложным, поскольку мы сравнили узел 30 с 38. Поэтому, если мы изменим эту строку на:

if (x.Score == y.Parent.Score)

Алгоритм выводит ранг 4, что правильно. Это означает, что мы устранили еще одну проблему. Но есть и другие, которые я тоже не понял:

• Случай, в котором Y.Parent.Right содержит дубликаты ключей. Технически, если у нас есть 3 узла с одинаковым ключом, они должны учитываться как 1.
• Случай, в котором Y.Parent.Right содержит ключи, равные x.Key (узел, для которого вы хотите получить ранг). Это вернуло бы нас на несколько позиций назад, неправильно.

Я полагаю, вы могли бы сохранить другое целое число, которое содержит количество узлов с более высоким счетом. После вставки вы можете взобраться на дерево и скорректировать значения, если поддерево этого узла не содержит узел с таким же счетом. Но как это сделать (и эффективно) мне сейчас неизвестно.

редактирование: сначала найдите окончательного преемника х с тем же счетом х. Затем рассчитайте ранг нормальным способом. Код выше работает.