AVL træ

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 23. oktober 2021; checks kræver 6 redigeringer .
AVL træ
engelsk  A.V.L træ
Type søgetræ
Opfindelsens år 1968
Forfatter Adelson-Velsky Georgy Maksimovich og Landis Evgeny Mikhailovich
Kompleksitet i O-symboler
Gennemsnit I værste fald
Hukommelsesforbrug På) På)
Søg O(log n) O(log n)
Indsæt O(log n) O(log n)
Fjernelse O(log n) O(log n)
 Mediefiler på Wikimedia Commons

Et AVL-træ  er et højdebalanceret binært søgetræ : for hvert af dets hjørner afviger højden af ​​dets to undertræer med højst 1.

AVL er en forkortelse dannet af de første bogstaver af skaberne (sovjetiske videnskabsmænd) Adelson-Velsky Georgy Maksimovich og Landis Evgeny Mikhailovich .

Maksimal højde

Den maksimale højde af et AVL-træ for et givet antal noder [1] :

hvor:

(runde op)

(rund ned)

(rund ned).

Antallet af mulige højder er meget begrænset i praksis (med 32-bit adressering er den maksimale højde 45, med 48-bit adressering er det 68), så det er nok bedre at forudberegne alle værdierne af minimumsantallet af noder for hver højde ved hjælp af den rekursive formel for Fibonacci-træet :

,

,

.

Mellemværdier for antallet af noder svarer til den tidligere (lavere) højde.

Balancering

Med hensyn til et AVL-træ er toppunktsbalancering en operation, der, hvis højdeforskellen mellem venstre og højre undertræ = 2, ændrer overordnede-underordnede links i undertræet af dette vertex, så forskellen bliver <= 1, ellers ændrer ikke noget. Det angivne resultat opnås ved rotationer af undertræet i det givne toppunkt.

Der anvendes 4 typer rotationer:

1. Lille venstredrejning Denne rotation bruges, når højdeforskellen mellem a-undertræ og b-undertræ er 2 og højde C <= højde R.

2. Stor venstredrejning Denne rotation bruges, når højdeforskellen mellem a-undertræ og b-undertræ er 2 og højde på c-undertræ > højde R.

3. Lille højrerotation Denne rotation bruges, når højdeforskellen mellem a-undertræ og b-undertræ er 2 og højde C <= højde L.

4. Stor højredrejning Denne rotation bruges, når højdeforskellen mellem a-undertræ og b-undertræ er 2 og højde på c-undertræ > højde L.

I hvert tilfælde er det nok blot at bevise, at operationen fører til det ønskede resultat, og at den samlede højde falder med højst 1 og ikke kan stige. Et stort spin er også en kombination af højre og venstre lille spin. På grund af balanceringstilstanden er højden af ​​træet O(log(N)), hvor N er antallet af hjørner, så tilføjelse af et element kræver O(log(N))-operationer.

Algoritme til at tilføje et toppunkt

Balanceindikatoren vil yderligere blive fortolket som forskellen mellem højden af ​​venstre og højre undertræ, og algoritmen vil være baseret på TAVLTree-typen beskrevet ovenfor. Direkte ved indsættelse (ark) tildeles en nulsaldo. Processen med at inkludere et vertex består af tre dele (denne proces er beskrevet af Niklaus Wirth i Algorithms and Data Structures):

  1. Kør langs søgestien, indtil vi er sikre på, at nøglen ikke er i træet.
  2. Inkludering af et nyt toppunkt i træet og bestemmelse af de resulterende balanceringsindikatorer.
  3. "Trækker sig tilbage" langs stien til søgning og kontrol ved hvert hjørne af balanceindikatoren. Om nødvendigt balance.

Vi vender tilbage som følge af funktionen om træets højde er faldet eller ej. Antag, at en proces fra venstre gren vender tilbage til forælderen (rekursionen går tilbage), så er tre tilfælde mulige: { h l  - højden af ​​venstre undertræ, h r  - højden af ​​højre undertræ } Inklusiv et toppunkt i venstre undertræ vil medføre

  1. h l < h r : udligner h l = h r . Der skal ikke gøres noget.
  2. h l = h r : nu vil det venstre undertræ være én større, men balancering er ikke påkrævet endnu.
  3. h l > h r : nu skal h l  - h r = 2, - balancering.

I den tredje situation er det nødvendigt at bestemme balanceringen af ​​det venstre undertræ. Hvis det venstre undertræ af dette toppunkt (Tree^.left^.left) er højere end det højre (Tree^.left^.right), så er en stor højredrejning påkrævet, ellers vil en lille højrerotation være tilstrækkelig. Lignende (symmetriske) ræsonnementer kan gives for optagelse i det højre undertræ.

Algoritme til sletning af et toppunkt

For nemheds skyld beskriver vi en rekursiv sletningsalgoritme. Hvis toppunktet er et blad, så sletter vi det og kalder balanceringen af ​​alle dets forfædre i rækkefølge fra forælder til rod. Ellers finder vi det nærmeste toppunkt i værdi i undertræet af den højeste højde (højre eller venstre) og flytter det til stedet for det toppunkt, der skal slettes, mens vi kalder fjernelsesproceduren.

Lad os bevise, at denne algoritme bevarer balancen. For at gøre dette beviser vi ved induktion på højden af ​​træet, at efter at have fjernet noget toppunkt fra træet og efterfølgende afbalancering, falder træets højde med højst 1. Grunden for induktionen: For et blad, åbenbart sandt. Induktionstrin: Enten er balancebetingelsen ved roden (efter sletning kan roden ændres) ikke overtrådt, så er højden af ​​det givne træ ikke ændret, eller det strengt mindre af undertræerne er faldet => højden før balancering har ikke ændret => derefter vil den ikke falde med mere end 1.

Som et resultat af disse handlinger kaldes fjernelsesproceduren naturligvis ikke mere end 3 gange, da toppunktet, der fjernes af det andet kald, ikke har et af undertræerne. Men at finde den nærmeste kræver O(N) operationer hver gang. Muligheden for optimering bliver indlysende: Søgningen efter det nærmeste toppunkt kan udføres langs kanten af ​​undertræet, hvilket reducerer kompleksiteten til O(log(N)).

Ikke-rekursiv top-down indsættelse i et AVL-træ

En ikke-rekursiv algoritme er mere kompliceret end en rekursiv.

  1. Indsættelsespunktet og toppunktet findes, hvis højde ikke ændres under indsættelsen (dette er toppunktet, for hvilket højden af ​​det venstre undertræ ikke er lig med højden af ​​det højre; vi vil kalde det PrimeNode)
  2. Nedstigning fra PrimeNode til indsættelsespunktet udføres med en ændring i balancer
  3. PrimeNode rebalancerer, når der er et overløb

Ikke-rekursiv sletning fra top til bund af et AVL-træ

For at implementere sletning vil vi gå ud fra det samme princip som ved indsættelse: vi finder et toppunkt, hvor sletning ikke vil føre til en ændring i dets højde. Der er to tilfælde:

  1. højden af ​​det venstre undertræ er lig med højden af ​​det højre undertræ (undtagen når bladet ikke har nogen undertræer)
  2. højden af ​​træet i bevægelsesretningen er mindre end den modsatte ("bror" af retningen) og balancen af ​​"bror" er 0 (parsing af denne mulighed er ret kompliceret, så ingen bevis endnu)

For at lette forståelsen indeholder ovenstående algoritme ingen optimeringer. I modsætning til den rekursive algoritme erstattes det fundne fjernede toppunkt med værdien fra venstre undergren. Denne algoritme kan optimeres på samme måde som den rekursive (på grund af det faktum, at efter at have fundet det toppunkt, der skal fjernes, kendes bevægelsesretningen):

  1. vi leder efter elementet der skal slettes og undervejs finder vi vores skønne top
  2. vi foretager ændringer i balancer, hvis det er nødvendigt, laver vi rebalancering
  3. slet vores element (vi sletter det faktisk ikke, men erstatter dets nøgle og værdi, det vil være lidt mere kompliceret at tage højde for permutationer af hjørner)

Ordning af saldi ved fjernelse

Som allerede nævnt, hvis toppunktet, der skal slettes, er et blad, så slettes det, og den omvendte traversering af træet sker fra forælderen til det slettede blad. Hvis ikke et blad, findes en "erstatning" for det, og den omvendte gennemkøring af træet kommer fra "erstatnings"-forælderen. Umiddelbart efter fjernelse af elementet - "udskiftning" modtager saldoen på den fjernede knude.

I omvendt bypass: hvis de under overgangen til forælderen kom fra venstre, øges saldoen med 1, hvis de kom fra højre, falder den med 1.

Dette gøres indtil balancen ændres til -1 eller 1 (bemærk forskellen med at indsætte et element!): i dette tilfælde ville en sådan balanceændring indikere en konstant deltahøjde af undertræerne. Rotationer følger de samme regler som ved indsættelse.

Arrangering af saldi ved en enkelt omgang

Angiv:

Hvis rotationen sker, når et element indsættes, så er pivotens balance enten 1 eller −1. I dette tilfælde, efter rotationen, sættes saldierne for begge lig med 0. Ved sletning er alt anderledes: Pivots saldo kan blive lig med 0 (dette er let at verificere).

Her er en oversigtstabel over de endelige saldiers afhængighed af rotationsretningen og den indledende balance for pivot-knuden:

Drej retning Gammel pivotbalance Ny Current.Balance Ny pivotbalance
Venstre eller højre -1 eller +1 0 0
Ret 0 -en +1
Venstre 0 +1 -en

Double turn balancer

Pivot og Current er det samme, men et tredje medlem af turn tilføjes. Lad os udpege det til "Bund": det er (med en dobbelt højresving) Pivots venstre søn, og med en dobbelt venstre - Pivots højre søn.

Med denne rotation opnår Bottom altid en balance på 0 som et resultat, men arrangementet af saldi for Pivot og Current afhænger af dens indledende balance.

Her er en oversigtstabel over de endelige saldiers afhængighed af rotationsretningen og den indledende balance for bundknuden:

Retning Gammel Bundbalance Ny Current.Balance Ny pivotbalance
Venstre eller højre 0 0 0
Ret +1 0 -en
Ret -en +1 0
Venstre +1 -en 0
Venstre -en 0 +1

Præstationsvurdering

Ud fra formlen ovenfor vil højden af ​​et AVL-træ aldrig overstige højden af ​​et perfekt afbalanceret træ med mere end 45 %. For store har vi skønnet . Udførelse af grundlæggende operationer kræver således en rækkefølge af sammenligninger. Det er eksperimentelt blevet fundet, at der sker en balancering for hver 2 inklusioner og for hver 5 undtagelser.

Se også

Balancerede (selvbalancerende) træer:

Noter

  1. ↑ D. Knut. Kunsten at programmere. Sorter og søg. - S. 460.

Litteratur