Exclusão em uma Árvore de busca Binária

Question

O professor explicou-nos que este algoritmo para a exclusão de um nó em uma árvore de busca binária, mas eu não consigo entender como ele funciona quando o nó a ser eliminado tem apenas um filho (eu já sei como funciona teoricamente).

Algoritmo:

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;
}

Por exemplo, eu quero apagar o número do nó $7$:

Mas, não deveria o resultado final será este?

Answer 1

A escolha é certamente correta.

No entanto, não há nada de errado com o seu professor do código.Aqui está um excerto do CLRS.

As operações de inserção e exclusão de causar o conjunto dinâmico representado por uma árvore de busca binária para a mudança.A estrutura de dados deve ser modificado para refletir essa alteração, mas de tal forma que a pesquisa binária-árvore de propriedade continua a manter.

Nós certamente preferir a operação ser feita da maneira mais fácil ou o caminho mais rápido.No entanto, não há nenhuma exigência de que a modificação deve ser feita da maneira mais fácil ou até mesmo em qualquer forma fácil.Nem ele requer que a modificação seja feita da forma mais rápida ou até mesmo em qualquer forma rápida.Tudo o que requer que a operação de exclusão deve produzir outra árvore de busca binária que tem todos os nós de árvore de busca binária, sem que nó específico (e não mais de nós).Como os nós restantes formam um binário de pesquisa de árvore é completamente livre de restrições.

Seu professor do código, por outro lado, é, provavelmente, o mais curto limpar o código que faz o trabalho.Quanto mais eu estudo, mais engenho que eu encontrar.

Answer 2

Seu desenho é a solução correta, no entanto ur analisar ur professor de código não é preciso (u mis interepreted o código)

Quando eu vi pela primeira vez ur Q eu não li o código cuidadosamente & eu pensei (a partir de 1º pic/desenho) ur professor está a efectuar uma operação de exclusão para um tipo especial de BST que tem mais condições do que a ordem relativa, mas este não é o caso

Quando a exclusão de um BST (tentando seguir ur código de variáveis, Z é o nó a ser excluído)

Se Z é um nó folha (sem filhos), basta substituir o ponteiro do pai para com NULL

se Z tem 1 criança (seja de esquerda ou direita, não importa) fazer o ponteiro do pai aponta para o seu filho único

Isso é muito simples de codificação, em um semi-pseudo-código

Se (Z. esquerdo == NULL) { Physical_Delete(Z, Zright);return();//nós, têm apenas direito subárvore ou nenhum }

// Aqui nós r a certeza que existe uma subárvore esquerda

Se (Z.direito == NULL) { Physical_Delete(Z, Z. esquerda);return();}

//physical_Delete a substituição como o 2º parâmetro, todos os loops em ur professor de código é descobrir o que é meter temos duas subárvores

Se Z tem 2 filhos, então vc tem que escolher um deles para ocupar o seu lugar, e aqui vem a ur do professor de código (não no caso anterior)

Em ur pic imaginar u r a exclusão de "5" longo deste código é para ajustar o restante subárvore de seus 2 filhos (como link 7 & 3 & seus filhos para o nó 12-manter o BST restringir)

Se precisam de rastreamento detalhado nós podemos fazer isso, mas somente se u isto pode ser útil como um começo