Удаление в двоичном дереве поиска

Question

Учитель объяснил нам этот алгоритм для удаления узла в двоичном дереве поиска, но я не могу понять, как она работает, когда узел будет удален, имеет только один ребенок (я уже знаю, как это работает теоретически). .

алгоритм:

abc_delete(T, z) // z is the node that must be eliminated 
{
        if((z.left == NULL) && (z.right == NULL))
                y = z;
        else
                y = abr_successor(z);

        if(y.left != NULL)
                    x = y.left;
        else
                    x = y.right;

        if(x != NULL)
                x.p = y.p;

        if(y.p == NULL)
                T.root = x;
        else
        {
                if(y == (y.p).left)
                        (y.p).left = x;
                else
                        (y.p).right = x;
        }

        if(y != z)
                z.key = y.key;
        return y;
}

abr_successor(x)
{
        if(x == NULL)
                return NULL;
        if(x.right != NULL)
                return abr_min(x.right)
        y = x.p;
        while(y != NULL && x == y.right)
        {
                x = y;
                y = y.p;
        }
        return y;
}

.

Например, я хочу удалить номер узла $ 7 $ :

Но, не должен конечно быть, будь этим?

Answer 1

Вы Выбор, безусловно, правильный.

Тем не менее, нет ничего плохого в коде вашего учителя. Вот выдержка из CLRS.

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

Мы, безусловно, предпочитаем, что операция будет сделана самым простым способом или самым быстрым способом. Тем не менее, нет никаких требований, модификация должна быть сделана самым простым способом или даже любым простым способом. Также не требуется, чтобы модификация быть сделана самым быстрым или даже в любом случае. Все это требует, чтобы операция удаления должна производить другое двоичное поисковое дерево, которая имеет все узлы из заданного двоичного дерева поиска без этого конкретного узла (и более узлов). Как эти оставшиеся узлы образуют двоичное поиск, совершенно без ограничений.

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

Answer 2

Ваш рисунок - это правильное решение, однако ваша разборка к вашему коду учителя не точна (U MISS Intreepreed код)

Когда я впервые увидел, как тщательно прочитал код, не прочитал код, и я подумал (с 1-й картинки / рисунков) Ур преподаватель выполняет операцию удаления для особого вида BST, которая имеет дополнительные условия, чем относительный порядок, но Это не так

При удалении от BST (попытка выполнить варианты вашего кода, z - это узел, который будет удален)

Если z - узел листьев (нет детей), просто замените родительский указатель на него с NULL

Если z имеет 1 ребенок (олево или вправо не имеет значения) сделать родительский указатель указывает на его единственный ребенок

Это очень простое кодирование, в полупытовом коде

если (z.left== null) {fishing_delete (z, zrict); возвращаться(); // либо у нас есть только правый поддерева или нет }

// здесь мы уверены, что левый подмер

если (z. справа== нуль) {fishing_delete (z, z.left); возвращаться(); }

// Imity_delete имеет замену в качестве второго параметра, все петли в UR код учителя состоит в том, чтобы выяснить, что это в случае, у нас есть два субъекла

Если z имеет 2 детей, то вы должны избрать одного из них, чтобы занять свое место, и вот приходит код учителя (не в предыдущем случае)

В твоему фото представить u r Удаление "5" Этот длинный код предназначен для регулировки оставшегося подделки его 2 детей (как связать 7 и 3 и их детей в узел 12, сохраняя ограничение BST)

Если вам нужно подробное отслеживание, мы можем сделать это, но только если вы нашли это полезно, как старт