yandex rtb 1
ГоловнаЗворотній зв'язок
yande share
Главная->Математика і інформатика->Содержание->Листинг 5.1. Процедура MEMBER для дерева двоичного поиска

Алгоритмы и структуры данных

Листинг 5.1. Процедура MEMBER для дерева двоичного поиска

function MEMBER   (   х:   elementtype;   A:   SET   )boolean;

{  возвращает true,   если элемент х. принадлежит множеству А,  

false — в противном случае  } .

begin

if A = nil  then

return(false)    {   x не может  принадлежать  Ø  }

else if x = At.element then

return(true)

else  if x <  At.element then

return(MEMBER(x,   At.leftchild))

 else     {   x >  At.element  }

return(MEMBER(x,   АІ.rightchild))

end;    {   MEMBER   }

Процедура INSERT(x, А), которая добавляет элемент х в множество А, также проста для написания. Первым действием этой процедуры должна быть проверка условия А = nil, т.е. не является ли множество А пустым. Если это так, то создается новый узел, содержащий х, и А делается указателем на этот узел. Если множество А не пустое, то сначала производится поиск элемента, совпадающего с х (это делается примерно так же, как в функции MEMBER). Если элемент х уже есть в множестве, то никакие действия дальше не производятся. Если же в процессе поиска будет достигнут указатель nil (т.е. дошли до листа дерева), то он заменяется на указатель, указывающий на новый узел, содержащий элемент х. Код этой процедуры приведен в листинге 5.2.

Листинг 5.2. Вставка нового элемента в дерево двоичного поиска

procedure  INSERT   (   x:   elementtype;   var A:   SET   );

begin

if A = nil  then begin

new(А) ;

A↑.element:=  x ;

A↑.leftchild:=  nil;

А↑.rightchild:=  nil

end

else  if x <  A↑.element then

INSERT(x,   A↑.leftchild)

else if x >  A↑.element then

INSERT(x,   A↑.rightchild)

{  если х = A↑.element,   то никаких действий

не  производится,   т.к.   х уже  есть   в множестве А  }

end;    {   INSERT   }

Удаление элемента представляет некоторые трудности. Сначала надо найти этот элемент в дереве. Если х является листом, то он просто удаляется. Но если х является внутренним узлом (назовем его для краткости inode, от interior node — внутренний узел), то его нельзя просто удалить, так как нарушится связанность дерева.

Если inode имеет только одного сына (как узел 14 на рис. 5.1,6), то его можно заменить этим сыном. Если inode имеет двух сыновей, как узел 10 на рис. 5.1,а, то среди потомков правого сына надо найти элемент с наименьшим значением и заменить им удаляемый элемент. Например, для узла 10 на рис. 5.1,а таким будет узел 12.

Для написания процедуры DELETE полезно иметь функцию DELETEMIN(A), которая удаляет наименьший элемент из непустого дерева и возвращает значение удаляемого элемента. Код функции DELETEMIN приведен в листинге 5.3, а код процедуры DELETE, использующий эту функцию, — в листинге 5.4.

 

 

42