Tous les arbres rouges noirs sont équilibrés?

Question

Intuitivement, « arbres équilibrés » devrait être des arbres où la gauche et les sous-arbres à droite à chaque nœud doit avoir le numéro « à peu près le même » des noeuds.

Bien sûr, quand on parle d'arbres rouge-noir * (voir la définition à la fin) étant équilibrée, nous entendons réellement qu'ils sont hauteur équilibrés et en ce sens, ils sont équilibrés.

Supposons que nous essayons de formaliser l'intuition ci-dessus comme suit:

  

Définition: Binary Tree est appelée $ \ mu -balanced $, avec $ 0 \ le \ mu \ leq \ frac {1} {2} $, si pour chaque noeud $ N $, l'inégalité

     

$$ \ mu \ le \ frac {| N_L | + 1} {| N | + 1} \ le 1 - \ mu $$

     

détient et pour chaque \ $ mu \ gt \ mu $, il y a un noeud pour lequel ne l'énoncé ci-dessus. $ | N_L | $ est le nombre de nœuds dans le sous-arbre de $ N $ et $ gauche | N |. $ Est le nombre de nœuds sous l'arbre avec $ N $ en tant que root (y compris la racine)

Je crois, ce sont appelés poids équilibré arbres dans une partie de la littérature sur ce sujet.

On peut montrer que si un arbre binaire avec $ n noeuds $ est $ \ mu -balanced $ (pour une constante $ \ mu \ gt 0 $), la hauteur de l'arbre est $ \ mathcal {O} ( \ log n) $, maintenant ainsi les propriétés de recherche agréable.

La question est:

  

Y at-il quelque $ \ mu s gt 0 $ tel que chaque assez grand arbre rouge-noir est $ \ mu $ -balanced?

---

La définition des arbres rouge-noir que nous utilisons (de l'introduction aux algorithmes par Cormen et al):

Un arbre de recherche binaire, où chaque noeud est coloré en rouge ou en noir et

• La racine est noir
• Tous les nœuds NULL sont noirs
• Si un nœud est rouge, ses deux enfants sont noirs.
• Pour chaque nœud, tous les chemins de ce noeud aux noeuds NULL descendants ont le même nombre de noeuds noirs.

Note: on ne compte pas les noeuds NULL dans la définition de $ \ mu $ -balanced ci-dessus. (Même si je crois qu'il n'a pas d'importance si nous).

Answer 1

Claim :. Arbres rouges noirs peuvent être arbitrairement ONU- $ \ mu $ -balanced

Idée Preuve : Remplissez le sous-arbre droit avec autant de nœuds que possible et la gauche avec aussi peu de nœuds que possible pour un nombre donné $ k $ de nœuds noirs sur chaque trajet de feuille de base.

Preuve : Définir une séquence $ T_k $ des arbres rouge-noir de sorte que $ T_k $ a $ k $ noeuds noirs sur tous les chemins de la racine à une feuille (virtuelle). Définir $ T_k = B (L_k, r_k) $

• $ r_k $ l'arbre complet de taille 2k $ - $ 1 avec le premier, le troisième, ... niveau de couleur rouge, les autres noirs, et
• $ L_k $ l'arbre complet de taille $ k-1 $ avec tous les nœuds de couleur noire.

Il est clair que tous les T_k $ $ sont des arbres rouge-noir.

Par exemple, ceux-ci sont T_1 $ $ T_2 $ $ et $ T_3 $ , respectivement:

---

^{[ la source ]}

---

^{[ la source ]}

---

^{[ la source ]}

---

Vérifions l'impression visuelle de l'être du côté droit énorme par rapport à la gauche. Je ne vais pas compter les feuilles virtuelles; ils ne touchent pas le résultat.

Le sous-arbre gauche de $ T_k $ est terminée et a toujours la hauteur $ k-1 $ et contient donc 2 $ ^ k - 1 $ noeuds. Le sous-arbre droit, d'autre part, est complète et a une hauteur 2k $ - $ 1 et contient thusly 2 $ ^ {2k } -1 $ noeuds. Maintenant, la $ \ mu $ Valeur -balance pour la racine est

$ \ qquad \ displaystyle \ frac {2 ^ k} {2 ^ k + 2 ^ {2k}} = \ frac {1} {1 + 2 ^ k} \ underset {k \ to \ infty} {\} à 0 $

ce qui prouve qu'il n'y a pas $ \ mu> 0 $ comme demandé.

Answer 2

Non. Considérons un arbre rouge-noir avec la structure spéciale suivante.

• Le sous-arbre gauche est un arbre binaire complet avec la profondeur $ d $, dans lequel chaque nœud est noir.
• Le sous-arbre droit est un arbre binaire complet avec la profondeur 2d $ $, dans lequel chaque noeud en profondeur impair est rouge, et chaque nœud en profondeur même est noir.

Il est facile de vérifier que c'est un arbre rouge-noir valide. Mais le nombre de nœuds du sous-arbre droit (2 $ ^ {2d + 1} -1 $) est à peu près la carré du nombre de noeuds dans le sous-arbre gauche (2 $ ^ {d + 1} - 1 $).