Definícia úplného binárneho stromu je "Aúplný binárny strom je binárny strom, v ktorom je každá úroveň, s výnimkou prípadnej poslednej, úplne naplnená a všetky uzly sú čo najobľúbenejšie. "Chcel som vedieť, prečo je možné čiastočne naplniť poslednú úroveň. v niektorých situáciách / prípadoch?
Pokúsil som sa nájsť odpoveď na túto otázku na mnohých miestach, ale nebol som schopný nájsť uspokojivú odpoveď.Môže mi niekto pomôcť tým, že odpovie na to.
odpovede:
2 pre odpoveď č. 1Iné riešenie tejto otázky než iná odpoveď: Ak by všetky úrovne museli byť úplne vyplnené, mohli by ste mať iba stromy (2^n)-1 prvky pre niektorých n, Tj. 1, 3, 7, 15, ... prvkov. Povolením čiastočnej plnenia poslednej úrovne môžete mať binárne stromy s ľubovoľným počtom prvkov.
1 pre odpoveď č. 2
To je len definícia úplného binárneho stromu, ktorý nemusí nevyhnutne pomôcť ani brániť ničomu, je to tak, ako to je.
Ak sa o túto tému zaujímate, pozrite savyvážené binárne stromy. Tam je rozumné mať len najnižšie úrovne, ktoré nie sú úplne vyplnené, aby sa zabezpečilo, že strom je vyrovnaný a nemáte 10 uzlov hlbokú ľavú stranu a 1 uzol hlbokú pravú stranu.
Majú všetky úrovne stromov úplneplná pomoc vám zaručuje rýchle vyhľadávanie. Ak sú všetky úrovne úplne naplnené, viete, že hĺbka stromu je rovnaká na všetkých možných cestách, a preto vám zabezpečí dobrú hornú hranicu rýchlosti vyhľadávania. V takýchto prípadoch môžete vypočítať hĺbku všetkých možných ciest uzla listov D = floor(lg(N)), kde N je počet uzlov.
Teraz si predstavte, či nemusíte mať naplnené úrovne. Mohli by ste mať niečo také, ako je táto monstrozita, kde niektoré prvky budú prenesené oveľa rýchlejšie ako ostatné.
