Časté vzory vo stromu algoritmov

Dáta sú bežne uložené v binárny strom štruktúr pomocou špeciálnych algoritmov . Mnoho výhod pochádzajú z ukladania dát v stromovej štruktúre . Napríklad vyhľadávanie objednaný binárny strom je oveľa rýchlejší ako triedenie sekvenčné dátové štruktúry ako je pole . Stromová štruktúra dát možno predpokladať , veľa druhov vzorov v priebehu prístup k dátam a modifikácie . Pochopenie týchto modelov vám môžu pomôcť navrhnúť lepšie algoritmy pre optimalizáciu strom algoritmus . Základné komponenty Binárny strom

binárny strom sa skladá z uzlov , ktoré sa ukladajú dáta a prejdite do iných uzlov v strome . Koreň je východiskovým bodom stromu a zaujíma najvyššie úrovne . To môže mať až dve podriadené uzly . Tieto podriadené uzly môžu mať tiež až dve podriadené uzly . Počet podriadených uzlov daného uzla sa nazýva stupeň uzla . Uzol bez detí , a stupeň nula , sa nazýva list . Dĺžka v uzloch z koreňového uzla na najvzdialenejšie uzla , je výška stromu . Hĺbka uzla je vzdialenosť od koreňového uzla na neho . Každý uzol , ktorý má rovnakú hĺbku je povedal , aby bol na rovnakej úrovni .
Plný Binárny strom

plný binárny strom je strom , v ktorom každý uzol má presne dve alebo nulové deti . Inými slovami , každý uzol má buď dve deti , alebo je list . Príklad úplného binárneho stromu je binárny rozhodnutie diagram , alebo BDD .
Perfect Binárny strom

perfektný binárny strom má rovnaké vlastnosti kompletné binárny strom , ale všetky koncové uzly sú na rovnakej úrovni , čo znamená , že hĺbka všetkých listov je rovnaký v dokonalom binárneho stromu . Vzhľadom k tomu , že je tiež plný binárny strom , všetky uzly s výnimkou koncové uzly majú stupeň 2.
Balanced Binary Tree

vyvážený binárny strom je ten , v ktorom hĺbka každého uzla , je rovnaký alebo sa líšia o hodnotu jedna . Pridávanie a odoberanie uzlov z vyváženého binárneho stromu môže destabilizovať , takže rad úprav tzv rotácie sa musí konať do budúcna prehodnotiť strom . Vedenie strom vyvážený zaručuje , že priemerný čas vyhľadávania ľubovoľného uzla je optimálny . Významné réžia je nutné zachovať rovnováhu stromu .
Degenerate Binárny strom

zvrhlík binárny strom je ten , v ktorom každý uzol okrem uzla listu má presne jeden podriadený uzol . To má rovnaké výkonové charakteristiky spájať zoznam , ktorý zvyšuje vyhľadávací čas pre každý uzol značné množstvo . Napríklad , zvažovať prípad , v ktorom uzol je hľadal je koncový uzol . Celý strom musí byť previazaný s cieľom nájsť tento uzol . S vyváženú binárneho stromu , nájsť uzol list vyžaduje len niekoľko uzlov pre prechod , ktorý sa rovná hĺbke uzla listu . U veľkých stromov , môže rozdiel vo výkone je významný .

• Predchádzajúca strana: Ako zistiť Orthagonal v 3D Vector . 
• Ďalšia strana: Čo znamená Neplatná syntax stredná