Föreläsning 8

Sökträd

[kapitel 9]
OH-bilder från denna föreläsning

Vad är ett sökträd?
Ett träd där elementen är ordnade efter nyckelstorlek.

Vad vill man kunna göra snabbt i ett sökträd?
lagra, hitta samt ta bort element.

Hur gör man insättning av nya element?

Hur tar man bort element?

Kan man undvika att trädet blir obalanserat?
Ja, det finns flera sätt. AVL-träd, (2,4)-träd samt röd-svarta träd är tekniker för detta.

Vad är ett AVL-träd?
Ett sökträd där grenarna från varje nod maximalt får skilja sig med 1 i höjd.
Insättning och borttagning kräver ibland s.k. trinode restructuring för att återställa balanseringen.

Vad är ett (2,4)-träd?
Ett sökträd där varje nod kan ha 2, 3 eller 4 barn.
Alla grenar är här exakt lika långa.
Trädet växer genom split-operationen där en nod delas upp i två.
Trädet krymper genom fuse-operationen då två noder smälter ihop till en.

Vad är ett röd-svart träd?
Enkelt uttryckt: ett (2,4)-träd där varje nod lagras som ett litet träd med 1, 2 eller 3 noder.