Curs Arbori binari de cautare

Un arbore binar ale carui chei iau valori de un tip total ordonat se numeste arbore binar de cautare (strict) daca cheia fiecarui nod este mai mare decat orice cheie din fiul sau stang si mai mica decat orice cheie din fiul sau drept. Formal, intr-un arbore binar de cautare, pentru orice nod u al sau avem relatiile:
(1) info[u] > info[v],  pentru orice v in left[u]
(2) info[u] < info[w], pentru orice w in right[u].
Sa observam ca ar fi suficient sa impunem existenta acestor relatii de ordine intre un nod si descendentii sai directi. Cu alte cuvinte, T este un arbore binar, cu chei de un tip total ordonat, si cu proprietatea ca pentru orice nod u al sau avem relatiile :
       (1’)  info[u] > info[root(left[u])]
       (2’)  info[u] < info[root(right[u])]