Lors de la conversion à un arbre rouge-noir, est-il raison de choisir une forme sur une autre?

Question

J'ai une bibliothèque de liste chaînée / méthodes d'arbres binaires à utiliser lorsque des conteneurs standards ne correspondent pas - par exemple quand il existe différents types de nœuds, ou quand je dois convertir arbre binaire à la liste et retour. Il inclut la gestion des arbres rouge-noir.

L'une des méthodes convertit à partir d'une liste double liée à un arbre binaire simple parfaitement équilibré dans le temps de O(n) (étant donné que le nombre d'éléments est connu à l'avance). L'algorithme est connu comme « pliage » - c'est la deuxième moitié d'un algorithme de rééquilibrage de l'arbre binaire qui a été une fois publié au Dr Dobbs. Les étapes sont essentiellement ...

• Compte tenu de la taille de l'arbre, décider de la taille des sous-arbres gauche et droit

• Recurse pour le sous-arbre gauche

• Pop un nœud dans la liste à utiliser comme racine

• Recurse pour le sous-arbre droit

• Lier les sous-arbres à la racine

J'ai aussi une méthode similaire qui crée un arbre rouge-noir. Le principe est le même, mais la récursion garde la trace de la hauteur du nœud - hauteur zéro nœuds sont créés rouge, tous les autres sont noirs. Le calcul de la hauteur de départ est basé sur le bit de jeu le plus élevé dans la taille des arbres et est tripoté de sorte qu'un arbre de taille (2^n)-1 parfaitement équilibré ne dispose que de nœuds noirs (la récursion ne va que jusqu'à la hauteur d'un).

Le point ici est que je n'ai que des nœuds rouges au niveau des feuilles, et un maximum de précision la moitié des noeuds sont rouges.

La chose est, tout cela est une façon simple de générer un arbre rouge-noir valide, il est pas la seule option. Éviter d'avoir toutes les feuilles rouges dans un arbre parfaitement équilibré était un choix arbitraire. Je puisse avoir des couches alternées de nœuds rouges et noirs. Ou je pourrais réduire le nombre de nœuds rouges considérablement dans certains cas, en repérant les sous-arbres qui sont parfaitement équilibrés et (si elle a besoin des noeuds rouges) rendant la racine de la place rouge de sous-arbre toutes ses feuilles.

La question est - est-il une raison pratique de choisir une forme d'arbre rouge-noir valide sur une autre

est pure curiosité - je sais que je n'ai aucune raison pratique - mais personne ne sait d'une application spécialisée où ce choix est significatif

Answer 1

Dans l'analyse standard du coût amorti de la modification des arbres rouge-noir selon la méthode de l'pysicist, les noeuds noirs avec zéro ou deux enfants rouges se voient attribuer un potentiel positif d'un, ce qui signifie qu'ils représentent des endroits problématiques dans l'arbre où supplémentaire le travail peut être fait. noeuds rouges et noirs avec des nœuds exactement un enfant rouge se voient attribuer un potentiel de zéro.

Donc, pour réduire le coût des modifications, donner à chaque noeud noir un enfant rouge.

---

raison pourquoi noeuds noirs avec un enfant rouge sont bénis est mieux expliqué par analogie avec les nombres binaires redondants. Je vais d'abord expliquer comment relier les arbres rouge-noir à des nombres binaires, puis je vais vous expliquer pourquoi les nœuds d'un rouge-enfant sont utiles.

Comme vous le savez, les arbres rouges-noirs sont une façon de représenter 2-4 arbres, dans lequel chaque chemin simple de la racine à une feuille a la même longueur, mais les noeuds ont 2, 3 ou 4 enfants. L'algorithme le plus simple pour ajouter ou supprimer un noeud dans un arbre 2-4 est le même algorithme que l'ajout ou la soustraction de l'une d'un nombre binaire redondant .

Un nombre binaire redondant est un nombre dans lequel le chiffre ième représente 2 ⁱ , tout comme dans un nombre binaire standard, mais le chiffre ième peut être 0, 1, ou 2 . Ils sont appelés redondants car il y a plusieurs façons d'écrire un nombre donné. 4 _décembre 100 peut être écrit ou 20 ou 12.

Pour ajouter un à un nombre binaire redondant, vous incrémenter le chiffre le moins significatif; si elle est 3, mis à 1 et augmenter le chiffre moins significatif suivant, et ainsi de suite. L'algorithme arrête lorsqu'il rencontre un 0 ou 1.

Pour ajouter une feuille à un arbre 2-4, ajouter un enfant à son parent prévu. Si le parent comment a cinq enfants, répartis en deux noeuds et les rendre les enfants de son parent. Continuez jusqu'à ce que vous atteignez un nœud qui n'a pas besoin fractionnement. Ainsi, le chemin vers la racine arrête quand il rencontre un nœud avec deux ou trois enfants.

Pour lié au coût amorti incrémenter un nombre binaire redondant, utilisez la méthode des physiciens et attribuer un potentiel de 1 à chaque 2 chiffres. Un incrément de xall ce qui touche k chiffres communiqués potentiel k-1, ce qui lui donne un coût amorti de O (1).

Cette analyse est similaire au coût amorti incrémenter un nombre binaire standard, mais un nombre binaire standard ne peut pas supporter à la fois augmenter et diminuer en O (1) Temps amorti: compte 2 ^k - 1. il est k 1 chiffres. Les coûts Increment Θ (k). Si cela est suivi d'un décrément, la paire coûte Θ (k) et porte le nombre à son ancien état.

binaire redondant est particulière en ce que 1 chiffres arrêtent les opérations en cascade de deux incrémentation et de décrémentation. 2-4 arbres sont spéciaux en ce que 3 nœuds arrêter les opérations en cascade à la fois insérer et supprimer.

Dans les arbres rouge-noir, un nœud avec un enfant rouge est juste une représentation d'un 3 nœuds dans un arbre 2-4. Ces noeuds sont spéciaux et robustes contre insérer ou de supprimer dans leurs sous-arbres, donc vous devriez les favoriser lors de la construction des arbres rouge-noir qui verra beaucoup de mises à jour.

Si vous savez que vous ne verrez que des inserts, favoriser les noeuds avec deux enfants noirs. Si vous savez que vous ne verrez que des effacements favoriser des nœuds avec deux enfants rouges.

Answer 2

La réponse courte est: il dépend

.

En gros, un arbre valide suffit. Cependant, en termes de amorti analyse - il pourrait très probablement être que vous voulez choisir la arbre le plus exact que dans le long terme vous donnera le comportement le plus optimisé.

par exemple. si vous choisissez toujours un arbre valide, mais qui est sujette à de nombreuses opérations d'équilibrage, vous obtiendrez une mauvaise performance amorti. Un exemple évident est un arbre entièrement noir, ce qui est tout à fait valable, mais effectue mauvais lorsqu'il est modifié.

Cela dépend, parce que ce sera généralement spécifique à l'application.