Arbre équilibré

Pour les articles homonymes, voir Arbre (homonymie).

Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus.

Cet article ne cite pas suffisamment ses sources (octobre 2018).

Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».

En pratique : Quelles sources sont attendues ? Comment ajouter mes sources ?

En informatique, un arbre équilibré, aussi appelé arbre à critère d'équilibre, est un arbre qui maintient une profondeur équilibrée entre ses branches. Cela a l'avantage que le nombre de pas pour accéder à la donnée d'une clé est en moyenne minimisé, et ce nombre est égal (+/- 1) quelle que soit la clé.

Le but est d'éviter de construire des arbres dits dégénérés (arbres peignes), dans lesquels certains chemins d'accès aux données sont d'une longueur disproportionnée. Cela peut être très avantageux lorsqu'on réutilise l'arbre ainsi construit : en effet, utiliser un arbre équilibré permet d'avoir un temps de recherche de complexité logarithmique dans le pire des cas au lieu d'une complexité linéaire, comme c'est parfois le cas pour des arbres dégénérés.

Arbres binaires de recherche bien équilibrés

Les arbres binaires de recherche présentent des cas de dégénérescence les rendant trop lents dans beaucoup de cas. Une amélioration consiste à ajouter à leurs spécifications un critère d'équilibre imposant des restrictions sur le sous-arbre droit (SAD) et gauche (SAG).

Arbre binaire à critère d'équilibre total

Avec ce type d'arbre, l'arbre doit être complet c'est-à-dire que, si sa profondeur est $n$ , le niveau $n-1$ est entièrement rempli. Cette approche est très rarement utile, une insertion pouvant demander la réorganisation de l'arbre entier. Insertion et suppression en $O(n)$ , recherche en $O(\log _{2}{n})$ .

Arbre binaire à critère d'équilibre partiel

Dans un arbre AVL, la hauteur du SAG et celle du SAD diffèrent au plus de un. Le nombre maximal de réorganisations est en $O(\log _{2}{(n)})$ , c'est-à-dire la hauteur de l'arbre. L'insertion, la recherche et la suppression sont en $O(\log _{2}{(n)})$ .

Arbre rouge-noir

Arbre SBB ou arbre rouge-noir : un arbre équilibré où la profondeur maximum de l'arbre est en $2*O(\log _{2}{(n+1)})$ .

Structure de données similaire

Il existe une structure de donnée hybride qui ressemble à un arbre et dont les feuilles forment une liste chaînée : la skip list. Elle possède aussi un critère d'équilibre ; mais celui-ci est probabiliste, et non déterministe.

v · m Arbre enraciné
Arbre binaire	Arbre binaire de recherche Arbre de fouille Arbre cartésien MVP Tree (en) Top tree (en) T-tree (en)
Arbre équilibré	AA tree (en) Arbre AVL LLRB tree (en) Arbre bicolore Arbre bouc-émissaire Arbre splay Treap
Arbre B	B*-tree (en) Bx-tree (en) UB-tree (en) 2-3 tree (en) Arbre 2-3-4 (a,b)-tree (en) Dancing tree Htree (en)
Trie	Arbre des suffixes Arbre radix Arbre ternaire de recherche X-fast trie (en) Y-fast trie (en)
Partition binaire de l'espace trees	Quadtree Octree Arbre kd (relaxé) Implicit k-d tree (en) Vp-tree
Arbres non binaires	Arbre exponentiel Fusion tree (en) arbre d'intervalles arbre PQ arbre de portée (range tree) arbre SPQR arbre de Van Emde Boas
Arbre de base de données spatiales	R-arbre R+ tree (en) R* tree (en) X-tree (en) M-tree (en) arbre de segments Hilbert R-tree (en) Priority R-tree (en)
Autres arbres	Arbre de Merkle Arbre couvrant de poids minimal Arbre syntaxique Arbre de la syntaxe abstraite Finger tree (en) Order statistic tree (en) Arbre métrique Cover tree (en) BK-tree (en) Doubly chained tree iDistance (en) Link-cut tree (en) Fenwick tree (en) Tas Binaire Binomial Fibonacci Arbre cousu

v · m Structure de données
Type abstrait	Ensemble File File d'attente à double extrémité File de priorité Liste Vecteur Graphe Union-find
Tableau	Buffer circulaire Tableau de bits Table de hachage Vecteur
Chaînage	Liste chaînée Skip list Chaînage XOR
Arbre	Arbre B Arbre binaire de recherche AVL Bicolore Équilibré Splay Tas Binaire Binomial Fibonacci Trie
Graphe	Diagramme de décision binaire

Portail de l'informatique théorique

Read other articles:

NBC

American broadcast television network For other uses, see NBC (disambiguation). Peacock Network redirects here. For the streaming service, see Peacock (streaming service). Television channel National Broadcasting CompanyTypeRadio and television networkCountryUnited StatesAffiliatesStateMarketHeadquartersComcast Building, Rockefeller Center, Midtown Manhattan, New York CityProgrammingLanguage(s)EnglishPicture format1080i HDTV720p or 1080p via ATSC 3.0 in some marketsOwnershipOwnerNBCUniversalP...

The Boat Race 2007

{{{Name}}} The Boat Race ke-153 merupakan balap perahu tahunan yang berlangsung pada tanggal 7 April 2007. Balapan tersebut mempertandingan dua tim dari Universitas Oxford dan Cambridge dalam balap dayung berdampingan di sepanjang Sungai Thames. The Boat Race 2007 menghadirkan atlet dari luar Inggris terbanyak sepanjang sejarah balapannya. Balapan tersebut dimenangkan oleh tim dari Cambridge dengan jarak 1¼ length dalam waktu 17 menit 49 detik. Tim Cambridge terdiri dari beberapa kru yang r...

Rio Steven Dumatubun

Ini adalah nama Maluku, (Kei), marganya adalah Dumatubun Rio Steven DumatubunLahir17 April 1984 (umur 39)Semuli Raya, Lampung, IndonesiaPekerjaanPelawak tunggalaktorTahun aktif2015—sekarangSuami/istriSari Sumartini (m. 2011)Anak2 Rio Steven Dumatubun (lahir 17 April 1984) adalah seorang pelawak tunggal dan aktor berkebangsaan Indonesia. Rio yang merupakan bagian dari komunitas Stand Up Indo Jakarta Barat ini mulai dikenal setelah mengikuti kompetisi ...

Lesjaverk

Village in Lesja, Norway Village in Eastern Norway, NorwayLesjaverkVillageView of the village railway stationLesjaverkLocation of the villageShow map of InnlandetLesjaverkLesjaverk (Norway)Show map of NorwayCoordinates: 62°11′32″N 8°32′26″E / 62.19229°N 8.54062°E / 62.19229; 8.54062CountryNorwayRegionEastern NorwayCountyInnlandetDistrictGudbrandsdalenMunicipalityLesja MunicipalityElevation[1]634 m (2,080 ft)Time zoneUTC+01:00 (CET) �...

Laura Stacey

Canadian ice hockey player Ice hockey player Laura Stacey Stacey with PWHL Montreal in 2024Born (1994-05-05) May 5, 1994 (age 29)Mississauga, Ontario, CanadaHeight 5 ft 10 in (178 cm)Weight 157 lb (71 kg; 11 st 3 lb)Position ForwardShoots RightPWHL teamFormer teams PWHL MontrealPWHPAMarkham Thunder (2016-19)Dartmouth Big Green (2012-16)National team CanadaPlaying career 2012–present Medal record Women's ice hockey Representing Canada O...

S1 (Suisse)

Pour les articles homonymes, voir S1. S1CaractéristiquesCréation 18 octobre 2013Propriétaire CH Media[1]Slogan Das neue Schweizer Fernsehen (La nouvelle télévision suisse)Langue Allemand, Suisse allemandPays SuisseStatut Généraliste nationale privéeSiège social S1TV AG Seefeldstrasse 9CH - 8008 Zurich - ZHSite web www.s1tv.chDiffusionAnalogique NonNumérique NonSatellite NonCâble UPC CablecomChronologieTele 24modifier - modifier le code - modifier Wikidata S1 est une chaîne de té...

Silvestro Valier

Silvestro ValierSilvestro Valier ritratto da Nicolò Cassana nel 1694, Pinacoteca Querini Stampalia, Palazzo Querini Stampalia, VeneziaDoge di VeneziaStemma In carica25 febbraio 1694 –7 luglio 1700 PredecessoreFrancesco Morosini SuccessoreAlvise II Mocenigo NascitaVenezia, 28 marzo 1630 MorteVenezia, 7 luglio 1700 (70 anni) DinastiaValier PadreBertuccio Valier MadreBenedetta Pisani ConsorteElisabetta Querini ReligioneCattolicesimo Silvestro Valier (Venezia, 28 marzo 1630 –...

Adaptationism

Darwinian perspective that biological traits are evolved adaptations This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages) This article possibly contains original research. Please improve it by verifying the claims made and adding inline citations. Statements consisting only of original research should be removed. (December 2021) (Learn how and when to remove this template message) This article...

Человек прямоходящий

† Человек прямоходящий Научная классификация Домен:ЭукариотыЦарство:ЖивотныеПодцарство:ЭуметазоиБез ранга:Двусторонне-симметричныеБез ранга:ВторичноротыеТип:ХордовыеПодтип:ПозвоночныеИнфратип:ЧелюстноротыеНадкласс:ЧетвероногиеКлада:АмниотыКлада:Синапсиды�...

Pea Ridge National Military Park

For the military conflict, see Battle of Pea Ridge. Pea Ridge National Military ParkElkhorn Tavern at Pea Ridge National Military ParkMap of ArkansasShow map of ArkansasPea Ridge National Military Park (the United States)Show map of the United StatesLocationBenton County, Arkansas,United StatesNearest cityGarfieldCoordinates36°27′15.″N 94°02′04.9″W / 36.45417°N 94.034694°W / 36.45417; -94.034694Area4,300 acres (17 km2)[1]EstablishedJuly...

Raceland, Louisiana

Census-designated place in Louisiana, United StatesRaceland, LouisianaCensus-designated placeRacelandLocation in LouisianaShow map of LouisianaRacelandLocation in the United StatesShow map of the United StatesCoordinates: 29°43′21″N 90°36′19″W / 29.72250°N 90.60528°W / 29.72250; -90.60528CountryUnited StatesStateLouisianaParishLafourcheArea[1] • Total21.62 sq mi (55.99 km2) • Land21.57 sq mi (55.86&#...

Archevêque

Jean-François de Gondi, premier archevêque de Paris. Dans plusieurs dénominations chrétiennes, un archevêque Écouter est un ministre ecclésiastique appartenant à l'ordre épiscopal, mais bénéficiant d'une primauté d'honneur sur les évêques suffragants. Il est souvent à la tête d'une province ecclésiastique. Dans l'Église catholique Dans l'Église latine Ornement extérieur de l'écu d'un archevêque. Dans l'Église latine, régie par le code de droit canonique, l'archevêque ...

فلافل

فلافلمعلومات عامةاسم آخر طعمية في مصر، والباجية في اليمنالمنشأ مصر[1]المنطقة مصر[2] وانتقلت إلى الشام والعراق واليمنالنوع طبق — minced food ball (en) حرارة التقديم ساخنالمكونات الرئيسية البقوليات: فول أو حمصتعديل - تعديل مصدري - تعديل ويكي بيانات الفلافل وتُسمى الطعمية في م...

Poppendorf

For Poppendorf in Styria, see Poppendorf, Styria. Municipality in Mecklenburg-Vorpommern, GermanyPoppendorf MunicipalityLocation of Poppendorf within Rostock district Poppendorf Show map of GermanyPoppendorf Show map of Mecklenburg-VorpommernCoordinates: 54°8′N 12°18′E / 54.133°N 12.300°E / 54.133; 12.300CountryGermanyStateMecklenburg-VorpommernDistrictRostock Municipal assoc.Carbäk Government • MayorRalf KurthsArea • Total14.03 km...

Comedy film

Genre of film which emphasizes humour Comedic actor Buster Keaton (left) struggling with a wrecked Model T car in The Blacksmith, a 1922 short comedy film A comedy film is a film genre that emphasizes humor. These films are designed to amuse audiences and make them laugh.[1] Films in this genre typically have a happy ending, with dark comedy being an exception to this rule. Comedy is one of the oldest genres in film, and it is derived from classical comedy in theatre. Some of the earl...

1359 in Ireland

List of events in the year 1359 ← 1358 1357 1356 1355 1354 1359 in Ireland → 1360 1361 1362 1363 1364 Centuries: 12th 13th 14th 15th 16th Decades: 1330s 1340s 1350s 1360s 1370s See also:Other events of 1359List of years in Ireland Events from the year 1359 in Ireland. Incumbent Lord: Edward III Events Thomas de Burley, Prior of the Order of St. John of Jerusalem appointed Lord Chancellor of Ireland Births James Butler, 3rd Earl of Ormond, died 1405 Deaths References vteYears in I...

Bronson Reed

Australian professional wrestler Jonah (wrestler) redirects here. For other uses, see Jonah (disambiguation). Bronson ReedReed in 2021Birth nameJermaine HaleyBorn (1988-08-25) 25 August 1988 (age 35)Adelaide, South Australia, AustraliaSpouse(s)Paige Haley[1]Children1Professional wrestling careerRing name(s)Bronson ReedJ-RockJermaine HaileyJonah[2]Jonah RockBilled height6 ft 0 in (1.83 m)[3]Billed weight330 lb (150 kg)[3]Billed fro...

Florida's 12th congressional district

U.S. House district for Florida FL-12 redirects here. For the state road, see Florida State Road 12. Florida's 12th congressional districtInteractive map of district boundaries since January 3, 2023Representative Gus BilirakisR–Palm HarborArea1,069[1] sq mi (2,770 km2)Distribution93.09% urban[2]6.91% ruralPopulation (2022)806,076[3]Median householdincome$59,804[3]Ethnicity75.3% White13.6% Hispanic4.4% Black4.1% Two or more races2.0% Asian...

بوركينا فاسو في الألعاب الأولمبية

يفتقر محتوى هذه المقالة إلى الاستشهاد بمصادر. فضلاً، ساهم في تطوير هذه المقالة من خلال إضافة مصادر موثوق بها. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها. (ديسمبر 2018) بوركينا فاسو في الألعاب الأولمبية علم بوركينا فاسو رمز ل.أ.د. BUR ل.أ.و. اللجنة الأولمبية والريا�...

Portage la Prairie (provincial electoral district)

For the defunct federal electoral district, see Portage la Prairie (federal electoral district). Provincial electoral district in Manitoba, Canada Portage la Prairie Manitoba electoral districtProvincial electoral districtLegislatureLegislative Assembly of ManitobaMLA Jeff BerezaProgressive ConservativeDistrict created1870First contested1870Last contested2023DemographicsPopulation (2016)21,755Electors (2019)14,279Area (km²)2,119Pop. density (per km²)10.3 Portage la Prairie...