3

Estudando BST (arvore de busca binaria) não entendi algumas partes do código na função delete do "mycodeschool".

Essa parte do código, mais especificamente:

// Case 1:  No child
    if(root->left == NULL && root->right == NULL) { 
        delete root;
        root = NULL;
    }
//Case 2: One child 
    else if(root->left == NULL) {
        struct Node *temp = root;
        root = root->right;
        delete temp;
    }
  1. Não entendi porque em "Case 1" como o root pode receber NULL depois de receber o comando delete. Eu poderia simplesmente colocar root=NULL e só?

  2. E também em "Case 2" Quando se deleta temp, root também está sendo deletado, não? já que temp possui o mesmo endereço de root.

  3. E também não entendi a necessidade de deletar já que existe o comando root=root->right.

  4. E por que em "Case 1" o delete vem antes do comando principal root=NULL e em "Case 2" o delete tá depois do comando principal root=root->right?

1 Resposta 1

3

1: No Case 1 voçê está removendo um nó que não tem filhos da nem direita nem da esqueda. Remove ele da memória e seta como null para que o pai de root não aponte para um local da memória que foi 'desalocado';

2 e 3: Não, temp possui o endereço do 'antigo' root pois root agora está apontando para root->right . No Case 2 ele efetua a operação de remoção para nós que tem apenas 1 filho à direita. Quando ele remove temp da memória, ele está removendo o antigo root pois root agora passou a apontar para o nó da direita portanto temp aponta para um nó que não está em nenhuma posição da árvore sendo desnecessário deixar ele alocado na memória.

4: No Case 1 foi respondido no item 1.

No Case 2, primeiro ele pega a referencia do conteúdo para onde root está apontando e armazena em temp, faz root apontar para o único nó filho que tem à direita e depois remove o temp pois não tem mais necessidade dele alocado na mémoria. Ou seja, ele pega a referencia de root antes dele apontar para um novo local, e depois remove o antigo conteúdo de root.

Neste link tem algumas imagens que vai te auxiliar a entender melhor esse processo de deleção.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .