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

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

это работает по большей части. но мне нужно реализовать быструю функцию (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. # Nodeswithkeyhigher (key)).


rank algorithm red-black-tree
person timwaagh    schedule 28.06.2012    source источник

Ответы (1)


arrow_upward
0
arrow_downward

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

tl; dr: перейти к последнему абзацу

Это та же проблема, с которой у меня проблемы. (Да и DS). Пока все прогоны, кроме 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 (узел, ранг которого вы хотите присвоить). Это неправильно вернуло бы нас на несколько рангов.

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

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

person Kevin A    schedule 28.06.2012
comment
о ... спасибо ... это полезно ... ну, тогда мне лучше заняться липким ... похоже, я упускаю что-то потенциально выгодное. - person timwaagh; 29.06.2012
comment
каким-то образом мой волшебным образом перебрался через забор за 18 минут до крайнего срока, хотя у него все еще были недостатки, которых должно было быть достаточно, чтобы он потерпел неудачу. что означает, что ты и Липкий только что спасли мою задницу. Я чертовски благодарен. - person timwaagh; 30.06.2012