AVL Tree uppfanns av GM Adelson - Velsky och EM Landis 1962. Trädet heter AVL för att hedra sina uppfinnare.
understrykning i markdown
AVL-träd kan definieras som ett höjdbalanserat binärt sökträd där varje nod är associerad med en balansfaktor som beräknas genom att subtrahera höjden på dess högra underträd från höjden på dess vänstra underträd.
Trädet sägs vara balanserat om balansfaktorn för varje nod är mellan -1 till 1, annars kommer trädet att vara obalanserat och behöva balanseras.
Balansfaktor (k) = höjd (vänster(k)) - höjd (höger(k))
Om balansfaktorn för någon nod är 1, betyder det att det vänstra underträdet är en nivå högre än det högra underträdet.
Om balansfaktorn för någon nod är 0, betyder det att det vänstra underträdet och det högra underträdet har samma höjd.
Om balansfaktorn för någon nod är -1 betyder det att det vänstra underträdet är en nivå lägre än det högra underträdet.
Ett AVL-träd visas i följande figur. Vi kan se att balansfaktor associerad med varje nod är mellan -1 och +1. därför är det ett exempel på AVL-träd.
Komplexitet
| Algoritm | Genomsnittligt fall | Värsta fall |
|---|---|---|
| Plats | på) | på) |
| Sök | o(log n) | o(log n) |
| Föra in | o(log n) | o(log n) |
| Radera | o(log n) | o(log n) |
Operationer på AVL-trädet
På grund av det faktum att AVL-trädet också är ett binärt sökträd, utförs därför alla operationer på samma sätt som de utförs i ett binärt sökträd. Sökning och korsning leder inte till intrång i egendom av AVL-träd. Men infogning och radering är de operationer som kan bryta mot den här egenskapen och därför måste de ses över igen.
| SN | Drift | Beskrivning |
|---|---|---|
| 1 | Införande | Insättning i AVL-träd utförs på samma sätt som det utförs i ett binärt sökträd. Det kan dock leda till kränkning i AVL-trädfastigheten och därför kan trädet behöva balanseras. Trädet kan balanseras genom att applicera rotationer. |
| 2 | Radering | Radering kan också utföras på samma sätt som det utförs i ett binärt sökträd. Radering kan också störa balansen i trädet, därför används olika typer av rotationer för att balansera om trädet. |
Varför AVL Tree?
AVL-trädet styr höjden på det binära sökträdet genom att inte låta det skeva. Tiden det tar för alla operationer i ett binärt sökträd med höjden h är Åh) . Den kan dock utökas till På) om BST blir sned (dvs i värsta fall). Genom att begränsa denna höjd till log n, sätter AVL-trädet en övre gräns för varje operation som ska vara O(log n) där n är antalet noder.
AVL-rotationer
Vi utför rotation i AVL-träd endast i fall om Balansfaktor är annat än -1, 0 och 1 . Det finns i princip fyra typer av rotationer som är följande:
- L L-rotation: Den infogade noden finns i det vänstra underträdet i det vänstra underträdet i A
- R R-rotation: Den infogade noden finns i det högra underträdet i det högra underträdet i A
- L R-rotation: Den infogade noden finns i det högra underträdet av det vänstra underträdet i A
- R L-rotation: Infogad nod är i det vänstra underträdet av det högra underträdet av A
Där nod A är den nod vars balansfaktor är annan än -1, 0, 1.
De två första rotationerna LL och RR är enkla rotationer och de följande två rotationerna LR och RL är dubbelrotationer. För att ett träd ska vara obalanserat måste minsta höjd vara minst 2. Låt oss förstå varje rotation
1. RR Rotation
När BST blir obalanserad, på grund av att en nod infogas i det högra underträdet i det högra underträdet av A, utför vi RR-rotation, RR-rotation är en moturs rotation, som appliceras på kanten under en nod med balansfaktor -2
I exemplet ovan har nod A balansfaktor -2 eftersom en nod C är insatt i det högra underträdet av ett höger underträd. Vi utför RR-rotationen på kanten under A.
2. LL Rotation
När BST blir obalanserad, på grund av att en nod infogas i det vänstra underträdet i det vänstra underträdet av C, utför vi LL-rotation, LL-rotation är medursrotation, vilket appliceras på kanten under en nod med balansfaktor 2.
I exemplet ovan har nod C balansfaktor 2 eftersom en nod A är insatt i det vänstra underträdet i C vänstra underträdet. Vi utför LL-rotationen på kanten under A.
3. LR Rotation
Dubbla rotationer är lite tuffare än enkelrotation som redan har förklarats ovan. LR-rotation = RR-rotation + LL-rotation, dvs först utförs RR-rotation på underträd och sedan utförs LL-rotation på fullt träd, med fullt träd menar vi den första noden från vägen för den infogade noden vars balansfaktor är annan än -1 , 0 eller 1.
byt namn på en mapp linux
Låt oss förstå varje steg mycket tydligt:
| stat | Handling |
|---|---|
 | En nod B har infogats i det högra underträdet av A, det vänstra underträdet av C, på grund av vilket C har blivit en obalanserad nod med balansfaktor 2. Detta fall är L R-rotation där: Inlagd nod är i det högra underträdet av det vänstra underträdet av C |
 | Eftersom LR-rotation = RR + LL-rotation utförs därför RR (moturs) på underträdet rotat vid A först. Genom att göra RR-rotation, nod A , har blivit det vänstra underträdet av B . |
 | Efter att ha utfört RR-rotation är nod C fortfarande obalanserad, d.v.s. har balansfaktor 2, eftersom insatt nod A är till vänster till vänster om C |
 | Nu utför vi LL medurs rotation på fullt träd, dvs på nod C. nod C har nu blivit det högra underträdet av nod B, A är vänster underträd av B |
 | Balansfaktorn för varje nod är nu antingen -1, 0 eller 1, dvs BST är nu balanserad. |
4. RL Rotation
Som redan diskuterats är att dubbelrotationer är lite tuffare än enkelrotation som redan har förklarats ovan. RL-rotation = LL-rotation + RR-rotation, dvs först utförs LL-rotation på underträd och sedan utförs RR-rotation på fullt träd, med fullt träd menar vi den första noden från vägen för den infogade noden vars balansfaktor är annan än -1 , 0 eller 1.
| stat | Handling |
|---|---|
 | En nod B har infogats i det vänstra underträdet av C det högra underträdet av A , på grund av vilken A har blivit en obalanserad nod med balansfaktor - 2. Detta fall är RL-rotation där: Insatt nod är i det vänstra underträdet av det högra underträdet i A |
 | Eftersom RL-rotation = LL-rotation + RR-rotation, alltså LL (medurs) på underträdet rotat vid C utförs först. Genom att göra RR-rotation, nod C har blivit rätt underträd av B . |
 | Efter att ha utfört LL-rotation, nod A är fortfarande obalanserad, d.v.s. har balansfaktor -2, vilket beror på det högra underträdet för noden A i högerunderträdet. |
 | Nu utför vi RR-rotation (rotation moturs) på fullt träd, dvs på nod A. nod C har nu blivit det högra underträdet till nod B, och nod A har blivit det vänstra underträdet till B. |
 | Balansfaktorn för varje nod är nu antingen -1, 0 eller 1, d.v.s. BST är nu balanserad. |
F: Konstruera ett AVL-träd med följande element
H, I, J, B, A, E, C, F, D, G, K, L
1. Infoga H, I, J
Vid införande av ovanstående element, speciellt i fallet med H, blir BST obalanserad eftersom balansfaktorn för H är -2. Eftersom BST är höger-sned, kommer vi att utföra RR-rotation på nod H.
Det resulterande balansträdet är:
hur många noll för en miljon
2. Sätt in B, A
Vid infogning av ovanstående element, speciellt i fallet med A, blir BST obalanserad eftersom balansfaktorn för H och I är 2, betraktar vi den första noden från den senast infogade noden, dvs. H. Eftersom BST från H är vänstersned, vi kommer att utföra LL Rotation på nod H.
Det resulterande balansträdet är:
3. Sätt in E
Vid infogning av E blir BST obalanserad eftersom balansfaktorn för I är 2, eftersom om vi färdas från E till I finner vi att den infogas i det vänstra underträdet i höger underträd av I, vi kommer att utföra LR-rotation på nod I. LR = RR + LL rotation
3 a) Vi utför först RR-rotation på nod B
Det resulterande trädet efter RR-rotation är:
3b) Vi utför först LL-rotation på noden I
Det resulterande balanserade trädet efter LL-rotation är:
4. Infoga C, F, D
När du infogar C, F, D, blir BST obalanserad eftersom balansfaktorn för B och H är -2, eftersom om vi reser från D till B finner vi att den infogas i det högra underträdet i det vänstra underträdet av B, vi kommer att utföra RL Rotation på nod I. RL = LL + RR rotation.
4a) Vi utför först LL-rotation på nod E
Det resulterande trädet efter LL-rotation är:
skiva java
4b) Vi utför sedan RR-rotation på nod B
Det resulterande balanserade trädet efter RR-rotation är:
5. Sätt in G
När G sätts in blir BST obalanserad eftersom balansfaktorn för H är 2, eftersom om vi reser från G till H, finner vi att den infogas i det vänstra underträdet i det högra underträdet av H, vi kommer att utföra LR-rotation på nod I. LR = RR + LL rotation.
mjukvarutestning
5 a) Vi utför först RR-rotation på nod C
Det resulterande trädet efter RR-rotation är:
5 b) Vi utför sedan LL-rotation på nod H
Det resulterande balanserade trädet efter LL-rotation är:
6. Sätt in K
När K sätts in blir BST obalanserad eftersom balansfaktorn för I är -2. Eftersom BST är höger-sned från I till K, kommer vi därför att utföra RR-rotation på noden I.
Det resulterande balanserade trädet efter RR-rotation är:
7. Sätt i L
När du sätter in L-trädet är fortfarande balanserat eftersom balansfaktorn för varje nod nu är antingen -1, 0, +1. Därför är trädet ett balanserat AVL-träd
