Definitie van een gebalanceerde boom

Ik vraag me gewoon af of iemand misschien de definitie van een gebalanceerde boom voor mij kan verduidelijken. Ik heb dat “een boom in evenwicht is als elke subboom in evenwicht is en de hoogte van de twee subbomen verschilt door maximaal één.

Mijn excuses als dit een domme vraag is, maar is deze definitie van toepassing op elk knooppunt helemaal naar beneden naar de bladeren van een boom of alleen naar de linker- en rechter onderbomen onmiddellijk van de root? Ik vermoed dat een andere manier om dit te frame zou zijn, is het mogelijk voor interne knooppunten van een boom om onevenwichtig te zijn en de hele boom om evenwichtig te blijven?

Antwoord 1, Autoriteit 100%

De beperking wordt over het algemeen recursief toegepast op elke substructuur. Dat wil zeggen, de boom is alleen evenwichtig als:

1. De hoogtes van de linker en rechter substructuur verschillen in de meeste, en
2. De linker substructuur is gebalanceerd en
3. De juiste subtree is gebalanceerd

Volgens deze is de volgende boom gebalanceerd:

    A
   /   \
  B     C  
 /     / \  
D     E   F  
     /  
    G  

De volgende is niet in evenwicht, omdat de subbomen van C verschillen met 2 in hun lengte:

    A
   /   \
  B     C   <-- difference = 2
 /     /
D     E  
     /  
    G  

Dat gezegd hebbende, is de specifieke beperking van het eerste punt afhankelijk van het type boom. De hierboven vermelde bovenstaande is het typisch voor AVL-bomen .

rood-zwarte bomen , bijvoorbeeld, een zachtere beperking opleggen.

Antwoord 2, Autoriteit 43%

Er zijn verschillende manieren om “evenwichtig” te definiëren. Het hoofddoel is om de diepten van alle knooppunten te behouden als O(log(n)).

Het lijkt mij dat de balansvoorwaarde waar u het over had voor AVL-boomis.
Hier is de formele definitie van de balansconditie van de AVL-boom:

Voor elk knooppunt in AVL verschilt de hoogte van de linker subboom maximaal1 van de hoogte van de rechter subboom.

Volgende vraag, wat is “hoogte“?

De “hoogte” van een knoop in een binaire boom is de lengte van het langste pad van die knoop naar een blad.

Er is één raar maar veelvoorkomend geval:

Mensen definiëren de hoogte van een lege boom als (-1).

Het linker kind van root is bijvoorbeeld null:

             A  (Height = 2)
           /     \
(height =-1)       B (Height = 1) <-- Unbalanced because 1-(-1)=2 >1
                    \
                     C (Height = 0)

Nog twee voorbeelden om te bepalen:

Ja, Een evenwichtige boomVoorbeeld:

       A (h=3)
     /     \
 B(h=1)     C (h=2)        
/          /   \
D (h=0)  E(h=0)  F (h=1)
               /
              G (h=0)

Nee, Geen evenwichtige boomVoorbeeld:

       A (h=3)
     /     \
 B(h=0)     C (h=2)        <-- Unbalanced: 2-0 =2 > 1
           /   \
        E(h=1)  F (h=0)
        /     \
      H (h=0)   G (h=0)      

Antwoord 3, autoriteit 7%

Er is geen verschil tussen deze twee dingen. Denk er eens over na.

Laten we een eenvoudigere definitie nemen: “Een positief getal is even als het nul is of dat getal min twee even.” Zegt dit dat 8 even is als 6 even is? Of zegt dit dat 8 even is als 6, 4, 2 en 0 even zijn?

Er is geen verschil. Als er staat dat 8 even is als 6 even is, staat er ook 6 is even als 4 even is. En dus staat er ook dat 4 even is als 2 even is. En dus staat er dat 2 even is als 0 even is. Dus als er staat dat 8 even is als 6 even is, zegt het (indirect) dat 8 even is als 6, 4, 2 en 0 even zijn.

Het is hier hetzelfde. Elke indirecte sub-boom kan worden gevonden door een keten van directe sub-bomen. Dus zelfs als het alleen direct van toepassing is op directe sub-bomen, is het nog steeds indirect van toepassing op alle sub-bomen (en dus alle knooppunten).

Antwoord 4, autoriteit 3%

Gebalanceerde boom is een boom waarvan de hoogte in de orde van log is (aantal elementen in de boom).

height = O(log(n))
O, as in asymptotic notation i.e. height should have same or lower asymptotic
growth rate than log(n)
n: number of elements in the tree

De gegeven definitie “een boom is gebalanceerd, elke subboom is gebalanceerd en de hoogte van de twee subbomen verschilt met maximaal één” wordt gevolgd door AVL-bomen.

Aangezien AVL-bomen gebalanceerd zijn, maar niet alle gebalanceerde bomen AVL-bomen zijn, hebben gebalanceerde bomen deze definitie niet en kunnen interne knooppunten daarin uit balans zijn. AVL-bomen vereisen echter dat alle interne knooppunten in evenwicht zijn.

Antwoord 5, autoriteit 2%

Het doel van een uitgebalanceerde boom is om het blad te bereiken in een minimale beweging (minimale hoogte).
De graad van de boom is het aantal takken min 1.
Een gebalanceerde boom is mogelijk niet binair.

Antwoord 6

1. De hoogte van een knooppunt in een boom is de lengte van het langste pad van dat knooppunt naar beneden naar een blad, waarbij zowel de begin- als de eindpunten van het pad worden geteld.
2. Een knoop in een boom is in hoogte uitgebalanceerd als de hoogte van zijn subbomen niet meer dan 1 verschilt.
3. Een boom is in hoogte uitgebalanceerd als alle knooppunten in hoogte uitgebalanceerd zijn.