Árvore de busca binária (BST)

Estruturas de Dados e Algoritmos em Python

Miriam Antona

Software engineer

Definição

Subárvore esquerda de um nó:
- valores menores que o próprio nó
Subárvore direita de um nó:
- valores maiores que o próprio nó
As subárvores esquerda e direita devem ser árvores de busca binária

Representação esquemática de uma árvore de busca binária.

Implementação

class TreeNode:  
  def __init__(self, data, left=None, right=None):
    self.data = data
    self.left_child = left
    self.right_child = right

class BinarySearchTree:
  def __init__(self):
    self.root = None

Busca

Buscar 72

Representação esquemática de uma árvore de busca binária.

Busca

Buscar 72

Representação esquemática de uma árvore de busca binária onde o nó raiz está em amarelo.

Busca

Buscar 72

Representação esquemática de uma árvore de busca binária onde o nó raiz e a subárvore esquerda da raiz também estão em cinza. O primeiro nó da subárvore direita está em amarelo.

Busca

Buscar 72

Representação esquemática de uma árvore de busca binária. A subárvore esquerda do último nó raiz e o último nó raiz também estão em cinza. O novo nó raiz está em amarelo.

Busca

Buscar 72

Representação esquemática de uma árvore de busca binária onde o novo nó raiz está em amarelo e o restante dos nós em cinza.

Busca

Buscar 72

Representação esquemática de uma árvore de busca binária onde o novo nó raiz está em amarelo e o restante dos nós em cinza. O nó colorido tem o número 72 e está destacado.

Busca

def search(self, search_value):

    current_node = self.root

    while current_node:

      if search_value == current_node.data:

        return True

      elif search_value < current_node.data:

        current_node = current_node.left_child

      else:

        current_node = current_node.right_child

    return False

Inserção

def insert(self, data):

  new_node = TreeNode(data)

  if self.root == None:

Representação gráfica de um novo nó.

Inserção

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return

Representação gráfica do novo nó que se tornou o nó raiz.

Inserção

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:

Representação gráfica de um novo nó e um nó raiz com um filho à direita.

Inserção

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root

    while True:

      if data < current_node.data:

        if current_node.left_child == None:

Representação gráfica de um novo nó e um nó raiz com um filho à direita. O nó raiz é o current_node.

Inserção

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None:
          current_node.left_child = new_node
          return

Representação gráfica de um nó raiz com um filho à direita e um à esquerda. O nó raiz é o current_node. O novo nó é o filho à esquerda.

Inserção

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None: 
          current_node.left_child = new_node
          return
        else:

Representação gráfica de um novo nó e uma árvore de busca binária com alguns elementos. O nó raiz é o current_node.

Inserção

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None: 
          current_node.left_child = new_node
          return
        else:
          current_node = current_node.left_child

Representação gráfica de um novo nó e uma árvore de busca binária com alguns elementos. O current_node é o filho esquerdo da raiz.

Inserção

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None:
          current_node.left_child = new_node
          return
        else:
          current_node = current_node.left_child
      elif data > current_node.data:

        if current_node.right_child == None:

Representação gráfica de um novo nó e uma árvore de busca binária com uma subárvore esquerda.

Inserção

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None:
          current_node.left_child = new_node
          return
        else:
          current_node = current_node.left_child
      elif data > current_node.data:
        if current_node.right_child == None:

          current_node.right_child = new_node
          return

Representação gráfica de uma árvore de busca binária com uma subárvore esquerda. O novo nó agora é o filho direito da raiz.

Inserção

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None:
          current_node.left_child = new_node
          return
        else:
          current_node = current_node.left_child
      elif data > current_node.data:
        if current_node.right_child == None:

          current_node.right_child = new_node
          return
        else:

Representação gráfica de um novo nó e uma árvore de busca binária com alguns elementos.

Inserção

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None:
          current_node.left_child = new_node
          return
        else:
          current_node = current_node.left_child
      elif data > current_node.data:
        if current_node.right_child == None:

          current_node.right_child = new_node
          return
        else:
          current_node = current_node.right_child

Representação gráfica de um novo nó e uma árvore de busca binária com alguns elementos. O current_node é o filho direito da raiz.

Inserção

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None:
          current_node.left_child = new_node
          return 
        else:
          current_node = current_node.left_child
      elif data > current_node.data:
        if current_node.right_child == None:

          current_node.right_child = new_node
          return
        else:
          current_node = current_node.right_child

Representação gráfica de um novo nó e uma árvore de busca binária com alguns elementos. O current_node é o filho direito da raiz. O novo nó é o filho esquerdo do current_node.

Remoção

Sem filhos

Representação gráfica de uma árvore de busca binária com alguns elementos. Um dos nós está em vermelho porque será removido. Esse nó não tem filhos.

Remoção

Sem filhos
- deletar

Representação gráfica de uma árvore de busca binária com alguns elementos. O nó que seria removido desapareceu da árvore.

Remoção

Um filho

Representação gráfica de uma árvore de busca binária com alguns elementos. Um dos nós está em vermelho porque será removido. Esse nó tem um filho à direita.

Remoção

Um filho
- deletar
- conectar o filho ao pai do nó

Representação gráfica de uma árvore de busca binária com alguns elementos. O nó removido desapareceu e o nó raiz aponta para o filho direito do nó removido.

Remoção

Um filho
- deletar
- conectar o filho ao pai do nó

Representação gráfica de uma árvore de busca binária.

Remoção

Dois filhos

Representação gráfica de uma árvore de busca binária onde o nó raiz será removido e está em vermelho.

Remoção

Dois filhos
- substituir pelo sucessor
  - o nó com o menor valor maior que o do nó
- para achar o sucessor:

Representação gráfica de uma árvore de busca binária onde o nó raiz será removido e está em vermelho.

Remoção

Dois filhos
- substituir pelo sucessor
  - o nó com o menor valor maior que o do nó
- para achar o sucessor:
  - visitar o filho direito

Representação gráfica de uma árvore de busca binária onde o nó raiz será removido e está em vermelho. O filho direito da raiz está em amarelo.

Remoção

Dois filhos
- substituir pelo sucessor
  - o nó com o menor valor maior que o do nó
- para achar o sucessor:
  - visitar o filho direito
  - seguir pelos nós à esquerda até o fim

Representação gráfica de uma árvore de busca binária onde o nó raiz será removido e está em vermelho. Outro nó está em amarelo para encontrar o sucessor.

Remoção

Dois filhos
- substituir pelo sucessor
  - o nó com o menor valor maior que o do nó
- para achar o sucessor:
  - visitar o filho direito
  - seguir pelos nós à esquerda até o fim

Representação gráfica de uma árvore de busca binária onde o nó raiz será removido e está em vermelho. Outro nó está em amarelo para encontrar o sucessor.

Remoção

Dois filhos
- substituir pelo sucessor
  - o nó com o menor valor maior que o do nó
- para achar o sucessor:
  - visitar o filho direito
  - seguir pelos nós à esquerda até o fim

Representação gráfica de uma árvore de busca binária onde o nó raiz será removido e está em vermelho. Outro nó está em amarelo para encontrar o sucessor. O sucessor foi encontrado e é o número 13.

Remoção

Dois filhos
- substituir pelo sucessor
  - o nó com o menor valor maior que o do nó
- para achar o sucessor:
  - visitar o filho direito
  - seguir pelos nós à esquerda até o fim

Representação gráfica de uma árvore de busca binária. O nó raiz foi substituído pelo sucessor.

Remoção

Dois filhos
- substituir pelo sucessor
  - o nó com o menor valor maior que o do nó
- para achar o sucessor:
  - visitar o filho direito
  - seguir pelos nós à esquerda até o fim
  - se o sucessor tiver filho à direita:

Representação gráfica de uma árvore de busca binária onde o nó sucessor tem um filho à direita.

Remoção

Dois filhos
- substituir pelo sucessor
  - o nó com o menor valor maior que o do nó
- para achar o sucessor:
  - visitar o filho direito
  - seguir pelos nós à esquerda até o fim
  - se o sucessor tiver filho à direita:
    - o filho vira filho esquerdo do pai do sucessor.

Representação gráfica de uma árvore de busca binária onde o nó sucessor tinha um filho à direita. O filho do sucessor virou filho esquerdo do pai do sucessor e o nó raiz foi trocado pelo sucessor.

Usos

Ordenar listas com eficiência
Muito mais rápido para buscar que arrays e listas ligadas
Muito mais rápido para inserir e remover que arrays
Usado para implementar estruturas mais avançadas:
- conjuntos dinâmicos
- tabelas de consulta
- filas de prioridade

Vamos praticar!

Estruturas de Dados e Algoritmos em Python