Binärbäume

In der Regel arbeitet man mit “geordneten” Binärbäumen: Alle Elemente, ide linken Teilbaum stehen sind kleiner als Element in der Wurzel des Teilbaums alle Elemente im rechten Teilbaum sind größer.

Aufbau eines Binärbaums

Bsp. Elemente 1,5,9,11,23,47,55,56,99

flowchart TD
e23((23))---e9((9))
e23---e55((55))
e9---e5((5))
e5---e1((1))
e9---e11((11))

e55---e47((47))
e55---e56((56))
e56---e99((99))

Tiefe und Ausgeglichenheit

Die Tiefe eines Teilbaumes wird in linker und rechter Tiefe angegeben und beschreibt die maximale Pfadtiefe ausgehend vom linken bzw. rechten Teilbaums.

Die Ausgeglichenheit ist die rechte Tiefe subtrahiert von der linken Tiefe. Ein Baum ist ausgeglichen, wenn die Ausgeglichenheit 0 beträgt.