В коде удаления из здесь.
Я не понимаю первый фрагмент кода удаления (где у узла нет двух дочерних элементов).
Если у удаляемого узла есть родитель и сам дочерний элемент (т. е. у узла есть один дочерний элемент), как это работает?
Код просто удаляет узел, а не устанавливает родительские указатели на осиротевшего потомка.
Я что-то упускаю?
Я могу ошибаться, но код на указанном сайте выглядит нормально. Я не проверял это, хотя.
Это верно, потому что функция удаления принимает один аргумент, который имеет тип узла BSTNode**. Это НЕ указатель на узел. Это указатель на указатель родительского узла на сам узел. Это может быть немного небрежно, но я должен признать, что после понимания того, что делает код, это элегантное в своем роде решение. Таким образом, когда вы переписываете (*node), вы не переписываете сам узел, вместо этого вы переписываете указатель родительского узла на узел. Фактически код делает то, что вы предложили, немного извращенным образом: D. Надеюсь, вы поняли, что я имел в виду, и я надеюсь, что я понял это правильно.
Я бы также рекомендовал вам прочитать дальше о красно-черных деревьях, так как в этой статье дается понимание только создания дерева, но описанная структура не имеет асимптотических границ для своей высоты. Если, например. вы вставляете отсортированные значения в эту структуру, это будет связный список вместо сбалансированного дерева.
