Zhrnutie na Binárny vyhľadávací strom
Binárny Vyhľadávací Strom: Komplexný Rozbor pre Študentov
Binárny vyhľadávací strom (BST): Základy a operácie
Vitajte pri štúdiu jednej z najdôležitejších dátových štruktúr v informatike – Binárneho vyhľadávacieho stromu (BST). BST slúži na efektívne ukladanie a organizovanie dát, čo umožňuje rýchle vyhľadávanie, vkladanie a mazanie prvkov. Predstavte si ho ako hierarchickú štruktúru, kde každý prvok (uzol) má svoje miesto určené jeho hodnotou. Táto štruktúra je kľúčová pre aplikácie, ktoré vyžadujú časté operácie s usporiadanými dátami, ako sú databázy, slovníky alebo systémy na správu súborov.
Základné pojmy BST
Predtým, než sa ponoríme do operácií, je dôležité pochopiť základnú terminológiu binárnych stromov:
Uzol: Základný stavebný blok stromu, ktorý obsahuje hodnotu (dáta) a odkazy na svojich potomkov.
Koreň (Root): Najvyšší uzol v strome, ktorý nemá žiadneho rodiča. Všetky operácie začínajú od neho.
Rodič (Parent): Uzol, ktorý má aspoň jedného priameho potomka.
Potomok (Child): Uzol, ktorý je priamo spojený s rodičom. V binárnom strome má každý uzol najviac dvoch potomkov: ľavého a pravého.
List (Leaf): Uzol, ktorý nemá žiadnych potomkov. Je to "koniec" vetvy.
Podstrom (Subtree): Akýkoľvek uzol a všetci jeho potomkovia tvoria podstrom. Každý uzol je koreňom svojho vlastného podstromu.
Vlastnosť binárneho vyhľadávacieho stromu
To, čo odlišuje BST od bežného binárneho stromu, je prísne pravidlo usporiadania hodnôt, ktoré musí platiť pre každý uzol v BST:
- Všetky hodnoty v ľavom podstrome uzla sú menšie ako hodnota samotného uzla.
- Všetky hodnoty v pravom podstrome uzla sú väčšie ako hodnota samotného uzla.
- Každý podstrom je sám o sebe binárnym vyhľadávacím stromom.
Táto vlastnosť zaručuje, že ak hľadáme konkrétnu hodnotu, vieme na každom kroku rozhodnúť, či máme pokračovať vľavo alebo vpravo, čím sa výrazne znižuje počet porovnaní. Napríklad, ak máme uzol s hodnotou $50$, všetky hodnoty v jeho ľavom podstrome budú menšie ako $50$ (napr. $25, 40$) a všetky hodnoty v jeho pravom podstrome budú väčšie ako $50$ (napr. $75, 60, 90$).
Základné operácie s BST
Vyhľadávanie (Search)
Operácia vyhľadávania v BST je vďaka jeho usporiadanej štruktúre veľmi efektívna. Postupujeme nasledovne:
- Začneme od koreňa stromu.
- Porovnáme hľadanú hodnotu s hodnotou aktuálneho uzla.
- Ak sa hodnoty zhodujú, našli sme uzol a operácia je ukončená.
- Ak je hľadaná hodnota menšia ako hodnota aktuálneho uzla, presunieme sa do ľavého potomka.
- Ak je hľadaná hodnota väčšia ako hodnota aktuálneho uzla, presunieme sa do pravého potomka.
- Ak sa dostaneme na prázdny (null) odkaz, znamená to, že hľadaná hodnota v strome neexistuje.
Príklad: Hľadáme hodnotu $40$ v strome s koreňom $50$. Ak $40 < 50$, ideme doľava. Ak ľavý potomok je $30$, a $40 > 30$, ideme doprava. Ak pravý potomok je $40$, našli sme ju.
Časová zložitosť vyhľadávania je v priemernom prípade $O(\log n)$, kde $n$ je počet uzlov v strome. V najhoršom prípade (keď je strom degenerovaný do lineárneho zoznamu) je zložitosť $O(n)$.
Vkladanie (Insertion)
Vkladanie nového uzla do BST zachováva jeho vlastnosť usporiadania. Postup je podobný vyhľadávaniu:
- Začneme od koreňa stromu.
- Porovnáme novú hodnotu s hodnotou aktuálneho uzla.
- Ak je nová hodnota menšia, presunieme sa do ľavého potomka.
- Ak je nová hodnota väčšia, presunieme sa do pravého potomka.
- Opakujeme kroky 2-4, kým sa nedostaneme na prázdny (null) odkaz. Na tomto mieste vytvoríme nový uzol s vkladanou hodnotou a pripojíme ho ako potomka k predchádzajúcemu uzlu.
Dôležité: V BST sa zvyčajne nepovoľujú duplicitné hodnoty. Ak by sme chceli vložiť už existujúcu hodnotu, operácia by sa buď ignorovala, alebo by sa s ňou zaobchádzalo špecifickým spôsobom (napr. priradenie k ľavému alebo pravému podstromu, alebo zvýšenie počítadla výskytov).
Časová zložitosť vkladania je rovnako ako pri vyhľadávaní v priemernom prípade $O(\log n)$ a v
Zaregistruj sa pre celé zhrnutieUž máš účet? Prihlásiť sa
Základy a operácie BST
Klíčová slova: Základy a operácie BST, Praktické využitie a simulácie BST
Klíčové pojmy: BST je hierarchická dátová štruktúra pre efektívne ukladanie, vyhľadávanie, vkladanie a mazanie usporiadaných dát., Každý uzol v BST má najviac dvoch potomkov (ľavého a pravého)., Pre každý uzol v BST platí: ľavý podstrom < uzol < pravý podstrom., Vyhľadávanie v BST začína od koreňa a porovnáva hodnoty na rozhodnutie o smere (ľavý/pravý podstrom)., Vkladanie nového uzla zachováva vlastnosť BST a prebieha podobne ako vyhľadávanie, kým sa nenájde prázdne miesto., Mazanie uzla z BST má tri prípady: list, uzol s jedným potomkom, a uzol s dvoma potomkami (vyžaduje nástupcu/predchodcu)., Časová zložitosť základných operácií (vyhľadávanie, vkladanie, mazanie) je v priemernom prípade $O(\log n)$ a v najhoršom prípade $O(n)$., Výška stromu $h$ ovplyvňuje výkon; vyvážený strom má $h \approx \log_2 n$, zatiaľ čo degenerovaný strom má $h = n$., Existujú tri hlavné prechody stromom: Inorder (vypíše usporiadané prvky), Preorder a Postorder.