Lekce 6 - Binární vyhledávací strom (BST)

V minulé lekci, Vyhledávání řetězce v textu, jsme se podívali na efektivní způsob, jak ve velkých datech vyhledávat řetězec, aneb hledat jehlu v kupce sena.

Rád bych rychle zopakoval, že v článku Binární vyhledávání jsme zjistili, že pokud si udržujeme data(prvky) v setříděném poli (kde jsou vlevo nejmenší prvky a vpravo prvky největší), můžeme pak určitý prvek nalézt v čase log n, když se vždy podíváme na prvek doprostřed pole a pokud je námi hledaný prvek větší (resp. menší), víme, že v té levé (resp. pravé) polovině už být nemůže a tak ji celou zahodíme. Tím se nám pole o polovinu zmenší a my pokračujeme znovu. Tento velmi rychlý algoritmus má jediný problém - musíme si pole udržovat setříděné. Pokud chceme do pole vložit nový prvek, musíme ho vložit přesně tam, kam podle velikosti patří. A vložení prvku někam dovnitř pole vyžaduje zvětšení pole o 1 a přesunutí prvků po jednom doprava, aby na nový prvek vzniklo místo a mohl být vložen. Pokud je pole velké milion prvků a my chceme vložit prvek doprostřed, musíme udělat půl milionu posunů doprava, což není zrovna levná operace.

Kdybychom používali spojový seznam, prvky do pole bychom vkládali v konstantním čase, ale bohužel bychom ztratili rychlý přístup k indexům, které pole nabízí. Existuje však struktura, které se říká Binární vyhledávací strom. Ta umožňuje rychlé vkládání prvků díky využívání ukazatelů (referencí) a zároveň si můžeme dovolit odhazovat nepotřebnou část struktury v každém kroku podobně, jako to bylo v binárním vyhledávání.

Binární vyhledávací strom

Binární vyhledávací strom (BST - Binary Search Tree) má následující vlastnosti:

...konec náhledu článku...
Pokračuj dál