Moment 8, balanserade träd

Översikt

Momentet behandlar binära sökträd och balansering av träd.

Innehåll

Implementationer av olika operationer på binära sökträd,  i synnerhet avsnitt 12.7 och framåt. Insättning, rotation, selektion, partitionering, borttagning, sammanslagning. Hela kapitel 12 är av vikt.

 Trädbalansering . Se i synnerhet på 13.1.

 13.5 kursivt.

Mål

 Att kunna beskriva principerna bakom 2-3-4 trädet.Insättning och borttagningsoperationer.

Att kunna implementera Röd-svarta träd, Insättning och borttagningsoperationer.

Att kunna beskriva fördelar nackdelar för de olika strukturerna. 

Minnesanteckningar