27b - Binárne vyhľadávacie stromy
Definícia: Usporiadaný strom je koreňový strom. Pre každý jeho uzol platí, že n-tica koreňov podstromov uzlu je usporiadaná. Binárny vyhľadávací strom je taký binárny usporiadaný strom, že pre každý jeho uzol platí, že ľavý podstrom tohto uzlu je buď prázdny alebo obsahuje uzly, ktorých hodnoty sú menšie ako hodnota tohto uzlu a zároveň rovnako pravý podstrom tohto uzlu je buď prázdny alebo obsahuje uzly, ktorých hodnota je väčšia ako hodnota tohto uzlu.
- vyhľadávanie:
- ak je vyhľadávaný kľúč rovný koreňu, vyhľadávanie končí úspešným vyhľadaním.
- ak je kľúč menší, pokračuje vyhľadávanie v ľavom podstrome
- ak je kľúč väčší, pokračuje vyhľadávanie v pravom podstrome
- vyhľadávanie končí neúspešne ak je prehľadávaný (pod)strom prázdny
- najhorší prípad úspešného aj neúspešného vyhľadávania je daný výškou stromu
- algoritmy v BVS:
- vyhľadávanie
- insert - ak uzol s daným kľúčom existuje, prepíšu sa staré dáta, ak neexistuje, vloží sa nový uzol:
- delete - rušenie terminálneho uzlu je ľahké, rovnako uzlu s jedným synom, pri rušení uzlu pri rušení uzlu s dvoma podstromami nahradíme rušený uzol buď najpravejším uzlom ľavého podstromu, alebo najľavejším uzlom pravého podstromu
- BVS so zarážkou:
- všetky terminálne uzly ukazujú na uzol, ktorý má ako kľúč to, čo práve hľadáme
- význam - netreba overovať koniec ⇒ zrýchlenie algoritmu
- BVS so spätnými ukazateľmi:
- význam - umožňuje priechod bez použitia zásobníku aj rekurzie - spätný ukazatel je tam len kvôli tomu priechodu
- ľavý syn ukazuje na svojho otca
- pravý syn dedí spätný ukazateľ od svojho otca
- sračka - rušenie uzlu, ktorý má len ľavý podstrom - musia sa skorigovať všetky ukazatele po pravej diagonále toho ľavého podstromu
AVL stromy
- výškovo vyvážený strom
- je maximálne o 45% vyšší ako váhovo vyvážený strom
- pre každý uzol platí, že výška jeho dvoch podstromov je zhodná alebo sa líši o 1
- treba pridať atribút „vyváženosť“ - 1 = pravý strom je o 1 dlhší ako ľavý, atď
- rotácia LL
- rotácia DLR
