Arbre bouc-émissaire
De Wikipedia, l'encyclopédie encyclopedia
Un arbre bouc-émissaire, en informatique, plus précisément en algorithmique, est un arbre binaire de recherche auto-équilibrant. Ce type d'arbre a été inventé en 1989 par Arne Andersson[1], puis réinventé en 1993 par Igal Galperin et Ronald L. Rivest[2]. Contrairement à la plupart des autres arbres auto-équilibrants, l'arbre bouc-émissaire se restructure plus rarement. Ainsi, la structure de l'arbre se déséquilibre peu à peu, jusqu'au moment où l'algorithme désigne un nœud bouc-émissaire, désigné comme responsable du déséquilibre. On y effectue alors un rééquilibrage pour que l'arbre retrouve une structure satisfaisante.
L'article doit être débarrassé d'une partie de son jargon ().
Sa qualité peut être largement améliorée en utilisant un vocabulaire plus directement compréhensible. Discutez des points à améliorer en page de discussion.
Cet article contient des anglicismes (indiquez la date de pose grâce au paramètre date).
Certains termes anglais peu courants en français devraient être remplacés par des termes français équivalents mieux connus. Discutez des points à améliorer en page de discussion.