Структури даних, Детальна інформація

begin

if (Tree = NIL) then FindEl := FALSE else

if (Tree^.Val = Value) then FindEl := TRUE else

if (Value < Tree^.Val) then FindEl := FindEl (Tree^.Left, Value)

else FindEl := FindEl (Tree^.Right, Value);

end;

function TreeStr.Find (Value:integer):boolean;

begin

Find := FindEl (TTree, Value);

end;

Мінімальний (максимальний) ключ в дереві можна знайти, якщо пройти по вказівникам Left (Right) від кореня поки не досягнемо вершини, лівий (правий) син якої дорівнює NIL. Процедура FindMin (FindMax) повертає вказівник на вершину, яка містить мінімальний (максимальний) ключ. Час виконання вказаних процедур дорівнює O(h), де h – висота дерева.

function FMax (Tree:PTree):PTree;

begin

if (Tree^.Right = NIL) then FMax := Tree

else FMax:= FMax (Tree^.Right);

end;

function TreeStr.FindMax:PTree;

begin

if TTree = NIL then FindMax := NIL

else FindMax := FMax (TTree);

end;

function Fmin (Tree:PTree):PTree;

begin

if (Tree^.Left = NIL) then FMin := Tree

else FMin:= FMin (Tree^.Left);

end;

function TreeStr.FindMin:PTree;

begin

if TTree = NIL\x7420\x6568\x206E\x6946\x646E\x694D\x206E\x3D3A\x4E20\x4C49\x200D\x6520\x736C\x2065\x6946\x646E\x694D\x206E\x3D3A\x4620\x694D\x206E\x5428\x7254\x6565\x3B29\x650D\x646E\x0D3B

У процедурі вставки Insert елемента Value в бінарне дерево Tree відбувається рух вниз по дереву від корня до листа. В кожній вершині x, яка не є листом, процедура обирає напрямок руху (вліво чи вправо) у відповідності до властивості впорядкованості: якщо Value < x.Val, то відбувається рух вліво, інакше – вправо. Дійшовши до листа z, процедура вставляє нову вершину w, ключ якої дорівнює Value знову ж таки за властивістю впорядкованості: якщо Value < z.Val, то z.Left := w, інакше z.Right := w. Час виконання процедури дорівнює O(h), де h – висота дерева.