Операция удаления

Выполняется в два действия:

1. Поиск вершины.
2. Если он успешен. то удаление вершины.

Операция удаления вершины имеет три варианта решения, которые зависят от связи вершины с другими.

1. Вершина-лист

В этом случае удаление вершины заключается в удалении самой вершины и обнулении указателя на текущую вершину в родительской вершине.

1. Удаляется вершина с одним потомком.

Удаление вершины заключается в перенаправлении указателя на текущую вершину на вершину-потомок, а затем удаление самой вершины.

1. Удаление вершины с двумя потомками.

Существуют два правила удаления такой вершины:

1. Указатель на текущую вершину перенаправляется на вершину (корень) левого поддерева, а вершина (корень) правого поддерева присоединяется к самой правой вершине левого поддерева.

2. Указатель перенаправляется на корень правого поддерева, а корень левого поддерева присоединяется к самой левой вершине правого поддерева.

← Самая левая вершина поддерева – это вершина с пустым левым указателем, в которую можно попасть из корня только по левым указателям.

Самая правая вершина поддерева – то же самое, но с правой стороны.

Дата добавления: 2014-01-15