Arbre bouc-émissaire

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.

Intérêt

Le principal intérêt de l'arbre bouc-émissaire concerne sa complexité spatiale. Il s'agit du premier arbre binaire de recherche dont les opérations sont en O(log(n)) en moyenne où n est le nombre de nœuds, et qui ne prend pas plus de mémoire qu'un arbre binaire de recherche. En effet, contrairement aux arbres bicolores et AVL qui stockent dans les nœuds des informations supplémentaires (telles que sa couleur ou sa hauteur), le bouc-émissaire ne garde en mémoire que l'étiquette du nœud et ses deux pointeurs vers ses enfants. Ainsi, cet arbre est plus économe en mémoire.

Exemple

Insertion

Considérons l'arbre suivant, où le nœud 4.4 vient tout juste d'être inséré. Cet arbre est un arbre binaire de recherche : chaque nœud est plus grand que tous les nœuds de son sous-arbre gauche et plus petit que les nœuds dans son sous-arbre droit. Si un arbre possède 11 nœuds, on dira qu'il est de taille 11.

Exemple d'un arbre devant être rééquilibré.

Recherche du nœud bouc-émissaire

On choisit une constante d'équilibrage, par exemple . Le nœud (4.4) est à une profondeur 6. Comme , notre arbre n'est donc pas 2/3-équilibré. Un rééquilibrage est nécessaire. Pour cela, nous allons trouver le nœud responsable du déséquilibre : le nœud bouc-émissaire. On définit la taille d'un nœud comme étant la taille du sous-arbre enraciné sur ce nœud. La condition de bouc-émissaire est .

Dans l'exemple précédent, on insère le nœud 4.4, et on remonte de parent en parent pour trouver le bouc-émissaire.

  • donc le nœud (4.2) n'est pas le bouc-émissaire.
  • donc le nœud (4.5) n'est pas le bouc-émissaire.
  • donc le nœud (4) n'est pas le bouc-émissaire.
  • donc le nœud (6) est le bouc-émissaire.

La section théorique explique plus en détail ce processus.

Rééquilibrage

Une fois que le bouc-émissaire a été trouvé, on rééquilibre tout son sous-arbre. Ici, le nœud (6) a été choisi, donc les 7 éléments de son sous-arbre sont placés comme dans un arbre binaire de recherche. On observe que ceci réduit sa profondeur : l'arbre entier est mieux équilibré.

Arbre bouc-émissaire rééquilibré

Théorie

Dans toute cette partie, un arbre sera la donnée d'un nœud noté "e" et de ses enfants gauche "g" et droite "d". La taille d'un nœud e, notée taille(e) est le nombre de nœuds qu'il y a dans l'arbre enraciné en ce nœud.

Définitions

Un arbre binaire de recherche est dit équilibré s'il y a autant de nœuds à droite de la racine qu'à gauche. On relâche cette notion en introduisant deux définitions paramétrées. Un nœud e est un nœud α-équilibré en poids si

Un arbre α-équilibré en poids est alors un arbre n'ayant que des nœuds α-équilibrés en poids. De façon similaire, on dira qu'un arbre est α-équilibré en hauteur si :.

Propriétés

Propriété 1. Un arbre α-équilibré en poids est également α-équilibré en hauteur.

Ainsi, par contraposée, un arbre bouc-émissaire étant le plus petit arbre non α-équilibré en poids, il ne peut être un arbre α-équilibré en hauteur (c'est d'ailleurs un premier critère discriminatoire dans la recherche de notre bouc-émissaire). Cependant, on dispose de la propriété suivante.

Propriété 2. Un arbre bouc-émissaire est presque -équilibré en hauteur : hauteur(arbre) .

Ceci constitue donc un premier critère discriminatoire dans la recherche de notre arbre bouc-émissaire.

De plus, cette propriété montre que la hauteur d'un arbre bouc-émissaire est majorée, à l'instar des arbres rouge-noir. La principale différence provient du moment où s'effectue le rééquilibrage: l'arbre bouc-émissaire le fait à la première rencontre avec un nœud non -équilibré en poids.

Dans la suite, nous considérons α ]1/2,1[fixé. Nous appellerons "nœud profond" tout nœud de profondeur supérieure à . C'est la détection de ces derniers qui enclenche le processus de rééquilibrage.

Opérations

Dans cette section, nous détaillons les opérations de recherche, d'insertion et de suppression dans un arbre bouc-émissaire[3]. On note n = taille(A), où A désigne l'arbre bouc-émissaire sur lequel on effectue les opérations. La valeur de n est stockée. Au cours de l'insertion et la suppression, on met à jour la valeur de n.

Recherche

L'algorithme de recherche est le même que pour un arbre binaire de recherche classique. Ainsi, la complexité dans le pire des cas est en .

Insertion

Le principe de l'insertion repose sur la mémorisation de la profondeur à laquelle le nouveau nœud est inséré. On commence par insérer aux feuilles l'élément x. On regarde récursivement si l'élément doit être ajouté à gauche ou à droite du nœud et on incrémente à chaque étape la valeur de la profondeur d d'insertion. On vérifie si l'arbre ainsi construit est α-équilibré en taille en testant que d ). Si ce n'est pas le cas, un rééquilibrage est nécessaire.

On cherche alors le sous-arbre bouc émissaire dont la racine va subir le rééquilibrage. Celle-ci est un ancêtre du nœud inséré et n'est pas α-équilibré en poids (il y aura toujours un tel nœud).

Ce nœud peut être trouvé en remontant de parent en parent à partir du nœud inséré. Le rééquilibrage d'un tel sous-arbre assure la propriété d'α-équilibré en taille dans tout l'arbre.

L'intérêt de remonter ainsi dans l'arbre pour trouver le nœud bouc-émissaire ne vérifiant pas les conditions

  • taille(enfant gauche) < α*taille(nœud)
  • taille(enfant droite) < α*taille(nœud)

est que nous disposons déjà des tailles d'un des enfants et du nœud.

Il y a dès lors moins de calcul à effectuer. On sait que le cas de base (la hauteur du nœud inséré qui est une feuille) est égal à 1. Il suffit alors de remonter l'arbre comme décrit précédemment, en calculant la taille de chaque nouveau nœud comme suit:

taille() = taille() + taille(frère de ) + 1

où seule la taille du frère de reste à déterminer.

Une fois le nœud bouc-émissaire localisé, on rééquilibre l'arbre dont il est racine (en le remplaçant par un autre arbre contenant les mêmes noeuds mais parfaitement -balancé). Une manière de faire est de parcourir les noeuds de l'arbre en les triant par valeur, puis choisir récursivement la valeur médiane comme racine du nouvel arbre. Ceci s'effectue en O(taille()) en temps.

Suppression

Contrairement à la plupart des autres types d'arbre, la suppression est plus simple que l'insertion. Pour ce faire, il faut garder en mémoire une valeur en plus de la structure d'arbre, que nous appellerons MaxNoeudsComptés. Il s'agit du plus grand nombre de noeuds que l'arbre a pu compter depuis le dernier rééquilibrage complet de l'arbre.

Ainsi, lorsqu'il y a un rééquilibrage, MaxNoeudsComptés est réinitialisé à la taille de l'arbre. À chaque insertion, MaxNoeudsComptés = max(MaxNoeudsComptés,n+1).

Ensuite, pour supprimer le nœud, on fait comme dans n'importe quel arbre binaire, puis on regarde si:

n *MaxNoeudsComptés

Si c'est le cas, alors on rééquilibre entièrement l'arbre, en réinitialisant MaxNoeudsComptés.

Complexité

En ignorant les opérations de rééquilibrage et de recherche d'un arbre bouc-émissaire, les complexités de l'insertion, suppression et recherche sont proportionnelles à la hauteur de l'arbre. Elles sont en .

Étudions la part de complexité qui n'est pas encore prise en compte.

Lemme. lors de l'insertion d'un élément, le coût pour trouver le nœud bouc-émissaire w et le reconstruire est O(taille(w)).

Théorème. En partant d'un arbre vide, une séquence de m opération d'insertion ou suppression a une complexité amortie de .

Étymologie

Le nom d'arbre bouc-émissaire est « basé sur la sagesse populaire selon laquelle, dès que quelque chose ne va pas, la première chose que les gens auront tendance à faire est de trouver quelqu'un à blâmer pour cela (le bouc-émissaire). Une fois ce blâme clairement établi, on peut laisser au bouc-émissaire le soin de résoudre le problème »[4].

Voir également

Notes et références

  1. Arne Andersson « Improving partial rebuilding by using simple balance criteria » () (DOI 10.1007/3-540-51542-9_33, CiteSeerx 10.1.1.138.4859, lire en ligne)
    Proc. Workshop on Algorithms and Data Structures
    « (ibid.) », Journal of Algorithms, Springer-Verlag,‎ , p. 393–402
  2. Igal Galperin et Ronald L. Rivest « Scapegoat trees » () (CiteSeerx 10.1.1.309.9376, lire en ligne)
    « (ibid.) », Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, Philadelphia, Society for Industrial and Applied Mathematics,‎ , p. 165–174
  3. Igor Galperin, On Consulting a Set of Experts and Searching (lire en ligne), « Chapter 3 - Scapegoat Trees »
  4. Pat Morin, Open Data Structures (in pseudocode), 0.1G β (lire en ligne), « Chapter 8 - Scapegoat Trees »

Liens externes

Read other articles:

Katedral RagusaKatedral Santo Yohanes PembaptisItalia: Cattedrale di S. Giovanni Battistacode: it is deprecated Katedral RagusaLokasiRagusa, SisiliaNegaraItaliaDenominasiGereja Katolik RomaArsitekturStatusKatedralStatus fungsionalAktifAdministrasiKeuskupanKeuskupan Ragusa Katedral Ragusa (Italia: Duomo di Ragusa, Cattedrale di San Giovanni Battistacode: it is deprecated ) adalah sebuah gereja katedral Katolik yang terletak di Ragusa, Sisilia, Italia. Katedral ini didedikasikan untuk Santo Yoh...

 

 

Famili GPCR adhesi manusia. Anggota didefinisikan oleh struktur hibrida yang tidak biasa dengan wilayah ekstraseluler yang panjang sering mengandung protein modul yang dikenal digabungkan ke daerah transmembran tujuh rentang melalui domain GPCR-Autoproteolsis INducing (GAIN) GPCR adhesi (adhesion G protein-protein-coupled receptor) adalah kelas 33 reseptor protein manusia dengan distribusi yang luas di sel embrio dan larva, sel-sel dari saluran reproduksi, neuron, leukosit, dan berbagai tumor...

 

 

Artikel ini tidak memiliki referensi atau sumber tepercaya sehingga isinya tidak bisa dipastikan. Tolong bantu perbaiki artikel ini dengan menambahkan referensi yang layak. Tulisan tanpa sumber dapat dipertanyakan dan dihapus sewaktu-waktu.Cari sumber: Mahmoud al-Zahar – berita · surat kabar · buku · cendekiawan · JSTOR Mahmoud al-Zahar300x300px Nama dalam bahasa asli(ar) م BiografiKelahiran6 Mei 1945 (78 tahun)Gaza Kementerian Luar Negeri dan Ekspatr...

The Colombo Express, salah satu kapal peti kemas yang terbesar yang dioperasikan oleh Hapag-Lloyd dari Jerman Kapal peti kemas (Inggris: containership atau celullarship) adalah kapal yang khusus digunakan untuk mengangkut peti kemas yang standar. Memiliki rongga (cells) untuk menyimpan peti kemas ukuran standar. Peti kemas diangkat ke atas kapal di terminal peti kemas dengan menggunakan kran/derek khusus yang dapat dilakukan dengan cepat, baik derek-derek yang berada di dermaga, maupun derek ...

 

 

Persatuan Sepak Bola Afrika BaratUnion des Fédérations Ouest-Africaines de Football  Zona A  Zona BTanggal pendirian1975; 49 tahun lalu (1975)TipeOrganisasi OlahragaWilayah layanan Afrika BaratJumlah anggota Zona A – 9 anggota Gambia Guinea Guinea-Bissau Liberia Mali Mauritania Senegal Sierra Leone Tanjung Verde Zona B – 7 anggota Benin Burkina Faso Ghana Niger Nigeria Pantai Gading Togo Bahasa resmi Inggris, Prancis dan PortugisAfiliasiCAF, ...

 

 

René Teulade Fonctions Sénateur français 1er octobre 2008 – 13 février 2014(5 ans, 4 mois et 12 jours) Élection 21 septembre 2021 Circonscription Corrèze Groupe politique SOC Prédécesseur Bernard MuratGeorges Mouly Successeur Patricia Bordas 1er vice-président du Conseilgénéral de la Corrèze 20 mars 2008 – 31 mars 2011 (3 ans et 11 jours) Président François Hollande Prédécesseur Georges Mouly Successeur Gérard Bonnet Conseiller général de la Co...

Oriental ClubStratford HouseFormation1824(Clubhouse occupied since 1962)PurposeEast India Company civil and military officers who served in the EastHeadquartersStratford HouseLocationLondon, WC1 The Oriental Club in London is an exclusive Private Members’ Club established in 1824.[1] Charles Graves describes it as fine in quality as White's but with the space of infinitely larger clubs.[2] It is located in Stratford Place, near Oxford Street and Bond Street. Foundation The ...

 

 

Disambiguazione – Se stai cercando l'omonimo comune del Kentucky, vedi Edmonton (Kentucky). Edmontoncittà (city)City of Edmonton Edmonton – Veduta LocalizzazioneStato Canada Provincia Alberta Divisione censuariaDivisione No. 11 AmministrazioneSindacoAmarjeet Sohi (Partito Liberale del Canada) dal 29-10-2021 TerritorioCoordinate53°32′N 113°30′W / 53.533333°N 113.5°W53.533333; -113.5 (Edmonton)Coordinate: 53°32′N 113°30′W / &#x...

 

 

Vadenacomune(IT) Vadena(DE) Pfatten Vadena – Veduta LocalizzazioneStato Italia Regione Trentino-Alto Adige Provincia Bolzano AmministrazioneSindacoElmar Oberhofer (SVP) dal 22-9-2020 Lingue ufficialiItaliano, Tedesco TerritorioCoordinate46°24′50.38″N 11°18′18.28″E / 46.413995°N 11.305077°E46.413995; 11.305077 (Vadena)Coordinate: 46°24′50.38″N 11°18′18.28″E / 46.413995°N 11.305077°E46.413995; 11.305077 (Va...

American heavy metal supergroup For other uses, see Hell Yeah (disambiguation). HellyeahHellyeah performing in 2013Background informationOriginDallas, Texas, U.S.Genres Groove metal heavy metal alternative metal Years active2006–2021 (indefinite hiatus)Labels Eleven Seven Epic Past members Chad Gray Christian Brady Tom Maxwell Kyle Sanders Roy Mayorga Vinnie Paul Greg Tribbett Bob Zilla Jerry Montano Websitehellyeahband.com Hellyeah, stylized as HELLYEAH, was an American heavy metal supergr...

 

 

Canadian mixed martial artist Gillian RobertsonRobertson in 2024Born (1995-05-17) May 17, 1995 (age 28)Niagara Falls, Ontario, Canada[1]Other namesThe SavageHeight5 ft 5 in (1.65 m)Weight115 lb (52 kg; 8 st 3 lb)DivisionStrawweight (2016, 2023–) Flyweight (2016–2022)Reach63[1] in (160 cm)StyleBrazilian Jiu-Jitsu, KickboxingFighting out ofPort Saint Lucie, Florida, United States[2]TeamAmerican Top Team (2011–2020)&...

 

 

2011 single by Nicki Minaj featuring Rihanna FlySingle by Nicki Minaj featuring Rihannafrom the album Pink Friday ReleasedAugust 30, 2011Recorded2010StudioGlenwood Place Studios (Burbank, California); Chalice Recording Studios (Los Angeles, California)Length3:32Label Young Money Cash Money Universal Motown Universal Republic Songwriter(s) Kevin Hissink W. Jordan Onika Maraj J.R. Rotem Clemm Rishad Producer(s) J.R. Rotem Skrt Kevin Hissink Nicki Minaj singles chronology Lollipop Luxury (20...

2020年夏季奥林匹克运动会波兰代表團波兰国旗IOC編碼POLNOC波蘭奧林匹克委員會網站olimpijski.pl(英文)(波兰文)2020年夏季奥林匹克运动会(東京)2021年7月23日至8月8日(受2019冠状病毒病疫情影响推迟,但仍保留原定名称)運動員206參賽項目24个大项旗手开幕式:帕维尔·科热尼奥夫斯基(游泳)和马娅·沃什乔夫斯卡(自行车)[1]闭幕式:卡罗利娜·纳亚(皮划艇)&#...

 

 

Short story by Hans Christian AndersenThe AngelShort story by Hans Christian AndersenIllustration from the 1888 anthology Hans Andersen's Fairy TalesOriginal titleEnglenCountryDenmarkLanguageDanishGenre(s)Literary fairy talePublicationPublished inNew Fairy Tales. First Volume. First Collection (Nye Eventyr. Første Bind. Første Samling)Publication typeFairy tale collectionPublisherC.A. ReitzelMedia typePrintPublication date11 November 1843Chronology  —   The Nighting...

 

 

La consommation de carburant d’une automobile est le volume de carburant utilisé lors d'un trajet rapporté à la distance parcourue. L’unité utilisée pour la consommation de carburant est le « litre pour cent kilomètres » (noté l/100 km)[1]. En Europe, la consommation de carburant fait partie des données nécessaires pour l'homologation des véhicules automobiles. La réduction de consommation des véhicules automobiles constitue un enjeu important pour la société par...

دير الزور دير الزور  اللقب لؤلؤة الفرات تاريخ التأسيس 1865 ميلادي تقسيم إداري البلد  سوريا[1] عاصمة لـ محافظة دير الزورمتصرفية الزور  المحافظة محافظة دير الزور خصائص جغرافية إحداثيات 35°20′00″N 40°09′00″E / 35.333333°N 40.15°E / 35.333333; 40.15 الارتفاع 253 متر (830 قدم) ...

 

 

33°40′N 47°00′E / 33.667°N 47.000°E / 33.667; 47.000 زاغروس سلسلة جبال زاغروس الموقع إيران العراق  إحداثيات 33°40′00″N 47°00′00″E / 33.666667°N 47°E / 33.666667; 47   الارتفاع 4409 متر  الطول 1500 كيلومتر  المساحة 533512 كيلومتر مربع  القمة الأم زرد كوه  [لغات أخرى]‏  تع...

 

 

American superhero television series Gen VAlso known asThe Boys: Gen VGenre Black comedy Drama Superhero Based onThe Boys Volume 4: We Gotta Go Nowby Garth EnnisDarick RobertsonDeveloped by Craig Rosenberg Evan Goldberg Eric Kripke Showrunners Michele Fazekas Tara Butters Starring Jaz Sinclair Chance Perdomo Lizze Broadway Maddie Phillips London Thor Derek Luh Asa Germann Shelley Conn Composers Matt Bowen Christopher Lennertz Country of originUnited StatesOriginal languageEnglishNo. of season...

This template does not require a rating on Wikipedia's content assessment scale.It is of interest to the following WikiProjects:Stub sorting This template is maintained by WikiProject Stub sorting, an attempt to bring some sort of order to Wikipedia. If you would like to participate, you can choose to improve/expand the articles containing this stub notice, or visit the project page, where you can join the project and see a list of open tasks.Stub sortingWikipedia:WikiProject Stub sortingTemp...

 

 

Artikel ini tidak memiliki referensi atau sumber tepercaya sehingga isinya tidak bisa dipastikan. Tolong bantu perbaiki artikel ini dengan menambahkan referensi yang layak. Tulisan tanpa sumber dapat dipertanyakan dan dihapus sewaktu-waktu.Cari sumber: Elektronika digital – berita · surat kabar · buku · cendekiawan · JSTOR Hitachi J100 dapat disesuaikan dan sasis penggerak frekuensi dunia AS Elektronika digital adalah sistem elektronika yang menggunaka...