Итерационный алгоритм для красно-черного дерева - PullRequest
Новая
       10

Итерационный алгоритм для красно-черного дерева

3 голосов
/ 21 сентября 2010

Может кто-нибудь предложить мне какой-нибудь указатель на итеративный алгоритм для вставки и удаления в красно-черное дерево? Все алгоритмы, доступные в .Net / C #, основаны на рекурсии, которой я не могу доверять для обработки очень большого количества данных (отсюда большое количество глубины рекурсии для вставки / удаления). У кого-нибудь есть один, основанный на итерации?

Примечание: Goletas.Collection использует итерационный алгоритм для дерева AVL, который очень эффективен для большого количества данных, я хочу аналогичную вещь для Red-Black Tree.

Ответы [ 3 ]

6 голосов
/ 21 сентября 2010

Алгоритмы на основе дерева по своей природе рекурсивны.

Конечно, вы могли бы переписать их, чтобы они были итеративными, но это было бы бесполезным упражнением.Вот почему:

Красно-чёрные деревья и подобные структуры данных самоуравновешены , а их высота является логарифмической с количеством сохраненных значений.Это означает, что вы никогда не достигнете предела рекурсии - для этого потребуется вставить ~ 2 2000 элементов, чего просто не произойдет: на вашем компьютере недостаточно памятии никогда, никогда не будет.

- Придерживайся рекурсии, все в порядке.

2 голосов
/ 21 сентября 2010

Спасибо всем за ваши ценные комментарии. Я только что нашел, но в VB6 и C. Я думаю, этого достаточно, чтобы понять идею. Вот ссылки

  1. Статья
  2. C Источник
  3. Источник VB

Надеюсь, кто-нибудь найдет это полезным. :)

1 голос
/ 04 июля 2012

Есть версия в Введение в алгоритмы Томаса Х. Кормена, Чарльза Э. Лизерсона, Рональда Л. Ривеста, Клиффорда Стейна.

Псевдокод доступен в Интернете по адресу Google books (стр. 270).

Как указано в комментариях, подход копирования данных в узел z вместо замены z на y в строке 14/15 не оптимален, особенно если у вас есть указатели на узлы где-то еще , Таким образом, строка 13-16 может быть вместо: 

do_fixup = y.color == BLACK

if y is not z:
    replace_parent(tree, y, z)
    y.left = z.left
    y.left.parent = y
    y.right = z.right
    y.right.parent = y
    y.color = z.color

if do_fixup:
    ...

Где replace_parent определяется как (это можно использовать и для строки 7-12): 

def replace_parent(tree, a, b):
    a.parent = b.parent
    if not b.parent:
        tree.root = a
    else:
        if b is b.parent.left:
            b.parent.left = a
        else:
            b.parent.right = a
...