Shrnutí na Binární vyhledávací strom
Binární Vyhledávací Strom: Komplexní průvodce pro studenty
Binární vyhledávací strom
Binární vyhledávací strom (zkráceně BST z anglického Binary Search Tree) je fundamentální datová struktura v informatice. Slouží k efektivnímu ukládání a organizaci dat, což umožňuje rychlé vyhledávání, vkládání a mazání prvků. Jedná se o speciální typ binárního stromu, který se řídí přesnými pravidly pro uspořádání hodnot v uzlech, a právě tato pravidla mu propůjčují jeho unikátní vyhledávací schopnosti.
Základní pojmy a vlastnosti
Binární strom je hierarchická datová struktura, která se skládá z uzlů. Každý uzel v binárním stromu může mít nanejvýš dva potomky, které obvykle nazýváme levý potomek a pravý potomek.
Uzel (Node): Základní stavební blok stromové struktury, který obsahuje hodnotu a odkazy na své potomky (pokud existují).
List (Leaf): Uzel, který nemá žádné potomky.
Kořen (Root): Uzel, který nemá žádného rodiče; je to vstupní bod do stromu.
Rodič (Parent): Uzel, který má přímé potomky.
Potomek (Child): Uzel, který má rodiče. Každý uzel kromě kořene má právě jednoho rodiče.
Podstrom (Subtree): Libovolný uzel a všichni jeho potomci, tvořící samostatný binární strom.
Klíčová vlastnost binárního vyhledávacího stromu spočívá v uspořádání hodnot uzlů. Pro každý uzel $U$ ve stromu platí následující pravidla:
- Všechny hodnoty v levém podstromu uzlu $U$ jsou menší než hodnota uzlu $U$ samotného.
- Všechny hodnoty v pravém podstromu uzlu $U$ jsou větší než hodnota uzlu $U$ samotného.
- Levý i pravý podstrom uzlu $U$ jsou samy o sobě binárními vyhledávacími stromy.
Tato uspořádávací vlastnost zajišťuje, že data jsou ve stromu logicky organizována, což umožňuje logaritmickou časovou složitost pro většinu operací, pokud je strom vyvážený.
Reprezentace uzlu
Typicky je uzel binárního vyhledávacího stromu reprezentován strukturou, která obsahuje:
- Hodnotu (Data): Uložená data v uzlu.
- Odkaz na levého potomka (Left Child): Ukazatel na kořen levého podstromu.
- Odkaz na pravého potomka (Right Child): Ukazatel na kořen pravého podstromu.
struct Node {
int data;
struct Node *left;
struct Node *right;
};
Operace na binárním vyhledávacím stromu
Binární vyhledávací stromy podporují několik základních operací, které jsou klíčové pro jejich efektivní použití.
Hledání (Vyhledávání)
Hledání prvku s danou hodnotou $X$ v BST začíná u kořene stromu. Algoritmus postupuje rekurzivně nebo iterativně následovně:
- Porovnejte $X$ s hodnotou aktuálního uzlu $U$.
- Pokud se $X$ rovná hodnotě $U$, prvek byl nalezen.
- Pokud je $X$ menší než hodnota $U$, pokračujte v hledání v levém podstromu uzlu $U$.
- Pokud je $X$ větší než hodnota $U$, pokračujte v hledání v pravém podstromu uzlu $U$.
- Pokud se dostanete k prázdnému podstromu (tj. aktuální uzel je
null), prvek ve stromu není.
Příklad hledání: Hledání hodnoty $25$ ve stromu s kořenem $50$.
- $25 < 50$, jdeme doleva.
- Aktuální uzel je $30$. $25 < 30$, jdeme doleva.
- Aktuální uzel je $20$. $25 > 20$, jdeme doprava.
- Aktuální uzel je $25$. $25 = 25$, hodnota nalezena.
Vkládání (Insert)
Vkládání nové hodnoty $X$ do BST se provádí podobně jako hledání. Začíná se u kořene a postupuje se dolů stromem, dokud se nenajde vhodné místo pro vložení nového uzlu jako listu.
- Začněte u kořene stromu.
- Porovnejte $X$ s hodnotou aktuálního uzlu $U$.
- Pokud je $X$ menší než hodnota $U$:
- Pokud má $U$ levého potomka, pokračujte vlevo.
- Pokud $U$ nemá levého potomka, vložte $X$ jako levého potomka uzlu $U$ a operace je dokončena.
- Pokud je $X$ větší než hodnota $U$:
- Pokud má $U$ pravého potomka, pokračujte vpravo.
- Pokud $U$ nemá pravého potomka,
Zaregistruj se pro celé shrnutíUž máš účet? Přihlásit se
Binární vyhledávací stromy
Klíčová slova: Binární vyhledávací strom, Binární vyhledávací stromy
Klíčové pojmy: BST je hierarchická datová struktura pro efektivní ukládání a organizaci dat., Pro každý uzel v BST platí: levý potomek < rodič < pravý potomek., Hledání prvku začíná od kořene a postupuje se doleva nebo doprava podle porovnání s aktuální hodnotou uzlu., Vkládání nového prvku se provádí jako hledání, dokud se nenajde prázdné místo pro vložení jako list., Mazání uzlu má tři případy: list, uzel s jedním potomkem, uzel se dvěma potomky., Uzel se dvěma potomky se maže nahrazením inorder následníkem (nebo předchůdcem) a následným smazáním původního následníka/předchůdce., Časová složitost většiny operací v BST je $O(\log N)$ pro vyvážený strom, ale $O(N)$ pro degenerovaný strom., Kořen je uzel bez rodiče, list je uzel bez potomků., Podstrom je libovolný uzel a všichni jeho potomci., Kritické je zachování vlastností BST při každé operaci., Simulace pomáhají pochopit dynamické chování stromu.