Структуры и алгоритмы обработки данных



Краткая теория


Удаление узла дерева не должно нарушать упорядоченность дерева. При удалении возможны следующие варианты расположения узлов:

1)  найденный узел является листом - он просто удаляется (рис.1);

2)  найденный узел имеет только сына - в этом случае сын перемещается на место удаленного отца (рис.2);

3)  у удаляемого отца два сына -  в  этом  случае  основная  трудность  состоит  в  удалении отца, поскольку в  удаляемую  вершину  входит одна  стрелка,  а выходит две.

В  этом случае  нужно найти  подходящее  звено  поддерева, которое можно было бы  вставить  на место удаляемого, причем  это  подходящее  звено должно просто  перемещаться. Такое  звено всегда  существует:

       - это самый  правый элемент   левого   поддерева  (для  достижения  этого  звена необходимо  перейти в следующую вершину по  левой ветви, а  затем  переходить в  очередные вершины  только  по правой ветви  до тех  пор, пока очередная ссылка не будет равна nil);

       - это самый  левый  элемент  правого  поддерева   (для  достижения  этого  звена необходимо перейти в следующую  вершину по правой ветви, а  затем  переходить  в очередные  вершины  только по левой ветви  до  тех  пор, пока  очередная такая ссылка не будет равна nil).

       Очевидно, что   такие  подходящие  звенья  могут  иметь  не  более  одной ветви.




Содержание  Назад  Вперед