Именно так, как это звучит. Мы будем удалять узел из дерева, у которого есть только один потомок. Давайте посмотрим на наше дерево и посмотрим, какие узлы имеют одного дочернего элемента. В нашем примере только узел 33 имеет одного потомка. Все остальные узлы имеют по два потомка.
Если бы мы удалили узел 47 из списка, у нас было бы два узла, каждый из которых имеет по 1 дочернему элементу; узел 40 будет иметь одного непосредственного дочернего элемента, а узел 33 будет иметь одного непосредственного дочернего элемента. Однако оставим пример как есть. Однако важно, чтобы читатель имел это визуальное представление в своей голове.
Итак, как бы мы удалили узел 33 из дерева, показанного выше? Это просто. Родительский узел узла 33, узел 40, будет указывать на дочерний узел узла 33 после того, как он разорвет ребро с узлом 33.
Узел 35 переместился бы на место узла 33. Если мы исследуем бинарное дерево поиска, мы можем с уверенностью заключить, что все в левом поддереве каждого родителя меньше родителя, а все в правом поддереве каждого родителя больше, чем родитель.
Вот и все. Простой.
Если вам понравилось то, что вы прочитали, моя книга Иллюстративное введение в алгоритмы охватывает этот алгоритм и многое другое.
