Понимание реализации удаления в двоичном дереве поиска (BST) с помощью рекурсивных вызовов

Question

У меня возникли проблемы с пониманием того, как реализовать операцию удаления в BST.Я могу реализовать find() и insert() без особых проблем и понять, что происходит, но бороться с удалением.

Процесс удаления, как я понимаю, включает обновление родительского узла, для которого мы хотим удалить правую или левую ссылку(в зависимости), чтобы ссылаться либо на null, дочерний узел узла, который мы хотим удалить (когда удаляемый узел имеет один дочерний элемент), либо заменить его своим преемником по порядку (когда удаляемый узел имеет 2 дочерних элемента).

Большинство реализаций, которые я видел, были Java здесь .Кажется, использовать рекурсию таким образом, что делает явную ссылку на родителя не требуется.Я думаю, что это то, где я все время путаюсь.

Кто-нибудь может объяснить, как здесь работают рекурсивные вызовы и как они этого достигают?

Answer 1

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

надеюсь, что это полезно