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
Došel jsi až sem a to je super! Věříme, že ti první lekce ukázaly něco nového a užitečného.
Chceš v kurzu pokračovat? Přejdi do prémiové sekce.
Koupit tento kurz
Obsah článku spadá pod licenci Premium, koupí článku souhlasíš se smluvními podmínkami.
- Neomezený a trvalý přístup k jednotlivým lekcím.
- Kvalitní znalosti v oblasti IT.
- Dovednosti, které ti pomohou získat vysněnou a dobře placenou práci.
Popis článku
Požadovaný článek má následující obsah:
Popis algoritmu vyhledávací struktury binární vyhledávací strom (BST) s obrázky a teorií. Vkládání, vyhledávání a mazání, časová složitost.
Kredity získáš, když podpoříš naši síť. To můžeš udělat buď zasláním symbolické částky na podporu provozu nebo přidáním obsahu na síť.
David se informační technologie naučil na Unicorn University - prestižní soukromé vysoké škole IT a ekonomie.