A função Delete é usada para excluir o nó especificado de uma árvore de pesquisa binária. No entanto, devemos excluir um nó de uma árvore de pesquisa binária de tal forma que a propriedade da árvore de pesquisa binária não seja violada. Existem três situações de exclusão de um nó da árvore de pesquisa binária.
O nó a ser excluído é um nó folha
É o caso mais simples, neste caso, substitua o nó folha pelo NULL e simplesmente libere o espaço alocado.
ciclo de vida de desenvolvimento de software
Na imagem a seguir, estamos excluindo o nó 85, pois o nó é um nó folha, portanto o nó será substituído por NULL e o espaço alocado será liberado.
O nó a ser excluído possui apenas um filho.
Neste caso, substitua o nó pelo seu filho e exclua o nó filho, que agora contém o valor a ser excluído. Simplesmente substitua-o por NULL e libere o espaço alocado.
bytes python para string
Na imagem a seguir, o nó 12 deve ser excluído. Tem apenas um filho. O nó será substituído por seu nó filho e o nó 12 substituído (que agora é o nó folha) será simplesmente excluído.
O nó a ser excluído possui dois filhos.
É um caso um pouco complexo em comparação com outros dois casos. No entanto, o nó que deve ser excluído é substituído por seu sucessor ou predecessor em ordem recursivamente até que o valor do nó (a ser excluído) seja colocado na folha da árvore. Após o procedimento, substitua o nó por NULL e libere o espaço alocado.
Na imagem a seguir, o nó 50 deve ser excluído, que é o nó raiz da árvore. A travessia em ordem da árvore fornecida abaixo.
programa c para comparação de strings
6, 25, 30, 50, 52, 60, 70, 75.
substitua 50 por seu sucessor em ordem 52. Agora, 50 será movido para a folha da árvore, que será simplesmente excluída.
Algoritmo
Excluir (ÁRVORE, ITEM)
Escreva 'item não encontrado na árvore' ELSE IF ITEM DATA
Excluir(ÁRVORE->ESQUERDA, ITEM)
ELSE SE ITEM > ÁRVORE -> DADOS
Excluir(ÁRVORE -> DIREITA, ITEM)
ELSE SE ÁRVORE -> ESQUERDA E ÁRVORE -> DIREITA
DEFINIR TEMP = findLargestNode(ÁRVORE -> ESQUERDA)
DEFINIR ÁRVORE -> DADOS = TEMP -> DADOS
Excluir (ÁRVORE -> ESQUERDA, TEMP -> DADOS)
OUTRO
DEFINIR TEMP = ÁRVORE
SE ÁRVORE -> ESQUERDA = NULO E ÁRVORE -> DIREITA = NULO
DEFINIR ÁRVORE = NULO
ELSE SE ÁRVORE -> ESQUERDA! = NULO
DEFINIR ÁRVORE = ÁRVORE -> ESQUERDA
OUTRO
DEFINIR ÁRVORE = ÁRVORE -> DIREITA
[FIM DO SE]
TEMPERATURA LIVRE
[FIM DO SE]
Função:
void deletion(Node*& root, int item) { Node* parent = NULL; Node* cur = root; search(cur, item, parent); if (cur == NULL) return; if (cur->left == NULL && cur->right == NULL) { if (cur != root) { if (parent->left == cur) parent->left = NULL; else parent->right = NULL; } else root = NULL; free(cur); } else if (cur->left && cur->right) { Node* succ = findMinimum(cur- >right); int val = succ->data; deletion(root, succ->data); cur->data = val; } else { Node* child = (cur->left)? Cur- >left: cur->right; if (cur != root) { if (cur == parent->left) parent->left = child; else parent->right = child; } else root = child; free(cur); } } Node* findMinimum(Node* cur) { while(cur->left != NULL) { cur = cur->left; } return cur; }