Een AVL-boom gedefinieerd als zelfbalancerend Het verschil tussen de hoogten van de linker subboom en de rechter subboom voor elk knooppunt staat bekend als de evenwichtsfactor van het knooppunt.

De AVL-boom is vernoemd naar de uitvinders, Georgy Adelson-Velsky en Evgenii Landis, die deze in 1962 publiceerden in hun artikel An algoritme voor de organisatie van informatie.

Voorbeeld van AVL-bomen:

AVL-boom

De bovenstaande boom is AVL omdat de verschillen tussen de hoogten van de linker en rechter subboom voor elk knooppunt kleiner dan of gelijk zijn aan 1.

Bewerkingen op een AVL-boom:

• Plaatsing
• Verwijdering
• Zoeken [Het is vergelijkbaar met het uitvoeren van een zoekopdracht in BST]

De subbomen in een AVL-boom roteren:

Een AVL-boom kan op een van de volgende vier manieren roteren om zichzelf in balans te houden:

terwijl lus Java

Linksom draaien :

Wanneer een knooppunt wordt toegevoegd aan de rechter deelboom van de rechter deelboom en de boom uit balans raakt, voeren we een enkele rotatie naar links uit.

Linksrotatie in AVL-boom

Rechtse rotatie :

Als er een knooppunt wordt toegevoegd aan de linker subboom van de linker subboom, kan de AVL-boom uit balans raken. We voeren een enkele rotatie naar rechts uit.

Rechtsrotatie in AVL-boom

tekenreeks naar json java

Links-rechts rotatie :

Een links-rechts-rotatie is een combinatie waarbij de eerste rotatie naar links plaatsvindt nadat die rotatie naar rechts wordt uitgevoerd.

Links-rechts rotatie in AVL-boom

Rechts-links rotatie :

Een rechts-links-rotatie is een combinatie waarbij de eerste rotatie naar rechts plaatsvindt, waarna de rotatie naar links wordt uitgevoerd.

Rechts-links rotatie in AVL-boom

Toepassingen van AVL Boom:

1. Het wordt gebruikt om grote records in een database te indexeren en daar ook efficiënt in te zoeken.
2. Voor alle soorten in-memory collecties, inclusief sets en woordenboeken, worden AVL Trees gebruikt.
3. Databasetoepassingen, waarbij invoegingen en verwijderingen minder gebruikelijk zijn, maar frequente gegevensopzoekingen noodzakelijk zijn
4. Software waarvoor geoptimaliseerd zoeken nodig is.
5. Het wordt toegepast in bedrijfsruimtes en verhaallijnspellen.

Voordelen van AVL Boom:

1. AVL-bomen kunnen zichzelf in evenwicht brengen.
2. Het is zeker niet scheef.
3. Het biedt snellere zoekopdrachten dan rood-zwarte bomen
4. Betere zoektijdcomplexiteit in vergelijking met andere bomen zoals een binaire boom.
5. De hoogte kan niet groter zijn dan log(N), waarbij N het totale aantal knooppunten in de boom is.

Nadelen van AVL-boom:

1. Het is moeilijk uit te voeren.
2. Het heeft hoge constante factoren voor sommige operaties.
3. Minder gebruikt vergeleken met roodzwarte bomen.
4. Vanwege de vrij strikte balans bieden AVL-bomen ingewikkelde invoeg- en verwijderingsoperaties naarmate er meer rotaties worden uitgevoerd.
5. Neem meer verwerking voor het balanceren.

Gerelateerde artikelen:

foreach lus-typescript

• Inleiding tot binaire zoekbomen – Tutorials voor gegevensstructuur en algoritmen
• Invoeging in een AVL-boom
• Verwijdering in een AVL-boom