TechCodeview

Før vi kender til forskellene mellem det binære søgetræ og AVL-træet, bør vi kende til det binære søgetræ og AVL-træet separat.

Hvad er et binært søgetræ?

Det binært søgetræ er en træ binært træ. Som vi ved, kan dette træ have 'n' antal børn, hvorimod; det binære træ kan indeholde de yderste to børn. Så begrænsningen af ​​et binært træ er også efterfulgt af det binære søgetræ. Hver node i et binært søgetræ skal have de yderste to børn; med andre ord kan vi sige, at det binære søgetræ er en variant af det binære træ.

Det binære søgetræ følger også egenskaberne for den binære søgning. I binær søgning skal alle elementer i et array være i sorteret rækkefølge. Vi beregner det midterste element i den binære søgning, hvor den venstre del af det midterste element indeholder værdien mindre end den midterste værdi, og den højre del af det midterste element indeholder værdierne større end den midterste værdi.

I binært søgetræ bliver det midterste element til rodknudepunktet, den højre del bliver det højre undertræ, og den venstre del bliver det venstre undertræ. Derfor kan vi sige, at det binære søgetræ er en kombination af en binært træ og binær søgning .

Bemærk: Binært søgetræ kan defineres som det binære træ, hvor alle elementerne i det venstre undertræ er mindre end rodnoden, og alle elementerne i det højre undertræ er større end rodknuden.

Tidskompleksitet i binært søgetræ

Hvis det binære søgetræ næsten er et balanceret træ, vil alle operationer have en tidskompleksitet på O(logn) fordi søgningen er opdelt enten til venstre eller højre undertræ.

hvordan man åbner en fil med java

Hvis det binære søgetræ er enten venstre eller højre skævt, så vil alle operationer have den tidskompleksitet som På) fordi vi skal krydse indtil de n elementer.

Hvad er AVL-træet?

An AVL træ er et selvbalancerende binært søgetræ, hvor forskellen mellem højden af ​​venstre og højre undertræ ikke kan være mere end én. Denne forskel er kendt som en balancefaktor. I AVL-træet kan værdierne af balancefaktor være enten -1, 0 eller 1.

Hvordan sker selvbalanceringen af ​​det binære søgetræ?

Som vi ved, er AVL-træet et selvbalancerende binært søgetræ. Hvis det binære søgetræ ikke er afbalanceret, kan det være selvbalanceret med nogle omarrangeringer. Disse omarrangeringer kan udføres ved hjælp af nogle rotationer.

Lad os forstå selvbalancering gennem et eksempel.

forårsstøvle annotationer

Antag, at vi vil indsætte 10, 20, 30 i et AVL-træ.

Følgende er måderne at indsætte 10, 20, 30 i et AVL-træ:

Hvis rækkefølgen af ​​indsættelse er 30, 20, 10.

Trin 1: Først opretter vi et binært søgetræ, som vist nedenfor:

Trin 2: I ovenstående figur kan vi observere, at træet er ubalanceret, fordi balancefaktoren for node 30 er 2. For at gøre det til et AVL-træ skal vi udføre nogle rotationer. Hvis vi udfører den rigtige rotation på node 20, vil node 30 bevæge sig nedad, mens node 20 vil bevæge sig opad, som vist nedenfor:

Som vi kan observere, følger det endelige træ egenskaben for det binære søgetræ og et balanceret træ; derfor er det et AVL-træ.

I sagen var træet venstre ubalanceret træ, så vi udfører den rigtige rotation på noden.

Hvis rækkefølgen af ​​indsættelse er 10, 20, 30.

Trin 1: Først opretter vi et binært søgetræ som vist nedenfor:

Trin 2: I ovenstående figur kan vi observere, at træet er ubalanceret, fordi balancefaktoren for node 10 er -2. For at gøre det til et AVL-træ skal vi udføre nogle rotationer. Det er et højre ubalanceret træ, så vi vil udføre venstrerotation. Hvis vi udfører venstrerotation på node 20, så vil node 20 bevæge sig opad, og node 10 vil bevæge sig nedad, som vist nedenfor:

Som vi kan observere, følger det endelige træ ejendommens ejendom Binært søgetræ og en balanceret træ ; derfor er det et AVL-træ.

Hvis rækkefølgen af ​​indsættelse er 30, 10, 20

Trin 1: Først opretter vi det binære søgetræ som vist nedenfor:

Trin 2: I ovenstående figur kan vi observere, at træet er ubalanceret, fordi balancefaktoren for rodknuden er 2. For at gøre det til et AVL-træ skal vi udføre nogle rotationer. Ovenstående scenarie er venstre-højre ubalanceret, da en node er til venstre for sin overordnede node, og en anden er til højre for sin overordnede node. Først vil vi udføre den venstre rotation, og rotationen sker mellem noderne 10 og 20. Efter venstre rotation vil 20 bevæge sig opad, og 10 vil bevæge sig nedad som vist nedenfor:

Alligevel er træet ubalanceret, så vi udfører den rigtige rotation på træet. Når den rigtige rotation er udført på træet, vil træet gerne, som vist nedenfor:

Som vi kan observere i ovenstående træ, følger træet egenskaben for det binære søgetræ og et balanceret træ; derfor er det et AVL-træ.

Hvis rækkefølgen af ​​indsættelsen er 10, 30, 20

Trin 1: Først opretter vi det binære søgetræ, som vist nedenfor:

Trin 2: I ovenstående figur kan vi observere, at træet er ubalanceret, fordi balancefaktoren for rodknuden er 2. For at gøre det til et AVL-træ skal vi udføre nogle rotationer. Ovenstående scenarie er højre-venstre ubalanceret, da en node er til højre for sin overordnede node, og en anden node er til venstre for sin overordnede node. Først vil vi udføre den rigtige rotation, der sker mellem noderne 30 og 20. Efter højre rotation vil 20 bevæge sig opad, og 30 vil bevæge sig nedad som vist nedenfor:

10 ml er hvor meget

Alligevel er ovenstående træ ubalanceret, så vi skal udføre venstrerotation på noden. Når den venstre rotation er udført, vil knudepunktet 20 bevæge sig opad, og knudepunktet 10 vil bevæge sig nedad som vist nedenfor:

Som vi kan observere i ovenstående træ, følger træet egenskaben for det binære søgetræ og et balanceret træ; derfor er det et AVL-træ.

Forskelle mellem binært søgetræ og AVL-træ