Удаление X из двоичного



Рисунок 9. 11.  Удаление X из двоичного справочника. Возникает проблема наложения "заплаты" на место удаленного элемента X.


операции добавления листа:

        удлист( Д1, X, Д2) :-
                доблист( Д2, X, Д1).

К сожалению, если Х - это внутренняя вершина, то такой способ не работает, поскольку возникает проблема, иллюстрацией к которой служит Рисунок 9.11. Вершина Х имеет два поддерева Лев и Прав. После удаления вершины Х в дереве образуется "дыра", и поддеревья Лев и Прав теряют свою связь с остальной частью дерева. К вершине А оба эти поддерева присоединить невозможно, так как вершина А способна принять только одно из них.

Если одно из поддеревьев Лев и Прав пусто, то существует простое решение: подсоединить к А непустое поддерево. Если же оба поддерева непусты,



Содержание раздела