Niech
\(\displaystyle{ node = (e, left, right)}\) będzie strukturą danych reprezentującą węzeł drzewa binarnego
\(\displaystyle{ T}\) w taki sposób, że
\(\displaystyle{ e \in N}\) jest etykietą rozważanego węzła, a
\(\displaystyle{ left}\) i
\(\displaystyle{ right}\) reprezentują odpowiednio krawędź (dowiązanie) do lewego i prawego następnika wierzchołka z etykietą
\(\displaystyle{ e}\) w drzewie
\(\displaystyle{ T}\). Rozważmy następujący algorytm (
NULL oznacza brak węzła):
Kod: Zaznacz cały
Alg(node) = {
if node = NULL then return 0;
else return Alg(node.left) + Alg(node.right) + node.e; fi
}.
Kolejno:
(a) narysuj drzewo wywołań rekurencyjnych algorytmu
Alg(root), gdzie
root jest wierzchołkiemkorzeniem
drzewa binarnego
T,
(b) ustal rezultat działania algorytmu
Alg(root),
(c) oszacuj asymptotycznie liczbe operacji dodawania wzgledem liczby wierzchołków drzewa binarnego
T.
