Algorithme itératif pour l'arbre rouge-noir

Quelqu'un peut-il me suggérer un pointeur vers un algorithme itératif pour l'insertion et la suppression dans un arbre rouge-noir? Tous les algorithmes disponibles dans .Net/C# sont basés sur la récursion, ce que je ne peux pas faire confiance pour manipuler un très grand nombre de données (d'où un grand nombre de profondeur de récursion pour l'insertion/suppression). Quelqu'un en a-t-il un basé sur l'itération?Algorithme itératif pour l'arbre rouge-noir

Note: Goletas.Collection utilise un algorithme itératif pour l'arbre AVL qui est très efficace pour un grand nombre de données, je veux aussi quelque chose de similaire pour Red-Black Tree.

Source

2010-09-21 Anindya Chatterjee

Depuis un arbre rouge-noir est équilibré, la hauteur d'un arbre avec des éléments 'N' est approximativement' log_2 (N) '(au plus' 2 * log_2 (N + 1) '). Par conséquent, les opérations récursives ne prendront pas autant de pas, même si votre structure est très grande. Bien sûr, vous n'avez pas précisé ce qu'est réellement "grand" (pourriez-vous clarifier cela?). En outre, avez-vous essayé d'utiliser une implémentation existante d'un arbre d'auto-équilibrage? Sinon, ce serait une perte de temps si vous commenciez à implémenter quelque chose qui n'est pas nécessaire pour commencer. –

Merci à tous pour vos précieux commentaires. Je viens de trouver un mais en VB6 et C. Je pense que c'est assez pour saisir l'idée. Voici les liens

quelqu'un Hope sera utile. :)

Source

2010-09-21 11:07:31

Les algorithmes basés sur l'arbre sont par nature récursifs.

Bien sûr, vous pouvez les réécrire pour être itératif, mais ce serait un exercice futile. Voici pourquoi:

Les arbres rouge-noir et les structures de données similaires sont auto-équilibrés et leur hauteur est logarithmique avec le nombre de valeurs stockées. Cela signifie que jamais atteindre le plafond de récursivité - cela nécessiterait que vous insérez ~ 2 éléments , ce qui n'arrivera tout simplement pas: votre ordinateur n'a pas assez de mémoire, et ne le sera jamais.

- Stick avec récursivité, c'est bien.

Source

2010-09-21 08:08:46

Oui, je suis d'accord avec vous, mais l'algorithme itératif ne prend-il pas beaucoup moins de temps que son homologue récursif?Je suis également préoccupé par le temps de réponse que j'ai oublié de mentionner. –

@Anindya, non, ce n'est pas le cas. –

@Anindya: Tout le contraire. La récursion repose sur la pile d'appels, qui est une structure de données de bas niveau ** très efficace. Si vous réécrivez l'algorithme de manière itérative, vous devez gérer votre propre pile, ce qui sera toujours moins efficace (au moins un niveau supplémentaire d'indirection de pointeur, plus les contrôles de bornes). La seule façon de rendre l'itération plus efficace que la récursion est quand vous pouvez vous débarrasser de la pile explicite (récursion de queue). La rumeur selon laquelle l'itération est plus rapide que la récursion n'est que cela: une rumeur. –

Il existe une version dans Introduction aux algorithmes par Thomas H Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein.

Le pseudo code est en ligne disponible au Google books (page 270).

Comme indiqué dans les commentaires, l'approche de la copie des données au noeud z au lieu de remplacer z par y en ligne 14/15 n'est pas optimale, surtout si vous avez des pointeurs vers les noeuds à un autre endroit. Ainsi, la ligne 13-16 peut être à la place:

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

Où replace_parent est défini comme (ce qui peut être utilisé pour la ligne 7-12 aussi):

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

Source

2012-07-04 11:33:06 schlamar

Il est à noter que leur noeud RBT supprimant le pseudo-code est dangereux car, au lieu de relier correctement un noeud, il ne fait que copier des données à partir d'un autre noeud. Voir la ligne 15 de RB-DELETE (T, z) à la page 288. –

@AlexeyFrunze Pourquoi est-ce dangereux? Et pouvez-vous expliquer ce qui devrait être fait à la place? – schlamar

Cela ne fonctionne pas bien avec les codes C et C++ pratiques. S'il existe des pointeurs/références à partir des données de noeud vers le noeud ou vers les données de noeud ailleurs, le code se brise car ils deviennent invalides. La solution consiste simplement à effectuer l'échange de noeuds prévu sans copier les données de noeud. Il vous suffit de réadapter correctement les nœuds aux autres nœuds. –

Algorithme itératif pour l'arbre rouge-noir

Répondre

Questions connexes