Binární strom
Kategorie: Nezařazeno (celkem: 23179 referátů a seminárek)
Informace o referátu:
- Přidal/a: anonymous
- Datum přidání: 12. srpna 2008
- Zobrazeno: 1868×
Příbuzná témata
Binární strom
Binární strom je pojem z teorie grafů a zároveň datová struktura, používaná k ukládání a vyhledávání dat v počítačích.
Binární strom je strom ve smyslu používaném v teorii grafů. Jedná se o orientovaný graf s jedním vrcholem (kořenem), z něhož existuje cesta do všech vrcholů grafu. Každý vrchol binárního stromu může mít maximálně dva orientované syny a s výjimkou kořene právě jednoho předka. Kořen předka nemá.
V praktickém programování je obvykle binární strom reprezentován dvěma způsoby:
- pomocí dynamické struktury, kde jsou hrany reprezentovány ukazateli. Takto se reprezentuje například AVL-strom
- pomocí pole, kde prvek s indexem i má následníky s indexem 2i a 2i+1 (za předpokladu, že pole je indexováno od 1). Takto je například reprezentovaná halda v algoritmu heapsort.
Binární strom je nejčastěji používán jako binární vyhledávací strom a halda.