Il semble que la définition sur wiki n'est pas précise:
7 Réponses :
Il est possible d'avoir un arbre noir rouge-noir qui a tous les nœuds noirs. De manière triviale, une rbtree avec un seul nœud, ou avec les seuls nœuds de feuilles étant des enfants directs de la racine, seront tous les nœuds de l'arrière.
La définition de RBTREE n'est donc pas stricte, comment définissez-vous votre exact rbtree?
@cpuer - Je ne comprends pas votre question. Un arbre à nœuds mono-nœud (une seule racine) doit être noir. Si la racine a des enfants qui sont des feuilles, ces feuilles doivent être noires. Ce ne sont que des nœuds d'intérieur qui peuvent finir par être rouge - plus précisément, chaque nœud que vous ajoutez est de couleur rouge, jusqu'à ce que vous déterminiez s'il doit être repeint.
Chaque nœud que vous ajoutez est de couleur rouge, jusqu'à ce que vous déterminiez s'il doit être repeint , pourquoi n'est-ce pas mentionné dans la page wiki?
@CPuer: C'est sous "Opérations: insertion".
Oui, mais la même chose n'est pas vraie pour un arbre noir noir avec tous les nœuds rouges. Un tel arbre est invalide. Il y a des restrictions sur lesquelles les nœuds doivent être noirs. Par exemple, les nœuds de feuilles doivent être noirs et les enfants d'un nœud rouge doivent être noirs.
Comment décidons-nous d'imprimer les enfants d'un nœud noir comme rouge ou noir?
Un arbre noir rouge est simplement une représentation binaire-arborescente d'un 2-3- 4 arbre . Tout nœud rouge dans un arbre noir rouge correspond à un morceau de son nœud parent dans l'arbre analageux 2-3-4. Par exemple: est une représentation de l'arborescence 2-3-4 si un arbre noir rouge a [3 | 5] dans le exemple) ou 4-nœuds. Notez que cela est essentiellement juste un arbre de recherche binaire simple.
Side-trivia: un noeud comme [3 | 5] n'est pas appelé un nœud 3 car il a 3 éléments (ce qu'il ne le fait pas), mais plutôt parce qu'il peut avoir trois enfants.
@ JTBANDES, comment décidons-nous d'imprimer des enfants d'un nœud noir comme rouge ou noir?
@CPuer: Si les enfants de nœud noir sont rouges, cela signifie qu'ils font réellement partie du même nœud 2-3-4. J'avais [rouge 3] car il est en fait [3 | 5] dans la version 2-3-4.
@ JTBANDES, votre version est totalement différente de la page Wiki, pourquoi n'est-il pas mentionné du tout?
Il est brièvement mentionné: "Pour chaque arbre de 2-4, il y a des arbres rouges-noirs correspondants avec des éléments de données dans le même ordre. Les opérations d'insertion et de suppression sur 2-4 arbres sont également équivalentes à la coloration et à la rotation en rouge arbres noirs. Cela fait de 2-4 arbres un outil important pour comprendre la logique derrière les arbres rouges, et c'est la raison pour laquelle de nombreux textes d'algorithme d'introduction introduisent 2-4 arbres juste avant les arbres rouges, même si 2-4 arbres ne sont pas souvent utilisé dans la pratique. " (Remarque Un arbre de 2-4 est identique à un arbre de 2-3-4)
C'est comme ça que je l'ai appris dans mon dernier semestre de classe informatique. Cela a plus de sens que d'essayer de se souvenir des règles des arbres noirs rouges.
@ JTBANDES, mais pratiquement, comment décidons-nous si les enfants d'un nœud noir doivent être rouges ou noirs ??
Lisez la section Opérations dans l'article Wikipedia.
@ JTBANDES, l'opération pour imprimer les enfants d'un nœud noir comme rouge ou noir ne peut pas être infercé à partir des 5 propriétés ci-dessus, non?
Oui, il peut théoriquement. Lorsque vous effectuez une insertion ou une suppression, vous devez simplement vous assurer que les propriétés sont toujours vraies. Qu'entendez-vous par «si vous souhaitez imprimer.»? Chaque nœud devrait connaître sa couleur.
@jtbandes, il me semble qu'il est toujours vrai si nous imprimons les enfants d'un nœud noir comme rouge ou noir.
@ JTBANDES, vous voulez donc vouloir utiliser rbtree, la couleur est déjà connue à l'avance? Nous devons donc simplement trouver une position pour insérer le nouveau nœud?
Non, la couleur du nouveau nœud dépend de l'endroit où vous l'insérez, et vous devez parfois changer la couleur des autres nœuds. La section Opérations de l'article et les autres réponses expliquent ici comment décider.
Pour répondre à la deuxième partie de la question, de décider d'imprimer un nœud comme rouge ou noir, que les informations sont stockées dans chaque nœud.
Dans un arbre de recherche binaire typique, chaque nœud contient une valeur, un pointeur gauche et un pointeur de droite (et peut-être un pointeur parent). Dans un arbre noir rouge, chaque nœud contient toutes ces choses plus un champ supplémentaire indiquant si ce nœud est rouge ou noir. Les différentes opérations de l'arborescence, telles que Insert ou Supprimer, sont alors responsables du maintien de ces informations de couleur de manière cohérente.
Vous ne recevriez jamais d'arbre non coloré et vous ne voudriez pas choisir des couleurs pour les nœuds (sauf peut-être comme des devoirs ou une question d'examen).
Pour amplifier, parce que je pense que c'est là que l'idée fausse de l'affiche d'origine est, les nœuds toujours ont une couleur, pas seulement au moment de l'impression. Ces couleurs peuvent changer dans le cadre des opérations Insert / Supprimer, mais une couleur de nœud est toujours rouge ou noire. Les rouges et les noirs noirs ne sont pas seulement cosmétiques, ils font partie intégrante de la manière dont la structure de données conserve ses propriétés de la balance.
Oui Un arbre avec tous les nœuds noirs peut être un arbre noir rouge. On peut prouver que un tel arbre doit être un arbre complètement rempli afin de préserver la propriété de profondeur noire égale.
Vous pouvez vous-même prouver qu'un arbre avec tous les nœuds noirs peut être un arbre noir rouge en battue un petit arbre de ce genre.
Par exemple: Cet arborescence a tous les nœuds noirs et satisfait toutes les conditions. Supposons que la racine a nul comme son parent et les deux nœuds de feuilles ont à la fois leurs enfants comme nil.hope cela aide.
Voici un exemple pour montrer que tous les nœuds d'un arbre noir rouge sont noirs:
Premièrement, insert {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} dans l'ordre croissant dans l'arbre noir noir. Ensuite, supprimez {10, 9, 8} dans l'ordre décroissant de l'arbre noir rouge.
Enfin, tous les nœuds de cet arbre noir sont noirs.
Un arbre noir rouge dont les nœuds sont tous noirs sont identiques à ceux de l'arbre B (m = 4) dont les nœuds n'ont que une seule touche.
Cela donne une procédure concrète pour construire des arbres noirs rouges de tous les nœuds noirs. +1