Typer av binära träd

Ett binärt träd tillåter högst två barn per nod. Vänster- och högerpositionerna är olika, även om bara ett barn finns. Ett binärt träd kräver inte att värden ligger i ordning. Det är en extra egenskap hos binära sökträd.

Liknande men olika former

Begrepp	Regel	Följd
Fullt / proper	Varje nod har noll eller två barn	En nod med bara ett barn bryter mot regeln
Perfekt	Varje intern nod har två barn och alla löv har samma djup	Vid höjd 2 finns sju noder
Komplett	Alla nivåer utom sista är fulla; sista fylls från vänster	Effektiv arraylagring
Höjdbalanserat	Djupen är tillräckligt jämna enligt en bestämd regel	AVL begränsar lokal höjdskillnad
Skevt	Varje inre nod har bara ett barn	Höjden kan bli n - 1

Ett perfekt träd är både fullt och komplett, men ett fullt träd behöver inte vara perfekt. Olika balanserade strukturer använder olika regler. AVL och red-black är inte identiska begrepp.

Hur många noder får plats?

Ett binärt träd med höjden h kan innehålla högst 2^(h+1) - 1 noder. Gränsen uppnås för ett perfekt träd. För n noder kan höjden vara ungefär log2(n) i bästa fall men n - 1 om trädet bildar en kedja.

Varför formen spelar roll

Ett komplett träd kan representeras kompakt som en array, eftersom barnens index kan beräknas. Ett skevt träd slösar däremot positioner i en sådan representation och kan ge stor rekursionsstack. Se arrayimplementering för för- och nackdelar.

Öva: Rita ett träd med fem noder som är fullt men inte komplett, och förklara varför den sista nivåns ordning är fel.

Referens: W3Schools binära träd.