Нахождение ранга в красно-черном дереве без использования родительского указателя - PullRequest
Новая
       30

Нахождение ранга в красно-черном дереве без использования родительского указателя

0 голосов
/ 01 декабря 2011

Мне дали код для красно-черного дерева в классе. Структура, используемая для создания узла, не имеет родительского указателя. У меня большая часть моего проекта работает, но я не могу понять, как вычислить рейтинг за O (LG N) времени. Под рангом я подразумеваю, что если вы выполните обход по порядку и сохраните ключи в массиве, начиная с индекса 1, то в каком индексе будет храниться данный ключ. Выполнение этого будет за O (n) время, что недопустимо.

Читая через CLRS, глава Дополнение структур данных содержит код для возврата ранга по данному ключу. Это именно то, что мне нужно, но проблема в том, что код использует родительский указатель. Так как мы никогда не использовали родительские указатели ни в одном из наших примеров красно-черного дерева, и этот код не включает родительский указатель, я не верю, что мы должны изменить весь данный код просто для того, чтобы получить ранг для работы, что приводит меня к считаю, что есть способ сделать это без использования родительского указателя.

(Поля?), Которые существуют в структуре узла: ключ (int), указатель на левый дочерний элемент, указатель на правый дочерний элемент, размер поддерева (int) и цвет (int).

Весь код написан на C. То, что я ищу, это то, возможно ли это, и как я могу выполнить это с исходным кодом или без него (хорошее объяснение было бы идеально).

1 Ответ

1 голос
/ 01 декабря 2011

Допущение: размер поддерева включает корневой узел поддерева.Вызовите заказываемое значение в.

Затем этот алгоритм получает ранг в O (lgn): 

1: let rank=subtree size(root of tree)
2: if you go left:
- adjust rank=rank - (subtree size(sts) of right child (rc) of root) - 1
- move to left child(lc) of root
3: if you go right:
- adjust rank=rank(prior)
- move to rc(root)
4: iterate 2-3 (replacing root with current node) until you are at the node with value a
5: if this node has a rc, adjust a final time
- rank = rank - (sts(rc))

Готово.

Примечание: предполагается, чтообычное слева направо нижнее-высшее упорядочение дерева рб.

...