Удаление x из двоичного справочника. Возникает проблема наложения "заплаты" на место удаленного элемента x.
Удаление X из двоичного справочника. Возникает проблема наложения "заплаты" на место удаленного элемента X.
операции добавления листа:
удлист( Д1, X, Д2) :-
доблист( Д2, X, Д1).
К сожалению, если Х - это внутренняя вершина, то такой способ не работает, поскольку возникает проблема, иллюстрацией к которой служит рис. 9.11. Вершина Х имеет два поддерева Лев и Прав. После удаления вершины Х в дереве образуется "дыра", и поддеревья Лев и Прав теряют свою связь с остальной частью дерева. К вершине А оба эти поддерева присоединить невозможно, так как вершина А способна принять только одно из них.
Если одно из поддеревьев Лев и Прав пусто, то существует простое решение: подсоединить к А непустое поддерево. Если же оба поддерева непусты,
