Код доступен ЗДЕСЬ
Сегодня давайте углубимся в BST.
Я написал основную функцию BST в классе TreeNode, отличную от кода в day03, который находится в классе BinarySearchTree. Оба варианта приемлемы.
Примечание. BST не может содержать повторяющиеся данные
Как удалить BST:
Прежде всего, найдите целевой ключ, который мы хотим удалить, используя аналогичный метод с поиском и вставкой.
Во-вторых, удалите целевой узел! Есть 3 варианта обработки:
- 1- У удаляемого узла нет дочерних элементов.
- 2- У удаляемого узла есть 1 дочерний элемент.
- 3- У удаляемого узла есть 2 дочерних элемента.
Первый самый простой. Просто удалите узел.
Второй пока легкий. Просто возьмите левого или правого ребенка, чтобы заменить его.
Третий самый сложный. Сначала найдите неупорядоченного преемника, который является наименьшим узлом в правом поддереве. Во-вторых, замените ключ, который мы хотим удалить, на преемник. В-третьих, удалите узел-преемник.
Как получить доступ к следующему большему узлу (также известному как узел-преемник)?
Разделим эту задачу на три случая
- 1- У узла есть правый дочерний элемент.
- 2- Узел не имеет правого дочернего элемента, но является левым дочерним элементом своего родителя.
- 3- Узел не имеет правильного дочернего элемента, но является правым дочерним элементом своего родителя.
В случае 1 мы знаем, что все элементы в правом поддереве больше, чем узел. Задача состоит в том, чтобы найти наименьший элемент из всех элементов, превышающих узел. Итак, просто найдите самого левого ребенка правого ребенка.
В случае удаления это очень просто. Потому что единственный случай, когда нам нужно найти преемника, — это когда у узла есть два потомка, что означает, что он подходит для случая 1.
Случай 2 и 3 сложнее, подумайте об этом. Ответы ниже, но просто подумайте, почему. Добро пожаловать, чтобы оставить комментарий для обсуждения.
В случае 2, поскольку правого потомка нет, при обходе по порядку следующим должен быть его правый родитель.
В случае 3 при обходе по порядку следующим должен быть его правый родитель левого родителя.
