Průvodce pro binární stromy pro začátečníky

Pokud jste absolvovali kurz datových struktur v oboru počítačových věd nebo jste programátor samouk, je pravděpodobné, že jste se setkali s pojmem „binární stromy“. Ačkoli to může znít trochu zdrcujícím a složitým způsobem, koncept binárního stromu je docela jednoduchý.

Přečtěte si, jak rozebíráme binární stromy, a proč jsou nezbytným základním konceptem pro programátory.

Co jsou binární stromy?

Binární stromy patří mezi jednu z prvních datových struktur, které jsou studenti vyučováni v kurzu datových struktur. Binární strom je vytvořen z mnoha uzlů a každý uzel binárního stromu obsahuje dva ukazatele, které označují levý a pravý podřízený datový uzel.

První uzel v binárním stromu se nazývá „root“. Uzly poslední úrovně ve stromu se nazývají listy.

Každý uzel obsahuje datovou položku a dva ukazatele uzlu. Prázdný binární strom je reprezentován nulovým ukazatelem. Jak jste již možná zjistili, binární stromy mohou mít pouze dvě děti (odtud název).

Typy binárních stromových struktur

Existuje několik různých binárních stromových struktur v závislosti na způsobu umístění uzlů. Binární strom se nazývá úplný binární strom, pokud má každý uzel ve stromu buď nulu, nebo dvě podřízené položky. V dokonalém binárním stromu mají všechny uzly dvě děti a listy jsou ve stejné hloubce.

Příbuzný: Nejlepší způsoby, jak se naučit kódovat zdarma

Kompletní binární strom má uzly vyplněné v každé úrovni, s výjimkou poslední úrovně. U úplných binárních stromů jsou uzly soustředěny na levé straně kořene. Další běžnou strukturou je vyvážený binární strom; v této struktuře se výšky pravého a levého podstromu musí lišit maximálně o jeden. Je také nutné, aby byl vyvážen také levý a pravý podstrom.

Je důležité si uvědomit, že výška vyváženého binárního stromu je O (logn), kde n je počet uzlů ve stromu.

V některých případech, pokud má každý uzel pouze jedno levé nebo pravé dítě, pak se z binárního stromu může stát zkosený binární strom. Poté se bude chovat jako propojený seznam, těmto stromům se také říká degenerovaný strom.

Co jsou binární vyhledávací stromy?

Binární vyhledávací strom (BST) je v podstatě uspořádaný binární strom se speciální vlastností známou jako vlastnost „binární vyhledávací strom“. Vlastnost BST znamená, že uzly s klíčovou hodnotou menší než kořen jsou umístěny v levém podstromu a uzly s klíčovou hodnotou větší než kořen jsou součástí pravého podstromu.

Vlastnost BST musí být pravdivá pro každý následující nadřazený uzel ve stromu.

Binární vyhledávací stromy nabízejí rychlé vkládání a vyhledávání. Operace vkládání, mazání a vyhledávání mají nejhorší časovou složitost O (n), která je podobná propojenému seznamu.

Výhody binárních stromů

Binární stromy nabízejí mnoho výhod, a proto zůstávají velmi užitečnou datovou strukturou. Lze je použít k zobrazení strukturálních vztahů a hierarchií v datové sadě. Ještě důležitější je, že binární stromy umožňují efektivní vyhledávání, mazání a vkládání.

Je také velmi snadné implementovat a udržovat binární strom. Binární strom nabízí programátorům výhody uspořádaného pole a propojeného seznamu; vyhledávání v binárním stromu je stejně rychlé jako v tříděném poli a operace vkládání nebo mazání jsou stejně účinné jako v propojených seznamech.

Binární stromy jsou důležité datové struktury

Binární stromy jsou velmi důležitou datovou strukturou a je velmi důležité, aby je programátoři mohli pohodlně používat ve svých programech. Tazatelé se často ptají na jednoduché problémy s binárními stromy, jako jsou procházení, maximální hloubka, zrcadlení atd.

Důrazně doporučujeme porozumět konceptu binárních stromů a seznámit se s typickými problémy při pohovorech.

TreeViz: Jednoduchý způsob vizualizace datových struktur

Číst dále

O autorovi