Exclusão em BST: Três Casos
Trate a exclusão de folhas, de nós com um filho e de nós com dois filhos usando o sucessor em ordem, implementando o algoritmo do zero.
Exclusão em BST: Três Casos é uma aula grátis de Coding Interview Prep no CoddyKit. Esta é a aula 2 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Coding Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Coding Interview Prep inclui 4 aulas no total.
Por que a exclusão em BST é difícil
A exclusão em uma BST é a mais complexa das três operações fundamentais, pois remover um nó deve preservar a propriedade da BST em toda a árvore. Há três casos distintos, dependendo dos filhos do nó: ele não tem filhos (folha), tem um filho ou tem dois filhos. Cada caso exige uma estratégia diferente. Os entrevistadores gostam desse problema porque ele testa a manipulação de ponteiros, o raciocínio sobre casos-limite e o conhecimento do conceito de sucessor em ordem.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# Three cases for deleting a node:
# Case 1: Leaf node (no children) -> simply remove it
# Case 2: One child -> replace node with its child
# Case 3: Two children -> replace value with in-order successor
# then delete the in-order successor
print('BST delete: 3 cases based on number of children')Caso 1: excluindo um nó folha
Um nó folha não tem filhos. A exclusão é simples: retorne None da chamada recursiva, fazendo com que o pai defina seu ponteiro (esquerdo ou direito) como nulo. Esse é o caso-base que toda implementação de exclusão em BST deve tratar primeiro. Verifique se isso funciona no caso especial em que a árvore tem apenas um nó (a raiz é uma folha).
def find_min(node):
while node.left:
node = node.left
return node
# Demonstrating leaf deletion:
root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(7)
root.left.left = TreeNode(1) # leaf
root.left.right = TreeNode(4) # leaf
# To delete node 1 (leaf): set root.left.left = None
root.left.left = None
print(root.left.left) # None -- deleted
print(root.left.val) # 3 still intactCaso 2: nó com um filho
Quando um nó tem exatamente um filho, substitua o nó por esse filho. Retorne o filho não nulo da chamada recursiva para que o ponteiro do pai seja atualizado e ignore o nó excluído. Isso funciona perfeitamente tanto quando o único filho está à esquerda quanto quando está à direita — basta retornar aquele que existir.
# Demonstrating one-child deletion:
# Tree: 5
# / \
# 3 7
# \
# 4
# Delete node 3 (has only right child 4):
# Result: 5
# / \
# 4 7
root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(7)
root.left.right = TreeNode(4)
# In the recursive implementation:
# When we reach node 3 and it has no left child,
# we return root.right (node 4) to the parent.
# Parent sets its left pointer to 4, skipping 3.
print('One-child case: return the surviving child')Caso 3: nó com dois filhos
Quando um nó tem dois filhos, não podemos simplesmente removê-lo. Em vez disso, encontre o sucessor em ordem do nó (o menor valor da subárvore direita), copie esse valor para o nó atual e, em seguida, exclua o sucessor em ordem da subárvore direita. O sucessor tem no máximo um filho (não tem filho esquerdo), portanto sua exclusão se enquadra no Caso 1 ou no Caso 2 — que já sabemos tratar.
# Demonstrating two-child deletion:
# Tree: 5
# / \
# 3 7
# / \
# 6 9
# Delete node 5 (two children 3 and 7):
# In-order successor = 6 (smallest in right subtree)
# Step 1: replace 5's value with 6
# Step 2: delete 6 from right subtree
# Result: 6
# / \
# 3 7
# \
# 9
print('Two-child case: replace with in-order successor')Implementação completa da exclusão em BST
A exclusão recursiva completa combina os três casos. Encontre o nó a excluir comparando valores e, em seguida, trate o caso apropriado. O padrão de retornar a raiz (possivelmente modificada) em cada nível e atribuí-la novamente a root.left ou root.right trata com elegância todas as atualizações de ponteiros, sem exigir o rastreamento explícito do pai. A complexidade temporal é O(h).
def delete_node(root, key):
if not root:
return None # key not found
if key < root.val:
root.left = delete_node(root.left, key)
elif key > root.val:
root.right = delete_node(root.right, key)
else: # found the node to delete
if not root.left: # Case 1 or 2: no left child
return root.right
if not root.right: # Case 2: no right child
return root.left
# Case 3: two children -> find in-order successor
successor = find_min(root.right)
root.val = successor.val # copy successor value up
root.right = delete_node(root.right, successor.val) # delete successor
return root
root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(7)
root.right.left = TreeNode(6)
root.right.right = TreeNode(9)
root = delete_node(root, 5)
print(root.val) # 6 (successor replaced 5)Por que usar o sucessor em ordem?
O sucessor em ordem (o mínimo da subárvore direita) é usado em vez do máximo da subárvore esquerda porque ambas são escolhas válidas — usar qualquer uma preserva a propriedade de BST. O predecessor em ordem (o máximo da subárvore esquerda) também funciona. Algumas implementações alternam entre as duas opções para manter a árvore equilibrada. Em entrevistas, a versão com o sucessor em ordem é esperada com mais frequência; mencione que o predecessor funciona igualmente bem.
# Both approaches are valid for two-child deletion:
# Option A: Replace with in-order SUCCESSOR (min of right subtree)
# - Successor goes to current position
# - Delete successor from right subtree
# Option B: Replace with in-order PREDECESSOR (max of left subtree)
# - Predecessor goes to current position
# - Delete predecessor from left subtree
def find_max(node):
while node.right:
node = node.right
return node
# Using predecessor:
def delete_node_pred(root, key):
if not root:
return None
if key < root.val:
root.left = delete_node_pred(root.left, key)
elif key > root.val:
root.right = delete_node_pred(root.right, key)
else:
if not root.left:
return root.right
if not root.right:
return root.left
pred = find_max(root.left)
root.val = pred.val
root.left = delete_node_pred(root.left, pred.val)
return root
print('Both successor and predecessor deletion are correct')Excluindo todos os nós com um valor
Uma variação pede que você exclua todos os nós com valores dentro de um intervalo ou que correspondam a uma condição. Em uma BST, isso é eficiente: faça chamadas recursivas à subárvore apropriada com base nas comparações, aplicando a operação de exclusão sempre que a condição for satisfeita. A estrutura recursiva da exclusão em BST se estende naturalmente a esses cenários, sem exigir uma passagem de travessia separada.
# Delete all nodes with values outside [low, high]
def trim_bst(root, low, high):
if not root:
return None
if root.val < low:
# Entire left subtree is also < low, skip to right
return trim_bst(root.right, low, high)
if root.val > high:
# Entire right subtree is also > high, skip to left
return trim_bst(root.left, low, high)
# Current node is within range
root.left = trim_bst(root.left, low, high)
root.right = trim_bst(root.right, low, high)
return root
root = TreeNode(3)
root.left = TreeNode(0)
root.right = TreeNode(4)
root.left.right = TreeNode(2)
root.left.right.left = TreeNode(1)
root = trim_bst(root, 1, 3)
print(root.val, root.left.val) # 3 2Padrão de iterador de BST
O iterador de BST (LeetCode #173) retorna elementos em ordem crescente, um de cada vez, com tempo médio O(1) e espaço O(h). Implemente-o com uma pilha que simula a travessia iterativa em ordem: na construção, empilhe todos os nós à esquerda a partir da raiz. Em next(), retire o elemento do topo e empilhe todos os nós à esquerda da subárvore direita. Isso representa uma expansão controlada do algoritmo iterativo em ordem.
class BSTIterator:
def __init__(self, root):
self.stack = []
self._push_left(root)
def _push_left(self, node):
while node:
self.stack.append(node)
node = node.left
def next(self):
node = self.stack.pop()
if node.right:
self._push_left(node.right)
return node.val
def has_next(self):
return bool(self.stack)
root = TreeNode(7)
root.left = TreeNode(3)
root.right = TreeNode(15)
root.right.left = TreeNode(9)
it = BSTIterator(root)
while it.has_next():
print(it.next(), end=' ') # 3 7 9 15Análise de complexidade da exclusão de um nó
A exclusão em BST tem complexidade temporal O(h), em que h é a altura da árvore. Em uma BST equilibrada, isso corresponde a O(log n). Em uma árvore inclinada, a complexidade se degrada para O(n). Encontrar o sucessor em ordem acrescenta, no máximo, uma travessia O(h) adicional pela subárvore direita, o que não altera a complexidade geral. A complexidade espacial é O(h) para a pilha de chamadas na implementação recursiva.
# Complexity summary for BST operations:
# Operation | Balanced | Skewed
# ----------|-----------|-------
# Search | O(log n) | O(n)
# Insert | O(log n) | O(n)
# Delete | O(log n) | O(n)
# Min/Max | O(log n) | O(n)
# In-order | O(n) | O(n) (visits all nodes)
# The key: BST guarantees these complexities only when balanced.
# Python standard library has no balanced BST.
# Use sortedcontainers.SortedList for O(log n) ops in practice.
print('All BST core ops are O(h): O(log n) balanced, O(n) skewed')Soma de dois em uma BST
Soma de Dois IV em uma BST pergunta se algum par de nós soma um valor-alvo. Uma abordagem usa um conjunto: a travessia em ordem coleta valores enquanto verifica se target - current já existe no conjunto. Uma abordagem mais elegante usa simultaneamente um iterador de BST para frente e outro para trás, como dois ponteiros — isso evita espaço adicional além de O(h) para a pilha de cada iterador.
def find_target_bst(root, k):
seen = set()
def inorder(node):
if not node:
return False
if inorder(node.left):
return True
if k - node.val in seen:
return True
seen.add(node.val)
return inorder(node.right)
return inorder(root)
root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(6)
root.left.left = TreeNode(2)
root.left.right = TreeNode(4)
root.right.right = TreeNode(7)
print(find_target_bst(root, 9)) # True (2+7)
print(find_target_bst(root, 28)) # FalseConverter BST em uma árvore de soma dos maiores valores
A árvore de soma dos maiores valores (LeetCode #538) substitui o valor de cada nó pela soma de todos os valores maiores ou iguais a ele na BST. A ideia principal é fazer uma travessia em ordem inversa (direita → raiz → esquerda) para visitar os nós em ordem decrescente e acumular uma soma corrente. Isso leva O(n) de tempo e O(h) de espaço.
def bst_to_gst(root):
acc = [0] # running accumulated sum
def reverse_inorder(node):
if not node:
return
reverse_inorder(node.right) # visit larger values first
acc[0] += node.val
node.val = acc[0] # replace with cumulative sum
reverse_inorder(node.left)
reverse_inorder(root)
return root
root = TreeNode(4)
root.left = TreeNode(1)
root.right = TreeNode(6)
root.right.left = TreeNode(5)
root.right.right = TreeNode(7)
bst_to_gst(root)
print(root.val) # 4+5+6+7 = 22
print(root.right.val) # 5+6+7 = 18Verificação rápida
Teste sua compreensão dos conceitos de Estruturas de Dados e Algoritmos — Preparação para Entrevistas de Programação desta lição.
Recapitulação da lição
Nesta lição, você aprendeu: os três casos de exclusão em BST (folha, um filho, dois filhos), a técnica do sucessor em ordem para a exclusão de um nó com dois filhos e padrões recursivos claros, como o iterador de BST e a árvore BST de soma dos maiores valores. A seguir, validaremos a correção de BST e aproveitaremos as propriedades da travessia em ordem.
Perguntas Frequentes
A aula “Exclusão em BST: Três Casos” é grátis?
Sim — o texto completo de “Exclusão em BST: Três Casos” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Coding Interview Prep, atualize para CoddyKit PRO. O curso de Coding Interview Prep inclui 4 aulas no total.
O que vou aprender em “Exclusão em BST: Três Casos”?
Trate a exclusão de folhas, de nós com um filho e de nós com dois filhos usando o sucessor em ordem, implementando o algoritmo do zero. Você pratica Coding Interview Prep com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar Coding Interview Prep?
Nenhuma experiência prévia é necessária. Coding Interview Prep no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 2 de 4.
Quanto tempo leva a aula “Exclusão em BST: Três Casos”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de Coding Interview Prep?
Sim. Cada aula de Coding Interview Prep inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- Inserção e Busca em BST
- Exclusão em BST: Três Casos
- Validando BST e Propriedades da Ordem
- K-ésimo Menor, Soma de Intervalo e BST para Array Ordenado