Voordat we iets weten over de verschillen tussen de binaire zoekboom en de AVL-boom, moeten we de binaire zoekboom en de AVL-boom afzonderlijk kennen.
Wat is een binaire zoekboom?
De binaire zoekboom is een boom binaire boom. Zoals we weten kan die boom 'n' aantal kinderen hebben, terwijl; de binaire boom kan maximaal twee kinderen bevatten. De beperking van een binaire boom wordt dus ook gevolgd door de binaire zoekboom. Elk knooppunt in een binaire zoekboom moet maximaal twee kinderen hebben; met andere woorden, we kunnen zeggen dat de binaire zoekboom een variant is van de binaire boom.
De binaire zoekboom volgt ook de eigenschappen van de binaire zoekopdracht. Bij binair zoeken moeten alle elementen in een array in gesorteerde volgorde staan. We berekenen het middelste element in de binaire zoekopdracht waarbij het linkergedeelte van het middelste element de waarde bevat die kleiner is dan de middelste waarde, en het rechtergedeelte van het middelste element de waarden bevat die groter zijn dan de middelste waarde.
In de binaire zoekboom wordt het middelste element het hoofdknooppunt, het rechterdeel de rechter subboom en het linkerdeel de linker subboom. Daarom kunnen we zeggen dat de binaire zoekboom een combinatie is van a binaire boom En Binaire zoekopdracht .
Opmerking: Binaire zoekboom kan worden gedefinieerd als de binaire boom waarin alle elementen van de linker subboom kleiner zijn dan het hoofdknooppunt, en alle elementen van de rechter subboom groter zijn dan het hoofdknooppunt.
Tijdcomplexiteit in binaire zoekboom
Als de binaire zoekboom bijna een gebalanceerde boom is, zullen alle bewerkingen een tijdscomplexiteit van hebben O(login) omdat de zoekopdracht naar de linker of de rechter subboom is verdeeld.
unieke mysql-sleutel
Als de binaire zoekboom links- of rechtsscheef is, hebben alle bewerkingen een tijdscomplexiteit van Op) omdat we tot aan de n elementen moeten doorlopen.
Wat is de AVL-boom?
Een AVL-boom is een zelfbalancerende binaire zoekboom waarbij het verschil tussen de hoogte van de linker- en rechtersubboom niet meer dan één kan zijn. Dit verschil staat bekend als een balansfactor. In de AVL-boom kunnen de waarden van de balansfactor -1, 0 of 1 zijn.
Hoe gebeurt de zelfbalancering van de binaire zoekboom?
Zoals we weten is de AVL-boom een zelfbalancerende binaire zoekboom. Als de binaire zoekboom niet in balans is, kan deze met enkele herschikkingen zelf in balans zijn. Deze herschikkingen kunnen worden uitgevoerd met behulp van enkele rotaties.
Laten we zelfbalancering begrijpen aan de hand van een voorbeeld.
Stel dat we willen invoegen 10, 20, 30 in een AVL-boom.
niet
Hieronder volgen de manieren om 10, 20, 30 in een AVL-boom in te voegen:
Stap 1: Eerst maken we een binaire zoekboom, zoals hieronder weergegeven:
Stap 2: In de bovenstaande afbeelding kunnen we zien dat de boom uit balans is omdat de balansfactor van knooppunt 30 2 is. Om er een AVL-boom van te maken, moeten we enkele rotaties uitvoeren. Als we de juiste rotatie uitvoeren op knooppunt 20, zal knooppunt 30 naar beneden bewegen, terwijl knooppunt 20 naar boven beweegt, zoals hieronder weergegeven:
Zoals we kunnen zien, volgt de uiteindelijke boom de eigenschap van de binaire zoekboom en een gebalanceerde boom; daarom is het een AVL-boom.
In dit geval was het de boom onevenwichtige boom achtergelaten, dus voeren we de juiste rotatie uit op het knooppunt.
Stap 1: Eerst maken we een binaire zoekboom, zoals hieronder weergegeven:
Stap 2: In de bovenstaande figuur kunnen we zien dat de boom uit balans is omdat de balansfactor van knooppunt 10 -2 is. Om er een AVL-boom van te maken, moeten we enkele rotaties uitvoeren. Het is een rechtse onevenwichtige boom, dus we zullen een linkse rotatie uitvoeren. Als we een rotatie naar links uitvoeren op knooppunt 20, zal knooppunt 20 naar boven bewegen en knooppunt 10 naar beneden, zoals hieronder weergegeven:
Zoals we kunnen zien, volgt de uiteindelijke boom de eigenschap van de Binaire zoekboom en een evenwichtige boom ; daarom is het een AVL-boom.
Stap 1: Eerst maken we de binaire zoekboom, zoals hieronder weergegeven:
Stap 2: In de bovenstaande afbeelding kunnen we zien dat de boom uit balans is omdat de balansfactor van het hoofdknooppunt 2 is. Om er een AVL-boom van te maken, moeten we enkele rotaties uitvoeren. Het bovenstaande scenario is links-rechts onevenwichtig, aangezien het ene knooppunt zich links van het bovenliggende knooppunt bevindt en het andere rechts van het bovenliggende knooppunt. Eerst zullen we de rotatie naar links uitvoeren, en rotatie vindt plaats tussen knooppunten 10 en 20. Na rotatie naar links zal 20 naar boven bewegen en 10 naar beneden, zoals hieronder weergegeven:
Toch is de boom uit balans, dus voeren we de juiste rotatie op de boom uit. Zodra de juiste rotatie op de boom is uitgevoerd, zou de boom het volgende willen:
Zoals we in de bovenstaande boom kunnen zien, volgt de boom de eigenschap van de binaire zoekboom en een gebalanceerde boom; daarom is het een AVL-boom.
Stap 1: Eerst maken we de binaire zoekboom, zoals hieronder weergegeven:
Stap 2: In de bovenstaande afbeelding kunnen we zien dat de boom uit balans is omdat de balansfactor van het hoofdknooppunt 2 is. Om er een AVL-boom van te maken, moeten we enkele rotaties uitvoeren. Het bovenstaande scenario is rechts-links onevenwichtig, omdat één knooppunt zich rechts van het bovenliggende knooppunt bevindt en een ander knooppunt links van het bovenliggende knooppunt. Eerst zullen we de rechtse rotatie uitvoeren die plaatsvindt tussen knooppunten 30 en 20. Na rechtsom draaien zal 20 naar boven bewegen en 30 naar beneden, zoals hieronder weergegeven:
Toch is de bovenstaande boom uit balans, dus moeten we een rotatie naar links op het knooppunt uitvoeren. Zodra de rotatie naar links is uitgevoerd, beweegt knooppunt 20 naar boven en beweegt knooppunt 10 naar beneden, zoals hieronder weergegeven:
theelepel versus eetlepel
Zoals we in de bovenstaande boom kunnen zien, volgt de boom de eigenschap van de binaire zoekboom en een gebalanceerde boom; daarom is het een AVL-boom.
Verschillen tussen binaire zoekboom en AVL-boom
| Binaire zoekboom | AVL-boom |
|---|---|
| Elke binaire zoekboom is een binaire boom omdat beide bomen maximaal twee kinderen bevatten. | Elke AVL-boom is ook een binaire boom omdat de AVL-boom ook maximaal twee kinderen heeft. |
| In BST bestaat er geen term, zoals balansfactor. | In de AVL-boom bevat elk knooppunt een balansfactor en de waarde van de balansfactor moet -1, 0 of 1 zijn. |
| Elke binaire zoekboom is geen AVL-boom omdat BST een gebalanceerde of een ongebalanceerde boom kan zijn. | Elke AVL-boom is een binaire zoekboom omdat de AVL-boom de eigenschap van de BST volgt. |
| Elk knooppunt in de binaire zoekboom bestaat uit drie velden, d.w.z. de linker subboom, de knooppuntwaarde en de rechter subboom. | Elk knooppunt in de AVL-boom bestaat uit vier velden, d.w.z. de linker subboom, de knooppuntwaarde, de rechter subboom en de balansfactor. |
| Als we in het geval van de binaire zoekboom een knooppunt in de boom willen invoegen, vergelijken we de knooppuntwaarde met de wortelwaarde; als de waarde van het knooppunt groter is dan de waarde van het hoofdknooppunt, wordt het knooppunt in de rechter subboom ingevoegd, anders wordt het knooppunt in de linker subboom ingevoegd. Zodra het knooppunt is ingevoegd, hoeft de hoogtebalansfactor niet te worden gecontroleerd om het inbrengen te voltooien. | In het geval van de AVL-boom zullen we eerst de geschikte plaats vinden om het knooppunt in te voegen. Zodra het knooppunt is ingevoegd, berekenen we de balansfactor van elk knooppunt. Als aan de balansfactor van elk knooppunt is voldaan, is het invoegen voltooid. Als de balansfactor groter is dan 1, moeten we enkele rotaties uitvoeren om de boom in evenwicht te brengen. |
| In de binaire zoekboom is de hoogte of diepte van de boom O(n), waarbij n het aantal knooppunten in de binaire zoekboom is. | In de AVL-boom is de hoogte of diepte van de boom O(logn). |
| Het is eenvoudig te implementeren omdat we de eigenschappen van Binary Search moeten volgen om het knooppunt in te voegen. | Het is complex om te implementeren omdat we in de AVL-boom eerst de AVL-boom moeten construeren en daarna de hoogtebalans moeten controleren. Als de hoogte onevenwichtig is, moeten we enkele rotaties uitvoeren om de boom in evenwicht te brengen. |
| BST is geen uitgebalanceerde boom omdat hij niet het concept van de balansfactor volgt. | De AVL-boom is een in hoogte gebalanceerde boom omdat hij het concept van de balansfactor volgt. |
| Zoeken is inefficiënt in BST als er een groot aantal knooppunten beschikbaar is in de boom, omdat de hoogte niet in evenwicht is. | Zoeken is efficiënt in de AVL-boom, zelfs als er een groot aantal knooppunten in de boom aanwezig is, omdat de hoogte in evenwicht is. |