Sortierte binäre Bäume

Ein Tupel (T, v, V, R) ist ein sortierter binärer Baum

bezüglich der Wertefunktion v: T -> V und

bezüglich der vollständigen Ordnungsrelation R für V x V,

wenn T ein binärer Baum ist, der entweder leer ist oder für den bezüglich des linken Teilbaums T₁ und des rechten Teilbaums T₂ gilt, daß

v(root(T)) >_R v(t) t T₁,

v(root(T)) _R v(t) t T₂ und daß

sowohl (T₁, v, V, R) als auch (T₂, v, V, R) sortierte binäre Bäume sind.

Gelegentlich ist es auch sinnvoll, darauf zu bestehen, daß

v(t₁) _R v(t₂) t₁, t₂ T, t₁ t₂
In diesem Falle ist die Wertefunktion v: T -> V_T bijektiv, wobei
V_T = {v | exists t T: V(t) = v}, d.h. mit Hilfe eines Wertes v V_T kann ein Knoten t T eindeutig bestimmt werden.