Tous les arbres rouge-noir ne sont pas équilibrés?

Intuitivement, les "arbres équilibrés" devraient être des arbres où les sous-arbres gauche et droit de chaque nœud doivent avoir "approximativement le même" nombre de nœuds.

Bien sûr, lorsque nous parlons d'équilibrage des arbres rouge-noir * (voir définition à la fin), nous voulons en fait dire qu'ils sont équilibrés en hauteur et en ce sens, ils sont équilibrés.

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

Définition: Un arbre binaire est appelé $\mu$ équilibré, avec $0 \le \mu \leq \frac{1}{2}$ , si pour chaque nœud$N$, l'inégalité

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

détient et pour chaque , il y a un nœud pour lequel l'instruction ci-dessus échoue. est le nombre de nœuds dans le sous-arbre gauche de etest le nombre de nœuds sous l'arbre avec comme racine (y compris la racine).| N L | N | N | $\mu' \gt \mu$$|N_L|$$N$$|N|$$N$

Je pense que ces arbres sont appelés arbres à poids équilibré dans certaines publications sur ce sujet.

On peut montrer que si un arbre binaire à $n$ nœuds est $\mu$ équilibré (pour une constante $\mu \gt 0$ ), alors la hauteur de l'arbre est $\mathcal{O}(\log n)$ , maintenant ainsi les belles propriétés de recherche.

La question est donc:

Existe-t-il des $\mu \gt 0$ tels que chaque arbre rouge-noir suffisamment grand soit équilibré en $\mu$ ?

La définition des arbres rouge-noir que nous utilisons (tirée de Introduction to Algorithms de Cormen et al):

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

• La racine est noire
• 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 allant de ce nœud aux nœuds NULL descendants ont le même nombre de nœuds noirs.

Remarque: nous ne comptons pas les nœuds NULL dans la définition de -balanced ci-dessus. (Même si je crois que cela n'a pas d'importance si nous le faisons).$\mu$

Allégation : les arbres rouge-noir peuvent être arbitrairement déséquilibrés en $\mu$ .

Idée de preuve : remplissez le sous-arbre droit avec autant de nœuds que possible et le gauche avec le moins de nœuds possible pour un nombre donné $k$ de nœuds noirs sur chaque chemin racine-feuille.

Preuve : Définissez une séquence $T_k$ d'arbres rouge-noir pour que $T_k$ ait $k$ nœuds noirs sur chaque chemin de la racine à n'importe quelle feuille (virtuelle). Définissez $T_k = B(L_k, R_k)$ avec

• $R_k$ l'arbre complet de hauteur$2k - 1$ avec le premier, le troisième, ... niveau de couleur rouge, les autres noirs, et
• $L_k$ l'arbre complet de hauteur$k-1$ avec tous les nœuds colorés en noir.

Clairement, tous les $T_k$ sont des arbres rouge-noir.

Par exemple, ce sont respectivement $T_1$ , $T_2$ et $T_3$ :

^{[ source ]}

^{[ source ]}

^{[ source ]}

Vérifions maintenant l'impression visuelle du côté droit étant énorme par rapport à la gauche. Je ne compterai pas les feuilles virtuelles; ils n'ont pas d'impact sur le résultat.

Le sous-arbre gauche de $T_k$ est complet et a toujours la hauteur $k-1$ et contient donc $2^k - 1$ nœuds. Le sous-arbre droit, en revanche, est complet et a une hauteur de$2k - 1$ et contient donc$2^{2k}-1$ nœuds. Maintenant, lavaleur d'équilibre$\mu$ pour la racine est

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

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

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

• Le sous-arbre gauche est un arbre binaire complet de profondeur , dans lequel chaque nœud est noir.$d$
• Le sous-arbre droit est un arbre binaire complet avec une profondeur de , dans lequel chaque nœud à une profondeur impaire est rouge et chaque nœud à une profondeur paire est noir.$2d$

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