En AVL-träd definieras som en självbalansering Skillnaden mellan höjderna på det vänstra underträdet och det högra underträdet för någon nod kallas för balansfaktor av noden.

sammansatt primärnyckel

AVL-trädet är uppkallat efter dess uppfinnare, Georgy Adelson-Velsky och Evgenii Landis, som publicerade det i sin uppsats från 1962 En algoritm för organisation av information.

Exempel på AVL-träd:

AVL-träd

Ovanstående träd är AVL eftersom skillnaderna mellan höjderna på vänster och höger underträd för varje nod är mindre än eller lika med 1.

Operationer på ett AVL-träd:

• Införande
• Radering
• Sökande [Det liknar att utföra en sökning i BST]

Rotera underträden i ett AVL-träd:

Ett AVL-träd kan rotera på ett av följande fyra sätt för att hålla sig själv balanserad:

Vänsterrotation :

När en nod läggs till i det högra underträdet i det högra underträdet, om trädet kommer ur balans, gör vi en enda vänsterrotation.

Vänsterrotation i AVL-träd

Höger rotation :

turbo c++ ladda ner

Om en nod läggs till det vänstra underträdet i det vänstra underträdet, kan AVL-trädet komma ur balans, vi gör en enda högerrotation.

Högerrotation i AVL-trädet

Vänster-Höger rotation :

En vänster-höger-rotation är en kombination där den första vänsterrotationen sker efter att den högerrotationen exekveras.

Vänster-Höger-rotation i AVL-trädet

Höger-vänster rotation :

En höger-vänsterrotation är en kombination där den första högerrotationen sker efter att vänsterrotationen exekveras.

Höger-vänster rotation i AVL-trädet

Tillämpningar av AVL Tree:

1. Det används för att indexera enorma poster i en databas och även för att effektivt söka i den.
2. För alla typer av in-memory-samlingar, inklusive set och ordböcker, används AVL Trees.
3. Databasapplikationer, där infogning och radering är mindre vanliga men frekventa datauppslagningar är nödvändiga
4. Programvara som behöver optimerad sökning.
5. Det används i företagsområden och storylinespel.

Fördelar med AVL Tree:

1. AVL-träd kan självbalansera sig själva.
2. Det är säkert inte skevt.
3. Det ger snabbare uppslag än röd-svarta träd
4. Bättre söktidskomplexitet jämfört med andra träd som binärt träd.
5. Höjd kan inte överstiga log(N), där N är det totala antalet noder i trädet.

Nackdelar med AVL Tree:

1. Det är svårt att genomföra.
2. Den har höga konstanta faktorer för vissa av operationerna.
3. Mindre använda jämfört med röd-svarta träd.
4. På grund av dess ganska strikta balans ger AVL-träd komplicerade insättnings- och borttagningsoperationer när fler rotationer utförs.
5. Ta mer bearbetning för balansering.

Relaterade artiklar:

sharwanand

• Introduktion till binära sökträd – handledningar om datastruktur och algoritmer
• Insättning i ett AVL-träd
• Radering i ett AVL-träd