Вставка узла

3. Вставка узла в двоичное дерево поиска не представляет сложности. Для того чтобы вставить узел, необходимо найти его место. Для этого мы сравниваем вставляемый ключ с корнем, если ключ больше, чем ключ корня, уходим в правое поддерево, а иначе – в левое. Тем же образом продвигаемся дальше, пока не дойдем до конечного узла (листа). Сравниваем вставляемый ключ с ключом листа. Если ключ меньше ключа листа, то добавляем листу левого сына, а иначе – правого сына. Например, необходимо вставить в дерево, изображенное на рисунке, узел с ключом 5.

 

 

Сравниваем 5 с ключом корня; 5<10, следовательно, уходим в левое поддерево. Сравниваем 5 и 6; 5<6, спускаемся влево. Следующий узел является конечным (листом). Сравниваем 5 и 1; 5>1, следовательно, вставляем правого сына. Получим дерево с новым узлом, которое сохранило все свойства дерева поиска.

 

Удаление вершины

 

Проблемы возникают и при удалении. Нам необходимо сохранить свойство упорядоченности ДДП. При удалении возможны три случая: у удаляемой вершины нет потомков, у удаляемой вершины есть один потомок и у удаляемой вершины два потомка. Если потомков нет, то вершину можно просто удалить. Если потомок один, то удаляемую вершину можно “вырезать”, указав её родителю в качестве потомка единственного имеющегося потомка удаляемой вершины. Если же потомков два, требуются дополнительные действия. Нужно найти следующую за удаляемой (по порядку ключей) вершину, скопировать её содержимое (ключ и данные) в удаляемую вершину (она теперь никуда не удаляется физически, хотя логически исчезает) и удалить найденную вершину (у неё не будет левого потомка).

 

 

 

 

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

 

 

Сложнее всего случай, когда у удаляемого узла есть оба потомка.

 

 

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

 

 

В общем же случае на место удаляемого узла ставится самый левый лист его правого поддерева (или наоборот – самый правый лист его левого поддерева). Это не нарушает свойств дерева поиска.

Корень дерева удаляется по общему правилу за исключением того, что заменяющий его узел не требуется присоединять к узлу-родителю.

Продолжение программы