Binární strom
Z Wikipedie, otevřené encyklopedie
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. Z každého vrcholu binárního stromu smí vést maximálně dvě orientované hrany, do každého vrcholu s výjimkou kořene právě jedna orientovaná hrana vede. Do kořene nevede žádná hrana.
V praktickém programování je obvykle binární strom reprezentován dvěma způsoby:
- Dynamická struktura, kde jsou hrany reprezentovány ukazateli. Takto se reprezentuje například AVL-strom
- Pole, kde prvek s indexem i má následníky s indexem 2i a 2i+1. Takto je například reprezentovaná halda v algoritmu heapsort.
Binární strom je nejčastěji používán právě jako binární vyhledávací strom a halda.
