Co je to binární strom?

Binární strom je typ datové struktury používané v programování počítače k ​​ukládání, třídění a přístupu k informacím. Binární stromy jsou nejjednodušší rozmanitost 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í ukazatelských proměnných. Tento typ stromu odvozuje jeho název ze skutečnosti, že žádný uzel uvnitř stromu nemůže mít více než dvě děti.

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

Jakýkoli 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é dětské uzly, které jsou umístěny pod ním. Daný uzel je AcceSses skrz ty nad ním ve stromu a poskytuje přístup k těm pod ním.

Struktury dat binárních stromů umožňují každému uzlu mít více než dvě děti. Daný uzel tedy může mít nulu, jeden nebo dva dětské uzly k němu. Obyčejné binární stromy umožňují uzly s libovolným počtem dětí v kterémkoli bodě stromu. Rovněž neumítají žádná omezení, jak jsou uspořádány hodnoty uložené v uzlech, které obsahují strom.

datové struktury jsou nejužitečnější, když zlepšují rychlost, ke které lze data přistupovat pomocí počítače, a ke zlepšení jejich účinnosti se používají modifikované verze binárních stromů. Binární vyhledávací strom je ten, ve kterém všechny hodnoty dat umístěné na levém sestupném větev z daného uzlu mají hodnoty, které jsou stejné nebo méně než hodnota uložená v tomto uzlu. Hodnoty na pravé straně uzlu v uspořádaném binárním stromu musí být zase větší než hodnota vzákladní uzel. Toto uspořádání dat umožňuje napsat mnohem efektivnější vyhledávací algoritmus.

Tvar binárního stromu je také důležitý při určování účinnosti algoritmu vyhledávání. Nejméně efektivní rozmanitost binárního stromu je ten, ve kterém má každý uzel pouze jediné dítě. Počítač bude možná muset prozkoumat každou položku dat v celém stromu, aby v této konfiguraci vyhledal jednu informaci. Naproti tomu nejúčinnější binární strom je ten, ve kterém každý uzel s výjimkou těch ve spodní části stromu má dvě děti a kde všechny uzly listů, spodní uzly ve stromu, jsou ve stejné vzdálenosti od kořene.