Discussion:Arbre bicolore

Lien externe mort

Bonjour,

Pendant plusieurs vérifications automatiques, un lien était indisponible. Merci de vérifier si il est bien indisponible et de le remplacer par une version archivée par Internet Archive si c'est le cas. Vous pouvez avoir plus d'informations sur la manière de faire ceci ici. Merci également de vérifier que d'autres liens de l'article ne sont pas morts. Les erreurs rapportées sont :

• http://webpages.ull.es/users/jriera/Docencia/AVL/AVL%20tree%20applet.htm
  • Dans Arbre rouge-noir, le Fri Jan 20 20:57:22 2006, Socket Error: (113, "Aucun chemin d'acc\xc3\xa8s pour atteindre l'h\xc3\xb4te cible")
  • Dans Arbre rouge-noir, le Sat Jan 21 10:29:47 2006, Socket Error: (113, "Aucun chemin d'acc\xc3\xa8s pour atteindre l'h\xc3\xb4te cible")

▪ Eskimbot ☼ 21 janvier 2006 à 11:40 (CET)

= Après vérification manuelle, Le lien ne pose aucun souci.

▪ Anonyme: = Le lien amène sur une erreur 404

No comprendo

" Ils sont cependant assez complexes à mettre en œuvre, car les opérations d'insertion et de suppression font appel à de nombreuses études de cas"

Je ne comprends pas cette phrase, surtout le car : les études de cas estsont en principe quelque chose qu'on décide, pas qu'on subit; des effets et non des causes.

212.198.148.24 (d) 22 mai 2013 à 20:24 (CEST)

Le sens de cette phrase est que, pour effectuer une action sur cette structure, il faut faire de nombreux tests . En gros, c'est pénible. Regarde par exemple l'algorithme d'insertion sur l'article anglais. Zandr4^[Kupopo ?] 23 mai 2013 à 11:00 (CEST)

Ça ne change pas la pertinence de sa remarque sur l'utilisation de l'expression "étude de cas" ici... 2A01:E34:EC01:15F0:B81E:405F:C66A:42A4 (discuter) 20 mai 2022 à 11:48 (CEST)

Eventuel bug dans le code

Bonjour,

Il me semble d'avoir trouvé une erreur dans le code proposé de l'article

 "Arbre bicolore" de https://fr.wikipedia.org/wiki/Arbre_bicolore

et également dans la version anglaise:

 "Red–black tree"

En insérant les nœuds avec clé = 1, et puis 3: L'arbre résultant est alors de la forme:

           1-noir
          /      \ 
         --     3-rouge
               /      \ 
              --      --

Insérons maintenant un nœud avec une clé = 2: Après "insertion_recursif", mais AVANT "insertion_repare_arbre", nous avons l'arbre (non conforme):

          1-noir
          /      \ 
         --       \ 
                  3-rouge
                 /       \ 
                /         \ 
             2-rouge      --
             /     \
            --     --

En appelant la réparation:

void insertion_repare_arbre(struct noeud *n)

{
  if (parent(n) == NULL)
     insertion_cas1(n);
  else if (parent(n)->couleur == NOIR)
     insertion_cas2(n);
  else if (oncle(n)->couleur == ROUGE)
     insertion_cas3(n);
  else
     insertion_cas4(n);
}

Ca plante !

En effet, comme parent(2) n'est pas NULL, et comme parent(2) n'est pas noir, on fait donc le test si l'oncle de n est rouge, alors que cet oncle n'existe pas!

Le cas ou l'oncle n'existe pas semble avoir été oublié.

Essayez le code:

struct node {

 node *parent, *left, *right;
 Color color;
 int key;

};

// …

 node *root=0, *n1, *n2, *n3;

 n1=new node(); n1->key=1;
 root=insert(root,n1);

 n3=new node(); n3->key=3;
 root=insert(root,n3);

 n2=new node(); n2->key=2;
 root=insert(root,n2);

Merci d'avance pour votre réponse (qui peut être en anglais).

--GrainDur (discuter) 17 décembre 2018 à 04:38 (CET)

Typo ?

" (en le nombre d'éléments) " => ce n'est pas français et je ne comprends pas ce qu'on a voulu dire. 2A01:E34:EC01:15F0:B81E:405F:C66A:42A4 (discuter) 20 mai 2022 à 11:50 (CEST)

"En le" est une forme rare en français, voir https://www.cnrtl.fr/definition/en p.ex pour les explications. FrançoisD 20 mai 2022 à 16:39 (CEST)

Arbre bicolore pas forcément ABR ?

Bonjour,

La définition d'arbre bicolore actuellement présentée dans l'article impose que ce soit un ABR. Peut-être est-il plus simple dans un premier temps de présenter la définition d'arbre bicolore indépendamment de la définition d'ABR ? Luuuuc (discuter) 21 juin 2023 à 18:10 (CEST)

C'est le type le plus couramment employé, de toute manière c'est toujours la même chose, il faudrait juste préciser que l'exemple décrit un RBT. Je crois qu'il faudrait surtout expliquer clairement quelque part que la « couleur » n'en est pas vraiment une, c'est une métaphore car il s'agit juste d'avoir une propriété binaire qui permet de distinguer deux types d'éléments dans l'arbre. CaféBuzz (d) 12 mai 2024 à 18:45 (CEST)