© 1999-2003, Flemming Koch Jensen Alle rettigheder forbeholdt

Balancerede træer

 

 

	Træstrukturen er fordelagtig, da den kan give os optimale søgetider. Disse søgetider er dog afhængige af, at træet er rimelig balanceret, så højden bliver logaritmisk som funktion af antallet af knuder i træet. I worst case kan man forestille sig et træ der er degenereret til en liste; en såkaldt vestjysk palme [FKJ]:
Vestjysk palme
	Vi er derfor meget interesseret i teknikker til at garantere en rimelig balancering af vores træer, da de ellers ikke er meget mere værd end lister!
	Vi vil i den forbindelse indføre to definitioner:
Fuldt træ	Definition: Et fuldt træ Et fuldt træ, er et træ, hvor alle niveau er udfyldt med alle mulige knuder, evt. pånær det laveste niveau.
Komplet træ	Definition: Et komplet træ Et komplet træ, er et fuldt træ, hvor alle knuder på laveste niveau, fylder op fra venstre.
	Der findes forskellige teknikker, til at opnå et balanceret træ.
AVL-træer	Først og fremmest er der AVL-træer, der udemærker sig ved ikke at ændre på den traditionelle opbygning af et træ. AVL-træer garanterer at undertræerne til enhver knude, har en højdeforskel på højest 1.
B-træer	En anden teknik er at tillade knuder at have flere end to børn, disse træer kalder man normalt B-træer, hvor B er antallet af børn.
	I DocJava findes der pt. kun et beskrivelse af AVL-træer, og det er tvivlsomt om der kommer en beskrivelse af B-træer, da der er så meget andet der mangler at blive skrevet.