Suche in einem binären sortierten Baum
Gegeben sei ein Wert
k
V
und gesucht wird ein Knoten
t
T
mit
v
(
t
) =
k
:
1.
Wenn
T
leer ist, dann ist der gesuchte Wert nicht vorhanden.
2.
Sei
t
= root(
T
). Wenn
v
(
t
) =
k
, dann ist der gesuchte Wert gefunden.
3.
Es geht weiter mit dem ersten Schritt, wobei
T
=
T
1
, falls
k
<
v
(
t
), und
T
=
T
2
, falls
k
v
(
t
).
Diese Suche hat einen Aufwand von
O
(
h
(
T
)).
Copyright © 1999
Andreas Borchert
, in HTML konvertiert am 29.06.1999
![[Vorheriges Kapitel]](pprev.gif)
![[Vorherige Seite]](prev.gif)
![[Inhaltsverzeichnis]](up.gif)
![[Nächste Seite]](next.gif)
![[Nächstes Kapitel]](nnext.gif)
V und gesucht wird
ein Knoten t T mit v(t) = k:
v(t).