Árvore de Pesquisa Binária (Binary Search Tree)

Na ciência da computação binary search trees (BST), algumas vezes chamadas de árvores binárias ordenadas (ordered or sorted binary trees), é um tipo particular de container: estruturas de dados que armazenam "itens" (como números, nomes, etc.) na memória. Permite pesquisa rápida, adição e remoção de itens além de poder ser utilizado para implementar tanto conjuntos dinâmicos de itens ou, consultar tabelas que permitem encontrar um item por seu valor chave. E.g. encontrar o número de telefone de uma pessoa pelo seu nome.

Árvore de Pesquisa Binária mantem seus valores chaves ordenados, para que uma pesquisa e outras operações possam usar o princípio da pesquisa binária: quando pesquisando por um valor chave na árvore (ou um lugar para inserir uma nova chave), eles atravessam a árvore da raiz para a folha, fazendo comparações com chaves armazenadas nos nós da árvore e decidindo então, com base nas comparações, continuar pesquisando nas sub-árvores a direita ou a esquerda. Em média isto significa que cara comparação permite as operações pular metade da árvore, para que então, cada pesquisa, inserção ou remoção consuma tempo proporcional ao logaritmo do número de itens armazenados na árvore. Isto é muito melhor do que um tempo linear necessário para encontrar itens por seu valor chave em um array (desorndenado - unsorted), mas muito mais lento do que operações similares em tableas de hash (hash tables).

Uma pesquisa de árvore binária de tamanho 9 e profundidade 3, com valor 8 na raíz. As folhas não foram desenhadas.

Made with okso.app

Pseudocódigo para Operações Básicas

Inserção

insert(value)
  Pre: value has passed custom type checks for type T
  Post: value has been placed in the correct location in the tree
  if root = ø
    root ← node(value)
  else
    insertNode(root, value)
  end if
end insert

insertNode(current, value)
  Pre: current is the node to start from
  Post: value has been placed in the correct location in the tree
  if value < current.value
    if current.left = ø
      current.left ← node(value)
    else
      InsertNode(current.left, value)
    end if
  else
    if current.right = ø
      current.right ← node(value)
    else
      InsertNode(current.right, value)
    end if
  end if
end insertNode

Pesquisa

contains(root, value)
  Pre: root is the root node of the tree, value is what we would like to locate
  Post: value is either located or not
  if root = ø
    return false
  end if
  if root.value = value
    return true
  else if value < root.value
    return contains(root.left, value)
  else
    return contains(root.right, value)
  end if
end contains

Remoção

remove(value)
  Pre: value is the value of the node to remove, root is the node of the BST
      count is the number of items in the BST
  Post: node with value is removed if found in which case yields true, otherwise false
  nodeToRemove ← findNode(value)
  if nodeToRemove = ø
    return false
  end if
  parent ← findParent(value)
  if count = 1
    root ← ø
  else if nodeToRemove.left = ø and nodeToRemove.right = ø
    if nodeToRemove.value < parent.value
      parent.left ←  nodeToRemove.right
    else
      parent.right ← nodeToRemove.right
    end if
  else if nodeToRemove.left != ø and nodeToRemove.right != ø
    next ← nodeToRemove.right
    while next.left != ø
      next ← next.left
    end while
    if next != nodeToRemove.right
      remove(next.value)
      nodeToRemove.value ← next.value
    else
      nodeToRemove.value ← next.value
      nodeToRemove.right ← nodeToRemove.right.right
    end if
  else
    if nodeToRemove.left = ø
      next ← nodeToRemove.right
    else
      next ← nodeToRemove.left
    end if
    if root = nodeToRemove
      root = next
    else if parent.left = nodeToRemove
      parent.left = next
    else if parent.right = nodeToRemove
      parent.right = next
    end if
  end if
  count ← count - 1
  return true
end remove

Encontrar o Nó Pai

findParent(value, root)
  Pre: value is the value of the node we want to find the parent of
       root is the root node of the BST and is != ø
  Post: a reference to the prent node of value if found; otherwise ø
  if value = root.value
    return ø
  end if
  if value < root.value
    if root.left = ø
      return ø
    else if root.left.value = value
      return root
    else
      return findParent(value, root.left)
    end if
  else
    if root.right = ø
      return ø
    else if root.right.value = value
      return root
    else
      return findParent(value, root.right)
    end if
  end if
end findParent

Encontrar um Nó

findNode(root, value)
  Pre: value is the value of the node we want to find the parent of
       root is the root node of the BST
  Post: a reference to the node of value if found; otherwise ø
  if root = ø
    return ø
  end if
  if root.value = value
    return root
  else if value < root.value
    return findNode(root.left, value)
  else
    return findNode(root.right, value)
  end if
end findNode

Encontrar Mínimo

findMin(root)
  Pre: root is the root node of the BST
    root = ø
  Post: the smallest value in the BST is located
  if root.left = ø
    return root.value
  end if
  findMin(root.left)
end findMin

Encontrar Máximo

findMax(root)
  Pre: root is the root node of the BST
    root = ø
  Post: the largest value in the BST is located
  if root.right = ø
    return root.value
  end if
  findMax(root.right)
end findMax

Traversal

Na Ordem Traversal (InOrder Traversal)

inorder(root)
  Pre: root is the root node of the BST
  Post: the nodes in the BST have been visited in inorder
  if root = ø
    inorder(root.left)
    yield root.value
    inorder(root.right)
  end if
end inorder

Pré Ordem Traversal (PreOrder Traversal)

preorder(root)
  Pre: root is the root node of the BST
  Post: the nodes in the BST have been visited in preorder
  if root = ø
    yield root.value
    preorder(root.left)
    preorder(root.right)
  end if
end preorder

Pós Ordem Traversal (PostOrder Traversal)

postorder(root)
  Pre: root is the root node of the BST
  Post: the nodes in the BST have been visited in postorder
  if root = ø
    postorder(root.left)
    postorder(root.right)
    yield root.value
  end if
end postorder

Complexidades

Complexidade de Tempo

Access	Search	Insertion	Deletion
O(log(n))	O(log(n))	O(log(n))	O(log(n))

Complexidade de Espaço

O(n)