Algoritmo para iterativa Rojo-Negro Árbol

Question

Puede alguien por favor me sugiere ningún puntero a un algoritmo iterativo para la inserción y eliminación en un árbol Red-Negro? Todos los algoritmos disponibles en .Net / C # se basan en la recursión, que no puedo confiar para la manipulación de gran número de datos (por lo tanto gran número de nivel de recursividad para la inserción / eliminación). ¿Alguien tiene una basada en la iteración?

Nota:. Goletas.Collection utiliza un algoritmo iterativo para el árbol AVL, que es muy eficiente para la gran cantidad de datos, Quiero algo similar para el árbol Rojo-Negro también

Answer 1

Gracias a todos por sus valiosos comentarios. Acabo de encontrar uno, pero en VB6 y C. Creo que es suficiente para captar la idea. Aquí están los enlaces

1. artículo
2. C Fuente
3. VB Fuente

La esperanza alguien va a resultar útil. :)

Answer 2

algoritmos basados ??en árboles son, por su naturaleza recursiva muy.

Por supuesto que podría reescríbalos a ser iterativo, pero que sería un ejercicio inútil. He aquí por qué:

árboles rojo-negro y estructuras de datos similares son auto-equilibrada y su altura es logarítmica con el número de valores almacenados. Esto significa que no golpear el techo de la recursividad - esto requeriría que se inserta ~ 2 ²⁰⁰⁰ elementos, que simplemente no va a suceder: el equipo no tiene suficiente memoria, y nunca, nunca lo hará.

-. Seguir con la recursividad, está bien

Answer 3

Hay una versión en Introducción a los algoritmos por Thomas H Cormen, Charles E Leiserson, Ronald Rivest L, Clifford Stein.

El pseudo código está disponible en línea en Google (página 270).

Como señaló en los comentarios, el enfoque de copiar los datos a z nodo en lugar de sustituir z por y en línea 14/15 no es óptimo, especialmente si usted tiene punteros a los nodos en otro lugar. Así la línea 13-16 puede ser en su lugar:

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:
    ...

Donde replace_parent se define como (esto puede ser utilizado para la línea 7-12, también):

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