Datové struntury - spojový seznam 2, strom
7. 3. 2023
Jednosměrný seznam
Zarážka
- Speciální uzel na začátku seznamu
- Ignorujeme jeho klíč, udržujeme jej jako představitele seznamu. Samotný seznam začíná až jeho následníkem.
- Výhoda: funkce, které modifikují seznam, nemusí vracet nový uzel
- Nevýhoda: ztratíme flexibilitu v práci s podseznamy.
r = node, Zarážka
added = node, přidávaný uzel
n = index, na který se má přidat uzel
insert-nth(r, added, n)
x = n-tý uzel
insert-after(x, added)
Obousměrný seznam
- lez procházet oběma směry(next i prev)
- dochází tím k zjednodušení operace přidání i mazání
- sentinel
remove (r: node):
r.prev.next = r.next
if r.next != nil:
r.next.prev = r.prev
Pomocí sentinelu, který dáme jak na začátek tak i na konec seznamu, můžeme dostat cyklický seznam. Operace nad cyklickým seznamem jsou velmi jednoduché, protože nám odpadne test na nil.
Strom
Strom je souvislý graf bez kružnic = mezi každou dvojicí vrcholů vede právě jedna cesta
Kořenový strom je speciální případ stromu, kdy je jeden vrchol označen jako kořen. Získáme tak směr a nově uvažujeme cesty z kořene do ostatních vrcholů. Nově budeme ozly nazývat následníkem/předchůdcem, potomkem/rodičem, sourozencem (stejný rodič) nebo listem(nemá potomka).
Pro libovolný vrchol x ve stromu platí:
- počet předchůdců x je roven jeho hloubce
- Různé podstromu x obsahují disjuktní množiny vrcholů
- Výška podstromu s kořenem x je rovna maximu výšek podstromů vrcholu x, ke kterému přičteme jedna.
Kořenový strom je m-ární, pokud každý jeho vrchol má NEJVÝŠE m potomků.
Strom v pointer machine
Struct je vrchol, potomci přímo v položce, v poli, v seznamu. Strom si pamatujeme pomocí kořene.
struct node //pro pole
id : key
children : [m]node
n : int
struct node //pro seznam
id : key
child : node
sibling : node
Průchod stromem
Chceme systematicky navštívit všechny vrcholy stromu, každý právě jednou. Můžeme strom procházet buďto do hloubky nebo do šíčky. Procházet můžeme do hloubky pomocí dvou způsobů: rekurzivně a iterativně.
První se podíváme na průchod do hloubky rekurzivně.
depth-first-search(x: node)
print(x.id)
for c in x.children:
depth-first-search(c)
Průchod do hloubky pomocí iterativní verze.
depth-first-search-iter(x: node)
S = stack()
push(S, x)
while S is not empty:
y = pop(S)
print(y.id)
for w in y.children:
push(S, w)
Průchod do šířky pomocí iterativní verze.
breadth-first-search-iter(x: node)
Q = queue()
enqueue(Q, x)
while Q is not empty:
y = dequeue(Q)
print(y.id)
for w in y.children:
enqueue(Q, w)