31. Оператор проверки принадлежности элемента множеству. Оператор вставки элемента в бинарное дерево поиска.
MEMBER (x, A); x – элемент, А – множество, как дерево поиска. Мы рассмотрим этот алгоритм внутри INSERT и определим его как рекурсивную функцию.
Мы будем обозначать символом Element Type и будем полагать, что на множестве этого типа определено отношение «=» и «<», «>».
type
Node Type = record
element: Element Type;
Left Child, Right Child: ^Node Type;
end;
Программным образом дерево будет указатель следующего типа:
var
A: SET
type
SET =^Node Type;
Указатель будет адресовываться к корню дерева. Соответственно оператор создания пустого дерева сведется к виду:
A:=nil;
Псевдокод функции MEMBER:
function MEMBER (x: Element Type; A: SET): Boolean;
begin:
if A=nil then return (false)
else if x=A^.element then return (true)
else if x<A^.element then return (MEMBER(x, A^.LeftChild))
else return (MEMBER (x, A^.RightChild));
end;
Оператор вставки элемента в бинарное дерево поиска:
INSERT (x, A)
Определяется как рекурсивная процедура. Тут дадим алгоритм, который является аналогм операции new в С++. В нашем примере этот оператор будет выполнять область для хранения объектов типа Node Type, а адрес этой области будет передаваться оператору, который является элементом оператора new.
procedure INSERT (x: Element Type; var A:SET);
begin
if A=nil then begin
new(A); //создаем корень дерева
A^.element := x; // A^. – разименование
A^.LeftChild:=nil;
A^.RightChild:=nil;
else if “x<A^.element then INSERT (x, A^.LeftChild)
end;
// если x=A^.element, то никакие действия не осуществятся, т.к x уже хранится в дереве.
32.Оператор удаления элемента из бинарного дерева
DELETE (x, A) – удаление элемента x из множества A.
Определим как рекурсивную процедуру: если лист находится в узле, который является листом, то этот узел просто удаляется, в противном случае его нельзя просто удалить, т.к разрушиться связность дерева. Обозначим эту ситуацию inoude, если узел inode имеет только одного сына, как узел (6) на рис. 4.1, то узел inode можно заменить сыном, если узел inode имеет 2-х сыновей, как узел (12) на рис. 4.1, то среди потомков правого сына нужно найти наименьший элемент и заменить им удаленный элемент (каждый узел одновременно является потомком самого себя).
Можно действовать по другому: нужно найти наибольший среди потомков левого сына, таким образом при разработке рекурсивного DELETE нужно иметь рекурсивную функцию DELETE MIN, которая будет удалять минимальный элемент из каждого НЕ пустого дерева => и поддерева, после чего соответствующим образом меняя дерево или поддерево.
function DELETEMIN (var A:SET): Element Type;
if A^.LeftChild = nil then // равенство означает, что А указывает на наименьший элемент (1.1)
begin (1.2)
DELETEMIN = A^.element; (1.3)
A:=A^.RightChild; // замена узла, на который указывало А, его правым сыном, если правого сына нет, то А получает nil, таким образом узел с наименьшим элементом будет удален из множества, однако следует учитывать, что из динамической кучи соответствующей области памяти удален не будет, в реальной программе надо позаботится о таком удалении (1.4)
end (1.5)
else DELETEMIN:=DELETEMIN (A^.LeftChild); (1.6)
procedure DELETE (x: Element Type; var A:SET);
begin
if A< > nil then (2.1)
if x<A^.element then (2.2)
DELETE (x, A^.LeftChild) (2.3)
else if x<A^.element then (2.4)
DELETE (x, A^.RightChild) (2.5)
else if (A^.LeftChild = nil) end (A^.RightChild = nil) then // у узла нет сыновей (2.6)
A:=nil // удаление листов содержащих элемент x (2.7)
else if A^.LeftChild = nil then (2.8)
A^.RightChild (2.9)
else if A^.RightChild = nil then (2.10)
A:=A^.LeftChild (2.11)
else // у узла есть оба сына (2.12)
A^.element:=DELRTMIN (A^.RightChild); (2.13)
end;
Пример:
Пусть из дерева рис. 4.1 необходимо удалить элемент 10(находящийся в корне)
Первым будем использовать оператор вызова функции DELETMIN с элементом указывающим на узел (12). Т.к DELETMIN – рекурсивная функция, то в ней реализуется еще 1 вызов DELETMIN на узел (11). Узел (11) не имеет левого сына поэтому DELETMIN возвращает (11) и устанавливает указатель на (12) на левого сына равным nil. После этого заменим (10) на число (11) возвращаемое nil.
В результате мы получим дерево следующего вида:
