Corrigindo ponteiros na função de exclusão de árvore binária (nó com 2 crianças)

Question

Estou tendo um pouco de problema em pensar em como diabos conserto os ponteiros apropriados ao tentar excluir um nó de uma árvore binária onde esse nó tem 2 filhos.

Eu entendo o conceito básico e estou basicamente apenas tendo problemas para consertar os ponteiros ...

Então, basicamente, minha função de exclusão é feita principalmente e todos os casos já estão funcionando (no que diz respeito aos meus testes extensos, tudo funcionou bem), só estou perdendo o nó do caso com 2 filhos. Digamos que estamos dentro do else if que lida com esse caso:

Eu terei 2 ponteiros lá, currPtr que mantém o nó a ser excluído, prevPtr que mantém o nó pai. Eu também tenho uma variável chamada fromLeft que define se o currPtr Pai vem do ponteiro esquerdo ou direito prevPtr. Então, eu tenho uma chamada para outra função chamada extractMin(Tree *t) que extrai o menor valor na árvore. Se eu chamar essa função com currPtr->right como argumento, o sucessor de currPtr será extraído da árvore (a função a excluirá da árvore, consertará os ponteiros e devolverá o ponteiro do nó). O ponteiro sucessor será salvo tempPtr.

Aqui está a estrutura da minha árvore:

typedef int TreeElement;

typedef struct sTree {
   TreeElement item;

   struct sTree *left;
   struct sTree *right;
} Tree;

E o código para a função de extrato:

Tree *extractMin(Tree *tree) {
    Tree *prevPtr = NULL;
    Tree *currPtr = tree;

    while(currPtr->left) {
        prevPtr = currPtr;
        currPtr = currPtr->left;
    }

    if(prevPtr) prevPtr->left = currPtr->right;

    // inorder successor
    return currPtr;
}

O código acima está faltando o caso aqui a árvore só tem um nó, o nó raiz, não funciona corretamente e também não verifica se a árvore tem nenhum nós, mas funciona quando uma árvore tem alguns nós.

Então, como faço para corrigir os ponteiros necessários no else if Para a exclusão do nó? Além disso, lembre -se de que o left e right ponteiros nos nós da árvore sempre estarão apontando em algum lugar ou estar NULL.

A propósito, eu quero fazer isso iterativo.

Answer 1

Atualizada: Então, você deseja manter a ordem dos nós, substituindo o nó por seu sucessor ou antecessor direto.

Vamos supor que a árvore abaixo seja ordenada. A ordem dos nós é:

H < D < I < B < J < E < K < A < F < M < C < N < G < O

Você deseja excluir um nó (a) que tenha dois filhos. Você puxa o seu antecessor de ordem (k) ou o sucessor (f) filho do nó no lugar do original. Vamos escolher o sucessor. É assim que você o encontra: você atravessa os filhos de esquerda de C até encontrar um que não tenha filhos deixados; Este é o sucessor direto da Order de A.

       A
   B       C
 D   E   F   G
H I J K   M N O

Então F é puxado para cima e a subárvore esquerda de A não é tocada. No entanto, agora M também deve ser puxado para cima, para se tornar o filho esquerdo de C (isso é feito em seu extractMin()).

Depois de todos os rearranjos, você recebe

       F
   B       C
 D   E   M   G
H I J K     N O

No código, esta é a minha solução. Eu adicionei um cheque nulo para extractMin() Para simplificar o código do chamador, então não preciso else if.

Atualizada extractMin() Para cobrir o caso quando tree não tem filhos.

Tree *extractMin(Tree *parent, Tree *tree) {
    if (!tree) return NULL;

    Tree *prevPtr = NULL;
    Tree *currPtr = tree;

    while(currPtr->left) {
        prevPtr = currPtr;
        currPtr = currPtr->left;
    }

    if (prevPtr) {
        prevPtr->left = currPtr->right;
    } else if (parent) {
        parent->right = currPtr->right;
    }

    // inorder successor
    return currPtr;
}

// prevPtr is the parent, currPtr is the node to be deleted
Tree *successor = extractMin(currPtr, currPtr->right);
successor->left = currPtr->left;
successor->right = currPtr->right;
if (fromLeft) {
    prevPtr->left = successor;
} else {
    prevPtr->right = successor;
}
// Now currPtr can be destroyed

Observe que este código não foi testado, então não garanto nada :-)

Observe que exclusão repetida como essa podem tornar a árvore desequilibrada (ou seja, alguns caminhos ficarão muito mais longos que os outros). As árvores de classificação binária fazem deleções dessa maneira, mas também usam o reequilíbrio depois para manter a árvore próxima ao ideal (onde cada folha está no mesmo nível, como no meu primeiro exemplo acima).

Answer 2

A resposta do livro é substituir o nó em questão por seu descendente à esquerda.

                6
         3             8
     2      4      7      9
   1          5             10

Se quisermos remover 3, podemos substituí -lo por 4 e depois puxar 5 para o orifício para onde 4 foi. Sempre podemos fazer isso, e isso preservará a travessia em ordem.

OK. Olhando para o seu código, é isso que você deseja:

//in your function
    else if (/*has 2 nodes*/) {
        currPtr->item = extractMin(currPtr->right, &(currPtr->right))->item;
    }

Tree *extractMin(Tree *tree, Tree ** back) {
    Tree *currPtr = tree;

    while(currPtr->left) {
        back    = &(currPtr->left);
        currPtr = currPtr->left;
    }

    *back = currPtr->right;

    // inorder successor
    return currPtr;
}

O argumento ** nos permite lidar com o caso em que usamos os nós excluídos, criança certa imediata:

     3   <--deleting this node
   /   \   <--back points to this edge.
  2     4   <--extractMin is called on this node and returns this node,
         \
          5   <-- (*back) now points to this node. 

Pense na nova extractmina em 2 casos.

1. No primeiro caso, passamos pelo loop pelo menos uma vez. Se tivéssemos deixado o PrevPtr no código, veríamos isso após o loop, back == &(prevPtr->left); (por exemplo, modificação *Voltar irá modificar prevptr-> à esquerda). Portanto, é o mesmo que o seu código acima.
2. No segundo caso, não passamos pelo loop. Nesse caso, back aponta para um link que não poderíamos obter de outra maneira (a menos que modifiquemos o Extractmin para iniciar um nível mais alto).

Outra maneira de pensar sobre isso é que (*de volta) sempre aponta para Currptr (reserve um momento e verifique isso); portanto, aponta para a borda que precisamos modificar se estamos removendo o currptr.

Answer 3

Se você está falando sério sobre isso, dê uma olhada nas árvores AVL:

http://en.wikipedia.org/wiki/avl_tree

Eles podem ser complicados de implementar, mas permanecerão equilibrados devido às rotações que você executa em inserções e exclusões.