Binärbaum

​Als die in der Informatik meistverwendete Unterart von Bäumen, dürfen die Knoten eines Binärbaums nur maximal zwei direkte Nachkommen haben.

​Ein Binärbaum kann entweder leer sein, oder er besteht aus einer Wurzel, die mittels einer Kante meist mit einem eindeutigen linken und rechten Teilbaum verbunden ist.​ Jeder Teilbaum ist dabei wieder ein Binärbaum. ​Ist der Teilbaum leer, so wird der Kindknoten als fehlend bezeichnet. Solche unterste Knoten werden zugleich auch Blätter genannt.

Eine der wichtigsten praktischen Anwendungen von Binärbäumen sind die binären Suchbäume. Wird davon ausgegangen, dass ​alle Elemente im rechten Teil eines Binärbaums größer ​dem Wurzelelement und alle Elemente im linken Teil kleiner dem Wurzelement sind, dann kann mithilfe eines besonderen Algorithmus nach bestimmten Elementen gesucht werden:

Dabei werden mehrere Vergleiche mit den Wurzelelementen des Binärbaums bzw. seiner Teilbäume durchgeführt, ist das gesuchte Element kleiner, so wird links fortgefahren, andernfalls rechts. Bei diesem Verfahren sind somit weniger Vergleiche notwendig, als bei der linearen Suche.