Binární strom

Z Wikipedie, otevřené encyklopedie

Jednoduchý binární strom
Jednoduchý 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. 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:

  1. Dynamická struktura, kde jsou hrany reprezentovány ukazateli. Takto se reprezentuje například AVL-strom
  2. 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.