Hledáme nové posily do ITnetwork týmu. Podívej se na volné pozice a přidej se do nejagilnější firmy na trhu - Více informací.
Pouze tento týden sleva až 80 % na e-learning týkající se Swiftu. Zároveň využij výhodnou slevovou akci až 30 % zdarma při nákupu e-learningu - více informací.
discount 30 + hiring

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

Znalosti v hodnotě stovek tisíc získáš za pár korun

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.

Omezená nabídka: Nauč se vše a ušetři

Koupit lekce a funkce postupně a po jednom 50 bodů
Koupit všechny aktuálně dostupné lekce s funkcí odevzdávání úloh za exkluzivní cenu 43 bodů (108 Kč)
Na svém účtu máš aktuálně 0 bodů
Koupí tohoto výhodného balíčku získáš přístup ke všem 15 lekcím s kontrolou a certifikací a ještě navíc ušetříš 18 Kč. Nabídka je omezená pouze pro první lekce z kurzu a obsahuje exkluzivní slevu 15%.
43 bodů získáš za přidání svého článku na síť nebo odpovídá 125 Kč 108 Kč

Pozor, pokud si koupíš pouze tuto lekci, ztratíš nárok na speciální slevu 15% na balíček všech lekcí.

Koupit jen lekci 10 bodů
Na svém účtu máš aktuálně 0 bodů
10 bodů získáš za přidání svého článku na síť nebo odpovídá 25 Kč

Obsah článku spadá pod licenci Premium, koupí článku souhlasíš se smluvními podmínkami.

Co od nás v dalších lekcích dostaneš?
  • 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.

Body 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íť.

Článek pro vás napsal David Čápka
Avatar
David je zakladatelem ITnetwork a programování se profesionálně věnuje 13 let. Má rád Nirvanu, sushi a svobodu podnikání.
Unicorn university David se informační technologie naučil na Unicorn University - prestižní soukromé vysoké škole IT a ekonomie.
Aktivity