Co je binární strom?

Binární strom je typ datové struktury používané v počítačovém programování k ukládání, třídění a přístupu k informacím. Binární stromy jsou nejjednodušší paletou stromů, ale jsou velmi užitečné a snadno implementovatelné. Typická implementace binárního stromu se spoléhá na kořenový uzel spojený s řadou uzlů, které tvoří samotný strom pomocí proměnných ukazatele. Tento typ stromu vychází ze skutečnosti, že žádný uzel ve stromu nemůže mít více než dvě děti.

Struktury stromových dat přicházejí v mnoha variantách. Jsou tvořeny různými uzly, které jsou uspořádány v hierarchickém vzoru. Jeden uzel, kořen, je přístupový bod, skrz který lze prohledávat nebo jinak manipulovat celý datový strom. Tento kořenový uzel ukazuje na horní uzel uvnitř samotného stromu.

Každý uzel ve stromu, s výjimkou nejvyššího uzlu, bude mít nadřazený uzel, který je umístěn nad ním v hierarchii stromu. Může mít také podřízené uzly, které jsou umístěny pod ním. K danému uzlu se přistupuje přes ty nad ním ve stromu a poskytuje přístup k těm pod ním.

Datové struktury binárních stromů umožňují, aby každý uzel neměl více než dvě děti. Daný uzel tak může mít připojený nulový, jeden nebo dva podřízené uzly. Obyčejné binární stromy umožňují uzly s libovolným počtem dětí v libovolném bodě stromu. Rovněž neukládají žádná omezení týkající se uspořádání hodnot uložených v uzlech, které tvoří strom.

Datové struktury jsou nejužitečnější, když zvyšují rychlost, s jakou mohou počítače přistupovat k datům, a ke zlepšení jejich účinnosti se používají modifikované verze binárních stromů. Binární vyhledávací strom je takový, ve kterém všechny datové hodnoty umístěné na levé sestupné větvi z daného uzlu mají hodnoty, které jsou stejné nebo menší než hodnota uložená v tomto uzlu. Hodnoty na pravé straně uzlu v uspořádaném binárním stromu musí být naopak větší než hodnota v základním uzlu. Toto řazení dat umožňuje psaní mnohem účinnějšího vyhledávacího algoritmu.

Tvar binárního stromu je také důležitý při určování účinnosti vyhledávacího algoritmu. Nejméně účinná rozmanitost binárního stromu je taková, ve které má každý uzel pouze jediné dítě. Počítač může potřebovat prozkoumat každou položku dat v celém stromu, aby v této konfiguraci našel jednu informaci. Naopak nejúčinnějším binárním stromem je ten, ve kterém má každý uzel kromě těch ve spodní části stromu dvě děti a kde všechny uzly listů, spodní uzly ve stromu, jsou ve stejné vzdálenosti od kořene.