Colorez un arbre binaire pour être un arbre rouge-noir

Une question d'entretien courante consiste à fournir un algorithme pour déterminer si un arbre binaire donné est équilibré en hauteur (définition de l'arbre AVL).

Je me demandais si nous pouvions faire quelque chose de similaire avec les arbres rouges-noirs.

Étant donné un arbre binaire non coloré arbitraire (avec des nœuds NULL), existe-t-il un algorithme "rapide" qui peut déterminer si nous pouvons colorer (et trouver une coloration) les nœuds Rouge / Noir afin qu'ils satisfassent toutes les propriétés d'un arbre Rouge-Noir (définition comme dans cette question )?

Une pensée initiale était que nous pouvons simplement supprimer les nœuds NULL et essayer de vérifier récursivement si l'arbre résultant peut être un arbre rouge-noir, mais cela ne semble aller nulle part.

J'ai fait (une brève) recherche sur le Web des articles, mais je n'ai pas pu en trouver qui semblent résoudre ce problème.

Il est possible que je manque quelque chose de simple.

algorithms data-structures binary-trees search-trees Aryabhata
la source

Je suis presque sûr qu'un arbre peut être de couleur rouge-noir si pour chaque nœud, le chemin le plus long de celui-ci vers un nœud NULL n'est pas plus de deux fois plus long que le plus court. Est-ce assez rapide?

Karolis Juodelė

Réponses:

Si pour chaque nœud d'un arbre, le chemin le plus long de celui-ci vers un nœud feuille n'est pas plus de deux fois plus long que le plus court, l'arbre a une coloration rouge-noir.

Voici un algorithme pour déterminer la couleur de n'importe quel nœud n

if n is root,
    n.color = black
    n.black-quota = height n / 2, rounded up.

else if n.parent is red,
    n.color = black
    n.black-quota = n.parent.black-quota.

else (n.parent is black)
    if n.min-height < n.parent.black-quota, then
        error "shortest path was too short"
    else if n.min-height = n.parent.black-quota then
        n.color = black
    else (n.min-height > n.parent.black-quota)
        n.color = red
    either way,
        n.black-quota = n.parent.black-quota - 1

Voici n.black-quotale nombre de nœuds noirs que vous vous attendez à voir aller à une feuille, à partir du nœud net n.min-heightla distance à la feuille la plus proche.

Par souci de concision, notons , et . $b(n) =$ n.black-quota $h(n) =$ n.height $m(n) =$ n.min-height

Théorème: Correction d' un arbre binaire . Si pour chaque nœud , et pour le nœud , $T$ $n \in T$ $h(n) \leq 2m(n)$ $r = \text{root}(T)$ puisa une coloration rouge-noir avec exactementnoeuds noirs sur chaque chemin de la racine à la feuille. $b(r) \in [\frac{1}{2}h(r), m(r)]$ $T$ $b(r)$

Preuve: induction sur . $b(n)$

Vérifiez que les quatre arbres de hauteur un ou deux satisfont au théorème avec . $b(n) = 1$

Par définition d'arbre rouge-noir, la racine est noire. Soit un nœud avec un parent noir tel que $n$ $p$ . Alors,et. $b(p) \in [\frac{1}{2}h(p), m(p)]$ $b(n) = b(p) -1$ $h(n) = h(p)-1$ $h(n) \geq m(n) \geq m(p)-1$

Supposons que le théorème s'applique à tous les arbres dont la racine , . $r$ $b(r) < b(q)$

Si , alors peut être coloré en rouge-noir par l'hypothèse inductive. $b(n) = m(n)$ $n$

Si puis $b(p) = \frac{1}{2}h(p)$ . ne satisfait pas l'hypothèse inductive et doit donc être rouge. Soitun enfant de. et $b(n) = \lceil \frac{1}{2}h(n) \rceil - 1$ $n$ $c$ $n$ $h(c) = h(p)-2$ . Alorspeut être coloré en rouge-noir par l'hypothèse inductive. $b(c) = b(p)-1 = \frac{1}{2}h(p)-1 = \frac{1}{2}h(c)$ $c$

Notons que, par le même raisonnement, si , alorset un enfant desatisfont tous deux à l'hypothèse inductive. Par conséquent,pourrait avoir n'importe quelle couleur. $b(n) \in (\frac{1}{2}h(r), m(r))$ $n$ $n$ $n$

Karolis Juodelė
la source

@Aryabhata, tout parcours est correct, tant que le parent est vu avant ses enfants. Je n'ai pas de preuve formelle écrite, mais j'ai une idée de son apparence. J'essaierai d'écrire quelque chose quand je pourrai.

Karolis Juodelė

@Aryabhata, j'ai ajouté une preuve. Désolé j'ai mis beaucoup de temps.

Karolis Juodelė

@Aryabhata, l'idée est que si

d'un nœud

respecte certaines limites, un enfant ou un petit-enfant

peut avoir

dans ces mêmes limites. Avoir

dans ces bornes peut correspondre à

étant noir. La plupart des preuves portent sur la délimitation de

d'un enfant ou d'un petit-enfant, étant donné

du parent ou du grand-parent. Votre arbre est certainement colorable.

b (p)

$b(p)$

p

$p$

c

$c$

p

$p$

b (c)

$b(c)$

b (n)

$b(n)$

n

$n$

h

$h$

m

$m$

h

$h$

m

$m$

, l'enfant gauche est noir et l'enfant droit est rouge, le chemin de longueur 16 est

, le chemin de longueur 8 est

, les chemins de 9 et 12 peuvent avoir plusieurs colorations valides.

b (r o o t) = 8

$b(root) = 8$

b r b r b r \dots

$brbrbr\dots$

b b b b b b b b

$bbbbbbbb$

Karolis Juodelė

Il y a une question à propos de cette réponse .

David Richerby

Je crois que la réponse de Karolis est correcte (et une caractérisation assez agréable des arbres rouge-noir, donnant un algorithme de temps ), je voulais juste ajouter une autre réponse possible. $O(n)$

Une approche consiste à utiliser la programmation dynamique.

$n$ $S_R(n)$ $S_B(n)$ $n$ $S_R(n)$ $n$ $S_B(n)$ $n$

$n.Left$ $n.Right$ (i.e direct children of $n$ ), we can compute the corresponding sets for $n$ , by taking appropriate intersections and unions (and incrementing as needed).

I believe this comes out be an $O(n \log n)$ time algorithm.

Aryabhata
la source