Binárne a lexikografické stromy

Zhrnutie prednášky

Šiesta prednáška sa venuje konštrukcii binárnych a lexikografických stromov ako dátových abstrakcií, ktoré sa neskôr využijú pri vyhľadávaní a triedení. Stromy sa modelujú pomocou rekurzívnych dátových typov: uzol obsahuje hodnotu a dva smerníky (ľavý a pravý) predstavujúce hrany. Princíp je ukázaný na prekladači Morseovky, kde bodka vedie doľava, čiarka doprava a koreň je prázdny znak, takže písmeno sa nájde priamo prechodom stromom bez prehľadávania celého zoznamu. Opísané sú potrebné operácie: inicializácia (create), vloženie uzla, vytvorenie stromu, rekurzívne odstránenie stromu a preklad. Pri vkladaní sa pomocným smerníkom prechádza kódom znak po znaku a ak v danom smere uzol chýba, vytvorí sa nový.

• - Binárny strom má koreň, uzly s maximálne dvoma potomkami a koncové uzly nazývané listy.
• - Uzol sa modeluje ako štruktúra s hodnotou a dvoma smerníkmi, ktoré predstavujú ľavú a pravú hranu.
• - Morseov kód sa zapisuje do stromu: bodka vedie doľava, čiarka doprava, koreň je prázdny znak.
• - Vyhľadanie písmena v strome je jednoznačné a rýchle, netreba prechádzať celý zoznam.
• - Potrebné operácie sú inicializácia, vloženie uzla, vytvorenie stromu, rekurzívne odstránenie a preklad.
• - Pri vkladaní sa kódom prechádza pomocným smerníkom a chýbajúci uzol sa vytvorí, až kým sa nedosiahne koniec reťazca.
• - Morseovka nemá v strome neohodnotené uzly, kým lexikografický strom (napr. slovník) ich mať môže.

Zhrnutie pripravené s pomocou AI z prepisu videa.