Imaginez un arbre rouge-noir. Y a-t-il toujours une séquence d'insertions et de suppressions qui la crée?

Supposons la définition suivante d'un arbre rouge-noir:

C'est un arbre de recherche binaire.
Chaque nœud est coloré en rouge ou en noir. La racine est noire.
Deux nœuds reliés par une arête ne peuvent pas être rouges en même temps.
Ici devrait être une bonne définition d'une feuille NIL, comme sur wiki. La feuille NIL est de couleur noire.
Un chemin d'accès de la racine à une feuille NIL contient le même nombre de nœuds noirs.

Question

Supposons que vous ayez implémenté les opérations insertet deletepour l'arborescence rouge-noir. Maintenant, si on vous donne un arbre rouge-noir valide, y a-t-il toujours une séquence d' opérations insertet deletequi le construit?

Motivation

Cette question est motivée par cette question et par la discussion de cette question .

Personnellement, je pense que si vous imaginez un arbre rouge-noir valide composé uniquement de nœuds noirs ( ce qui implique que vous imaginez un arbre parfaitement équilibré), il y a une séquence de insertet les deleteopérations qui le construit. cependant,

Je ne sais pas comment prouver avec précision
Je suis également intéressé par le cas plus général

data-structures search-trees balanced-search-trees Alisianoi
la source

Votre question semble un peu circulaire ... n'importe quel ensemble d'opérations d'insertion et de suppression construira un arbre rouge-noir ... littéralement n'importe quoi, puisque le rouge-noir n'est qu'une définition. Votre question est-elle limitée à un arbre purement noir?

JOX

Non, je pense que vous comprenez mal. Bien sûr, tout ensemble d'insertions et de suppressions construit un arbre rouge-noir. La question est la suivante: est-ce que tout arbre qui correspond à la définition peut être construit par une séquence d’insertions et de suppressions? Si on vous donne un arbre, pouvez-vous recréer une séquence d'insertions et de suppressions?

alisianoi

@ all3fox Oui, vous avez raison. Il existe un algorithme qui utilise l'opération insertet deleteconstruit un arbre rouge-noir valide composé uniquement de nœuds noirs . Il utilise insertions / suppressions pour créer un arbre de hauteur . Tout d'abord, nous pouvons créer un arbre parfaitement équilibré rouge-noir de manière très large en utilisant insertions, puis en utilisant des insertions et le même nombre de suppressions le repeindre en un arbre complètement noir. Le truc ici est de remonter fois la couche rouge la plus basse jusqu'à l'arbre jusqu'à la racine.

(h + 2) \cdot 2^{h} - 1

$(h + 2) \cdot 2^h - 1$

h

$h$

2^{h + 1} - 1

$2^{h+1} - 1$

h * 2^{h - 1}

$h * 2^{h-1}$

h

$h$

Anton Trunov

@AntonTrunov merci, je comprends cela. Qu'en est-il du cas d'un arbre général rouge-noir? Que pensez - vous, est - il possible de construire tout arbre rouge-noir avec donnée insertet les deleteopérations?

alisianoi

a) La réponse dépendra de la mise en œuvre précise de insertet delete; il peut y avoir plusieurs façons de faire ces opérations. b) Étant donné que les arbres RB sont essentiellement des arbres B d'ordre 4, on peut y trouver de l'inspiration. Les détails peuvent s'avérer délicats, car le mappage de RB vers B (et / ou vers l'arrière) n'est pas unique.

Raphaël

Réponses:

Les opérations d'insertion et de suppression dans une arborescence rouge-noir incluent l'équilibrage nécessaire au maintien des propriétés rouge-noir.

Le problème avec les arbres noirs rouges non penchés (à gauche ou à droite) est qu’il existe plusieurs façons de restaurer le rouge-noir après l’effacement ou l’insertion de base.
Ce ne sont pas les insertions ou les suppressions qui transforment l’arbre, mais le rééquilibrage et la rotation qui ont lieu par la suite pour préserver / restaurer la noirceur rouge de l’arbre.

La description de base de l’arbre rouge-noir ne prescrit pas les itinéraires possibles.
Il n'est peut-être pas possible de comprendre comment reconstruire exactement un arbre noir rouge donné, car le rééquilibrage n'a pas besoin d'être déterministe.

Ce problème a été résolu avec des arbres noirs et rouges à la gauche.
L'équilibrage est effectué d'une seule manière. Ainsi, tout arbre noir rouge incliné peut être reconstruit à l'aide d'insertions et de suppressions, car le rééquilibrage / les rotations sont effectués de manière déterministe spécifique.

Cela ne signifie pas que les arbres RB de gauche sont meilleurs ou plus efficaces, ce qu'ils gagnent d'une part en utilisant des règles d'équilibrage déterministes, ils perdent de l'autre en raison d'un code d'équilibrage plus complexe.

Selon le commentaire de @ Anton:
Il existe un algorithme qui utilise l'opération insert et delete pour construire un arbre rouge-noir valide composé uniquement de nœuds noirs. Il utilise insertions / suppressions pour créer un arbre de hauteur . Tout d'abord, nous pouvons créer un arbre parfaitement équilibré rouge-noir de manière large en utilisant insertions, puis en utilisant insertions et le même nombre de suppressions le repeindre en un arbre complètement noir. Le truc ici est de remonter fois la couche rouge la plus basse jusqu'à l'arbre jusqu'à la racine. $(h+2)⋅2^{h}−1$ $h$ $2^{h+1}−1$ $h∗2^{h-1}$ $h$

Je pense qu'un algorithme d'équilibrage complet comme Day-Stout-Warren serait plus efficace.

Johan
la source

En utilisant les opérations insertet à deletepartir du livre CLRS, vous pouvez créer une arborescence de dossiers valide, composée uniquement de nœuds noirs . L'astuce consiste à insérer plus de nœuds que nécessaire, puis à supprimer les nœuds en excès. L'algorithme va éliminer les nœuds rouges.

Anton Trunov

@AntonTrunov, avez-vous un lien pour cet algorithme, ce serait bien de l'inclure dans la réponse. Je ne le trouve pas avec mon google-fu.

Johan

Malheureusement, je n'ai pas de lien. J'ai essayé de répondre à la question à l'époque et j'ai mis au point un algorithme pour le cas particulier de tous les arbres RB noirs. Je l'ai en quelque sorte décrit dans ce commentaire, mais je n'ai pas fourni de preuve.

Anton Trunov

Qu'entendez-vous par "cela a été 'résolu" avec des arbres noirs rouges penchés à gauche. ". Même un arbre noir rouge incliné à gauche dispose de plusieurs méthodes pour stocker les mêmes éléments.

user239558