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

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

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

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

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

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

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

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

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