Блог

Вопрос: Предположим, что другая структура данных содержит указатель на узел y в дереве двоичного поиска, и предположим, что y предшественник z удален из дерева процедурой TREE-DELETE . Какая проблема может возникнуть? Как можно TREE-DELETE переписать, чтобы решить эту проблему?

Я пытаюсь визуализировать ситуацию, если это может помочь, следующим образом:

TREE-DELETE алгоритм ниже. P[x] означает родителя x .

Проблема: Теперь предположим, что если удаляемый узел имеет два дочерних узла, то y он будет удален. Если указатель укажет на y , возникнут проблемы. В такой ситуации указатель должен указывать на узел z . Итак, мой вопрос, пожалуйста, как, если узел удален ( z как предполагает вопрос), имеет 2 дочерних элемента, то y , пожалуйста, будет удален? Насколько я помню, функция удаления работает в двоичном дереве не так. Он удалит узел и заменит его либо преемником, либо предшественником без каких-либо дальнейших действий. Если z преемник y был удален, тогда должен быть другой преемник узла y в случае, если дерево не пустое, имеет более 2 узлов, поэтому я не вижу, в чем здесь проблема, пожалуйста?

Изменить: после удаления y предшественника указатель будет продолжать указывать на y то, как я его вижу, и z будет удален?