BPC-ALD - Skripta_rev2019_2

2.  Po odstranění prvku 41 z uzlu v něm zůstane jen jeden prvek. Uzel má ale přímé 

sousedy, které mají více než 2 prvky. Použijeme jeho levého souseda a přesuneme z 
něho prvek, abychom doplnili uzel, z něhož byl prvek odstraněn. Výsledek ukazuje 
následující obrázek: 

3.  Po odstranění prvku 37 z kořenu můžeme volné zaplnit největším prvkem (34) z levého 

podstromu anebo nejmenším prvkem (39) z pravého podstromu. Zvolme prvek 34. 
Ježto nyní list, který tento prvek obsahoval, má nyní jen jeden prvek a zároveň nemá 
přímého souseda, z kterého by bylo možné prvek do něho přesunout, sloučíme ho s jeho 
levým přímým sousedem. Tím ale se sníží počet prvků v předchůdci na 1 prvek, což 
znamená další sloučení. Výsledek ukazuje následující obrázek: 

4.4  Hašování (Transformace klíče) 

Studijní cíle:  Tato  část  vysvětluje  metodu  hašování,  popisuje  konstrukci  hašovací  funkce  a 
ukazuje, jak řešit kolize při stejných hodnotách hašovací funkce. 

Klíčová slova: Hašování, hašovací tabulka, hašovací funkce, zřetězení.60 minut. 

Potřebný čas: 1 hodina 

Poslední vyhledávací metodou, kterou probereme, je hašování. Pro její anglický název hashing 
se  poměrně  obtížně  hledá  vhodný  překlad  do  českého  jazyka,  proto  zůstaneme  u  používání 
mírně češtině přizpůsobeného anglického názvu. 

Datová  struktura  použitá  v  hašování  pro  uložení  prvků  je  tabulka.  Tabulka  se  skládá  z řádků, 
v každém  řádku  je  místo  pro  uložení  jednoho  prvku.  Počet  řádků  v tabulce,  tedy  kapacitu 
tabulky označme m. Na jednotlivé řádky v tabulce se odkazujeme (adresujeme je) čísly 0 až m-