Innan vi känner till skillnaderna mellan det binära sökträdet och AVL-trädet bör vi känna till det binära sökträdet och AVL-trädet separat.
Vad är ett binärt sökträd?
De binärt sökträd är en träd binärt träd. Som vi vet kan det trädet ha 'n' antal barn, medan; det binära trädet kan innehålla de yttersta två barnen. Så begränsningen för ett binärt träd följs också av det binära sökträdet. Varje nod i ett binärt sökträd bör ha de yttersta två barnen; med andra ord kan vi säga att det binära sökträdet är en variant av det binära trädet.
Det binära sökträdet följer också egenskaperna för den binära sökningen. I binär sökning måste alla element i en array vara i sorterad ordning. Vi beräknar mittelementet i den binära sökningen där den vänstra delen av mittelementet innehåller värdet som är mindre än mittvärdet, och den högra delen av mittelementet innehåller värden som är större än mittvärdet.
I Binary Search Tree blir mittelementet rotnoden, den högra delen blir det högra underträdet och den vänstra delen blir det vänstra underträdet. Därför kan vi säga att det binära sökträdet är en kombination av a binärt träd och binär sökning .
Obs: Binärt sökträd kan definieras som det binära trädet där alla element i det vänstra underträdet är mindre än rotnoden och alla element i det högra underträdet är större än rotnoden.
Tidskomplexitet i binärt sökträd
Om det binära sökträdet är nästan ett balanserat träd kommer alla operationer att ha en tidskomplexitet på O(logga) eftersom sökningen är uppdelad antingen till vänster eller höger underträd.
mockito när som helst
Om det binära sökträdet är antingen åt vänster eller höger, kommer alla operationer att ha samma tidskomplexitet som På) eftersom vi måste korsa till de n elementen.
Vad är AVL-trädet?
En AVL-träd är ett självbalanserande binärt sökträd där skillnaden mellan höjderna på vänster och höger underträd inte kan vara mer än ett. Denna skillnad är känd som en balansfaktor. I AVL-trädet kan balansfaktorns värde vara antingen -1, 0 eller 1.
Hur sker självbalanseringen av det binära sökträdet?
Som vi vet är AVL-trädet ett självbalanserande binärt sökträd. Om det binära sökträdet inte är balanserat kan det vara självbalanserat med några omarrangemang. Dessa omarrangemang kan göras med hjälp av vissa rotationer.
Låt oss förstå självbalansering genom ett exempel.
Anta att vi vill infoga 10, 20, 30 i ett AVL-träd.
Följande är sätten att infoga 10, 20, 30 i ett AVL-träd:
Steg 1: Först skapar vi ett binärt sökträd, som visas nedan:
java if-sats
Steg 2: I figuren ovan kan vi observera att trädet är obalanserat eftersom balansfaktorn för nod 30 är 2. För att göra det till ett AVL-träd måste vi utföra några rotationer. Om vi utför rätt rotation på nod 20 kommer noden 30 att röra sig nedåt, medan noden 20 kommer att röra sig uppåt, som visas nedan:
Som vi kan observera följer det sista trädet egenskapen för det binära sökträdet och ett balanserat träd; därför är det ett AVL-träd.
I fallet var trädet lämnade obalanserat träd, så vi utför rätt rotation på noden.
Steg 1: Först skapar vi ett binärt sökträd som visas nedan:
Steg 2: I figuren ovan kan vi observera att trädet är obalanserat eftersom balansfaktorn för nod 10 är -2. För att göra det till ett AVL-träd måste vi utföra några rotationer. Det är ett höger obalanserat träd, så vi kommer att utföra vänsterrotation. Om vi utför vänsterrotation på nod 20, kommer nod 20 att röra sig uppåt, och nod 10 kommer att röra sig nedåt, som visas nedan:
Som vi kan observera följer det sista trädet egenskapen till Binärt sökträd och a balanserat träd ; därför är det ett AVL-träd.
likvärdighetslagar
Steg 1: Först skapar vi det binära sökträdet som visas nedan:
Steg 2: I figuren ovan kan vi observera att trädet är obalanserat eftersom balansfaktorn för rotnoden är 2. För att göra det till ett AVL-träd måste vi utföra några rotationer. Ovanstående scenario är vänster-höger obalanserat eftersom en nod är till vänster om sin föräldernod och en annan är höger om sin föräldernod. Först kommer vi att utföra vänsterrotationen, och rotationen sker mellan noderna 10 och 20. Efter vänsterrotation kommer 20 att röra sig uppåt och 10 flyttas nedåt som visas nedan:
Ändå är trädet obalanserat, så vi utför rätt rotation på trädet. När rätt rotation har utförts på trädet vill trädet, som visas nedan:
Som vi kan observera i ovanstående träd, följer trädet egenskapen för det binära sökträdet och ett balanserat träd; därför är det ett AVL-träd.
Steg 1: Först skapar vi det binära sökträdet, som visas nedan:
Steg 2: I figuren ovan kan vi observera att trädet är obalanserat eftersom balansfaktorn för rotnoden är 2. För att göra det till ett AVL-träd måste vi utföra några rotationer. Ovanstående scenario är höger-vänster obalanserat eftersom en nod är höger om sin föräldernod, och en annan nod är vänster om sin föräldernod. Först kommer vi att utföra den rätta rotationen som sker mellan noderna 30 och 20. Efter högerrotation kommer 20 att röra sig uppåt och 30 kommer att röra sig nedåt som visas nedan:
Ändå är ovanstående träd obalanserat, så vi måste utföra vänsterrotation på noden. När vänsterrotationen väl har utförts kommer noden 20 att röra sig uppåt, och noden 10 kommer att flyttas nedåt som visas nedan:
Som vi kan observera i ovanstående träd, följer trädet egenskapen för det binära sökträdet och ett balanserat träd; därför är det ett AVL-träd.
Skillnader mellan binärt sökträd och AVL-träd
| Binärt sökträd | AVL-träd |
|---|---|
| Varje binärt sökträd är ett binärt träd eftersom båda träden innehåller de yttersta två barnen. | Varje AVL-träd är också ett binärt träd eftersom AVL-trädet också har de yttersta två barnen. |
| I BST finns det ingen term som existerar, såsom balansfaktor. | I AVL-trädet innehåller varje nod en balansfaktor, och värdet på balansfaktorn måste vara antingen -1, 0 eller 1. |
| Varje binärt sökträd är inte ett AVL-träd eftersom BST kan vara antingen ett balanserat eller ett obalanserat träd. | Varje AVL-träd är ett binärt sökträd eftersom AVL-trädet följer egenskapen för BST. |
| Varje nod i det binära sökträdet består av tre fält, dvs vänster underträd, nodvärde och höger underträd. | Varje nod i AVL-trädet består av fyra fält, dvs vänster underträd, nodvärde, höger underträd och balansfaktorn. |
| I fallet med binärt sökträd, om vi vill infoga någon nod i trädet så jämför vi nodvärdet med rotvärdet; om nodens värde är större än rotnodens värde så infogas noden i det högra underträdet annars infogas noden i det vänstra underträdet. När noden väl är införd finns det inget behov av att kontrollera höjdbalansfaktorn för att infogningen ska slutföras. | När det gäller AVL-träd kommer vi först att hitta den lämpliga platsen för att infoga noden. När noden har infogats kommer vi att beräkna balansfaktorn för varje nod. Om balansfaktorn för varje nod är uppfylld är insättningen klar. Om balansfaktorn är större än 1 måste vi utföra några rotationer för att balansera trädet. |
| I binärt sökträd är trädets höjd eller djup O(n) där n är antalet noder i det binära sökträdet. | I AVL-träd är trädets höjd eller djup O(logn). |
| Det är enkelt att implementera eftersom vi måste följa egenskaperna för binär sökning för att infoga noden. | Det är komplicerat att implementera eftersom vi i AVL-trädet först måste konstruera AVL-trädet och sedan måste vi kontrollera höjdbalansen. Om höjden är obalans måste vi utföra några rotationer för att balansera trädet. |
| BST är inte ett balanserat träd eftersom det inte följer konceptet med balansfaktorn. | AVL-träd är ett höjdbalanserat träd eftersom det följer konceptet med balansfaktorn. |
| Sökning är ineffektivt i BST när det finns ett stort antal noder tillgängliga i trädet eftersom höjden inte är balanserad. | Sökningen är effektiv i AVL-trädet även när det finns ett stort antal noder i trädet eftersom höjden är balanserad. |