Pilnīgs binārs koks vs pilns binārs koks
Binārais koks ir koks, kurā katrā mezglā ir viens vai divi bērni. Binārajā kokā mezglā nevar būt vairāk par diviem bērniem. Binārajā kokā bērni tiek nosaukti par “kreisajiem” un “labajiem” bērniem. Bērna mezglos ir atsauce uz vecākiem. Pilnīgs binārs koks ir binārs koks, kurā visi binārā koka līmeņi ir pilnībā aizpildīti, izņemot pēdējo līmeni. Neaizpildītā līmenī mezgli tiek piestiprināti, sākot no kreisās puses. Pilns binārs koks ir koks, kurā katrā koka mezglā ir divi bērni, izņemot koka lapas.
Kas ir pilns binārs koks?
Pilns binārs koks ir binārs koks, kurā katrā koka mezglā ir tieši nulle vai divi bērni. Citiem vārdiem sakot, katrā koka mezglā, izņemot lapas, ir tieši divi bērni. 1. attēlā attēlots pilns binārs koks. Pilnā binārā kokā mezglu skaits (n), laukumu skaits (l) un iekšējo mezglu skaits (i) ir saistīts īpašā veidā tā, ka, ja jūs zināt kādu no tiem, jūs varat noteikt pārējos divus vērtības ir šādas:
1. Ja pilnam bināram kokam ir i iekšējie mezgli:
- lapu skaits l = i + 1
- kopējais mezglu skaits n = 2 * i + 1
2. Ja pilnam bināram kokam ir n mezglu:
- iekšējo mezglu skaits i = (n-1) / 2
- lapu skaits l = (n + 1) / 2
3. Ja pilnam bināram kokam ir l lapas:
- kopējais mezglu skaits n = 2 * l-1
- Iekšējo mezglu skaits i = l-1
Kas ir pilnīgs binārs koks?
Kā parādīts 2. attēlā, pilnīgs binārs koks ir binārs koks, kurā visi koka līmeņi ir pilnībā aizpildīti, izņemot pēdējo līmeni. Arī pēdējā līmenī mezgli jāpiestiprina, sākot no kreisās puses. Pilns binārs koks ar augstumu h atbilst šādiem nosacījumiem:
- No saknes mezgla līmenis virs pēdējā līmeņa apzīmē pilnu bināru koku ar augstumu h-1
- Vienā vai vairākos mezglos pēdējā līmenī var būt 0 vai 1 bērns
- Ja a, b ir divi mezgli līmenī virs pēdējā līmeņa, tad a ir vairāk bērnu nekā b tikai tad, ja a atrodas pa kreisi no b
Kāda ir atšķirība starp pilno bināro koku un pilnu bināro koku?
Pilnīgiem binārajiem kokiem un pilnajiem binārajiem kokiem ir skaidra atšķirība. Kamēr pilns binārs koks ir binārs koks, kurā katram mezglam ir nulle vai divi bērni, pilnīgs binārs koks ir binārs koks, kurā visi binārā koka līmeņi ir pilnībā aizpildīti, izņemot pēdējo līmeni. Dažām īpašām datu struktūrām, piemēram, kaudzēm, jābūt pilnīgi bināriem kokiem, kamēr tām nav jābūt pilnīgiem bināriem kokiem. Pilnā binārā kokā, ja jūs zināt kopējo mezglu skaitu vai laves vai iekšējo mezglu skaitu, pārējos divus varat atrast ļoti viegli. Bet pilnīgam binārajam kokam nav īpašas īpašības, kas saistītu trīs atribūtus.
