Pilnīgs binārais koks pret pilnu bināro koku
Binārais koks ir koks, kurā katram mezglam ir viens vai divi bērni. Binārajā kokā mezglam nevar būt vairāk par diviem bērniem. Binārajā kokā bērni tiek nosaukti kā “kreisie” un “labie” bērni. Pakārtotie mezgli satur atsauci uz viņu vecāku. Pilnīgs binārais koks ir binārais koks, kurā katrs binārā koka līmenis ir pilnībā aizpildīts, izņemot pēdējo līmeni. Neaizpildītā līmenī mezgli tiek piestiprināti, sākot no vistālāk kreisās pozīcijas. Pilns binārais koks ir koks, kurā katram koka mezglam ir divi bērni, izņemot koka lapas.
Kas ir pilns binārais koks?
Pilns binārais koks ir binārs koks, kurā katram koka mezglam ir tieši nulle vai divi bērni. Citiem vārdiem sakot, katram koka mezglam, izņemot lapas, ir tieši divi bērni. 1. attēlā zemāk ir attēlots pilns binārais koks. Pilnā binārajā kokā mezglu skaits (n), lāpju skaits (l) un iekšējo mezglu skaits (i) ir saistīti īpašā veidā tā, ka, ja zināt kādu no tiem, varat noteikt pārējos divus vērtības šādi:
1. Ja pilnam binārajam kokam ir iekšējie mezgli:
– Lapu skaits l=i+1
– kopējais mezglu skaits n=2i+1
2. Ja pilnam binārajam kokam ir n mezgli:
– 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=2l-1
– iekšējo mezglu skaits i=l-1
Kas ir pilnīgs binārais koks?
Kā parādīts 2. attēlā, pilnīgs binārais koks ir binārs koks, kurā katrs koka līmenis ir pilnībā aizpildīts, izņemot pēdējo līmeni. Arī pēdējā līmenī mezgli jāpievieno, sākot no vistālāk kreisās pozīcijas. Pilns binārais koks ar augstumu h atbilst šādiem nosacījumiem:
– No saknes mezgla līmenis virs pēdējā līmeņa apzīmē pilnu bināro koku ar augstumu h-1
– Vienam vai vairākiem pēdējā līmeņa mezgliem 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 tad un tikai tad, ja a atrodas pa kreisi no b
Kāda ir atšķirība starp pilno bināro koku un pilno bināro koku?
Pilnajiem binārajiem kokiem un pilnajiem binārajiem kokiem ir skaidra atšķirība. Kamēr pilns binārais koks ir binārs koks, kurā katram mezglam ir nulle vai divi bērni, pilns binārais koks ir binārais 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, ir jābūt pilnīgiem bināriem kokiem, savukārt tiem nav jābūt pilnīgiem bināriem kokiem. Pilnā binārajā kokā, ja zināt kopējo mezglu skaitu vai lāpju skaitu vai iekšējo mezglu skaitu, jūs varat ļoti viegli atrast pārējos divus. Taču pilnīgam binārajam kokam nav īpašu īpašību, kas būtu saistīta ar šiem trim atribūtiem.
