Träd & grafer Flashcards
Vad är några karakteristiska drag för ett träd som datastruktur?
Ett träd har en root node (ingång).
Data lagras hierarkiskt.
Alla noder har en förälder (utom root).
Varje nod kan ha noll eller flera barn.
Noder utan barn kallas “löv”.
Ge exempel på hur träd används i olika sammanhang.
Träd används för att representera:
Linux filsystem
If-satsernas syntax i programmering
SQL-syntax för SELECT-satser
Strukturering av naturligt språk
Organisationshierarkier
Vad är ett träd inom IT?
Ett träd är en av de vanligaste abstrakta datastrukturerna inom IT. Det är en hierarkisk struktur med termer som kommer från genealogi, t.ex. root, node, parent, children och leaves.
Vilka är några användningsområden för trädstrukturer?
Träd används inom:
Filsystem
Kompilatorer (för att analysera programmeringsspråks syntax)
Naturligt språkbehandling
Organisationshierarkier
Sorteringsalgoritmer
m.m
Vilka är vanliga operationer på träd?
Skapa ett träd (create)
Lägg till en ny nod (insert)
Räkna antal noder (size)
Räkna längsta väg (height)
Sök efter en viss nod
Traversera trädet (flera sätt)
Vad är ett binärt träd?
Ett binärt träd är en typ av träd där varje nod har högst två barn. Det används ofta för sortering och parsning.
Hur ser trädet ut efter att noderna 78, 44, 101, 97, 222 har insatts?
Trädet byggs upp enligt följande struktur:
78 är root.
44 är vänster barn till 78.
101 är höger barn till 78.
97 är vänster barn till 101.
222 är höger barn till 101.
Vad gör funktionen ascending_write(node)?
Funktionen traverserar trädet in-order (vänster, root, höger) och skriver ut nodernas data i stigande ordning.
Hur fungerar insättning av noder i ett träd?
Insättningen börjar från root och jämför varje nods värde för att avgöra om den ska placeras till vänster (mindre värde) eller till höger (större värde).
Hur representeras en nod i ett träd med Python?
En nod representeras av en klass Tree med tre attribut: data, left, och right. left och right pekar på barnnoderna.
Hur ser trädet ut efter att noderna 78, 44, 101, 97, 222 har insatts?
Trädet byggs upp enligt följande struktur:
78 är root.
44 är vänster barn till 78.
101 är höger barn till 78.
97 är vänster barn till 101.
222 är höger barn till 101.
Vad består en graf av?
En graf består av:
Noder (vertices): Punkterna i grafen.
Bågar (edges): Linjer som binder samman noderna.
Vilka olika typer av grafer finns det?
Riktade grafer (directed): Bågarna har en riktning.
Oriktade grafer (undirected): Bågarna har ingen riktning.
Viktade grafer (weighted): Bågarna har vikter (kostnader) associerade med sig.
Cykliska grafer (cyclic): Grafer som innehåller cykler.
Acykliska grafer (acyclic): Grafer som inte innehåller cykler.
Hur ser en riktad graf ut?
En riktad graf är en graf där varje båge har en riktning. Exempel på en riktad graf:
Noder: A, B, C, D, E
Bågar: A → B, B → C, C → D, D → E
Hur ser en oriktad graf ut?
En oriktad graf är en graf där bågarna inte har någon riktning. Exempel på en oriktad graf:
Noder: A, B, C, D, E
Bågar: A – B, B – C, C – D, D – E
Vad är en viktad graf och hur används den?
En viktad graf är en graf där varje båge har en vikt (kostnad) associerad med sig. Exempel på användning är att representera avstånd mellan städer. Exempelgraf:
Noder: A (Alingsås), G (Göteborg), J (Jönköping), M (Malmö), S (Stockholm)
Bågar: Alingsås → Göteborg (46), Göteborg → Jönköping (154), etc.
