Modifique a implementação da árvore de busca binária para que ela lide corretamente com chaves duplicadas. Isto é, se uma chave já está na árvore, a nova dever’substituir a antiga.
Passo 1
O enunciado pede para ajustar a inserção em uma Árvore Binária de Busca de forma que, quando uma chave duplicada for inserida, em vez de criar um novo nó a implementação substitua o valor antigo pelo novo. Isso envolve trabalhar no método de inserção (insert) de uma BST.
O conteúdo envolvido é o algoritmo recursivo de inserção em BST. Normalmente, comparamos a chave nova com a do nó atual e decidimos ir para a subárvore esquerda (se menor) ou direita (se maior). Para lidar com duplicatas, precisamos tratar o caso de igualdade.
O conteúdo envolvido é o algoritmo recursivo de inserção em BST. Normalmente, comparamos a chave nova com a do nó atual e decidimos ir para a subárvore esquerda (se menor) ou direita (se maior). Para lidar com duplicatas, precisamos tratar o caso de igualdade.
Passo 2
No pseudocódigo de inserção, ao chegar num nó n:
– Se n for nulo, cria um novo nó com (chave, valor).
– Se key < n.key, faz n.left = insert(n.left, key, value).
– Se key > n.key, faz n.right = insert(n.right, key, value).
– Se key == n.key, ao invés de inserir uma nova folha, atualiza n.value = value.
Após qualquer uma dessas ações, retornamos n para manter a ligação da árvore.
– Se n for nulo, cria um novo nó com (chave, valor).
– Se key < n.key, faz n.left = insert(n.left, key, value).
– Se key > n.key, faz n.right = insert(n.right, key, value).
– Se key == n.key, ao invés de inserir uma nova folha, atualiza n.value = value.
Após qualquer uma dessas ações, retornamos n para manter a ligação da árvore.
Passo 3
A implementação final em Python (ou adaptável para outras linguagens) ficaria assim:
Resposta
class Node:
def init(self, key, value):
self.key = key
self.value = value
self.left = None
self.right = None
def init(self, key, value):
self.key = key
self.value = value
self.left = None
self.right = None
def insert(node, key, value):
if node is None:
# Se a posição estiver vazia, cria um novo nó
return Node(key, value)
if node is None:
# Se a posição estiver vazia, cria um novo nó
return Node(key, value)
if key < node.key:
# Insere na subárvore esquerda
node.left = insert(node.left, key, value)
elif key > node.key:
# Insere na subárvore direita
node.right = insert(node.right, key, value)
else:
# Chave duplicada: substitui o valor
node.value = value
return node