Árvore binária de busca (BST)
Última atualização
Uma árvore binária de busca mantém seus valores em ordem: para cada nó, todos os valores da subárvore esquerda são menores e todos os da subárvore direita são maiores. Para inserir ou encontrar um valor você começa na raiz e vai repetidamente para a esquerda ou para a direita conforme a comparação, de modo que cada passo divide o espaço de busca pela metade. Pressione reproduzir acima para ver os valores posicionados por comparação e uma busca descendo pela árvore.
Em uma árvore balanceada essas operações rodam em tempo O(log n). O problema: inserir dados já ordenados faz a árvore degenerar em uma lista encadeada com operações O(n), que é exatamente por que existem variantes autobalanceadas como as árvores AVL e rubro-negra.
Complexidade de tempo e espaço
| Operação | Balanceada | Pior caso (desbalanceada) |
|---|---|---|
| Busca | O(log n) | O(n) |
| Inserção | O(log n) | O(n) |
| Remoção | O(log n) | O(n) |
| Espaço | O(n) | O(n) |
Passo a passo (inserção)
| Passo | O que acontece |
|---|---|
| 1 | Se a árvore estiver vazia, o novo valor se torna a raiz. |
| 2 | Caso contrário, comece na raiz. |
| 3 | Se o valor for menor, vá para o filho esquerdo; se for maior, vá para a direita. |
| 4 | Repita até chegar a um espaço vazio. |
| 5 | Anexe ali o novo valor como uma folha. |
Exemplo resolvido
Inserindo [5, 3, 8, 1, 4] em uma árvore vazia, um valor de cada vez:
| Inserir | Caminho percorrido | Ação |
|---|---|---|
5 | - | A árvore está vazia, então 5 se torna a raiz. |
3 | 5 | 3 < 5, vá para a esquerda; o espaço está vazio, anexe 3 como filho esquerdo de 5. |
8 | 5 | 8 > 5, vá para a direita; o espaço está vazio, anexe 8 como filho direito de 5. |
1 | 5 -> 3 | 1 < 5 vá para a esquerda, depois 1 < 3 vá para a esquerda; anexe 1 como filho esquerdo de 3. |
4 | 5 -> 3 | 4 < 5 vá para a esquerda, depois 4 > 3 vá para a direita; anexe 4 como filho direito de 3. |
Quando usar uma árvore binária de busca
| Use quando | Evite quando |
|---|---|
| Você precisa de ordem mais buscas rápidas e as inserções chegam em ordem aleatória. | Seus dados chegam já ordenados: uma BST desbalanceada degrada para O(n) por operação. |
| Você quer que o percurso em ordem retorne os valores em sequência ordenada de graça. | Você só precisa de testes de pertencimento sem ordem: uma tabela hash oferece buscas O(1) em média. |
| Você precisa de consultas por intervalo ou do sucessor/antecessor de uma chave. | Você precisa de garantias O(log n): use uma árvore autobalanceada AVL ou rubro-negra. |
| O conjunto de dados muda com frequência e atualizar um arranjo ordenado seria custoso. | O conjunto de dados é fixo e somente leitura: um arranjo ordenado com busca binária é mais simples e melhor para o cache. |
Código de Binary Search Tree
Uma implementação limpa e executável de Binary Search Tree em Python, JavaScript, Java, C++, C. Escolha uma linguagem, copie o código ou abra-o já carregado no Playground da Coddy.
Código de Binary Search Tree em Python
Python
1class Node:2 def __init__(self, key):3 self.key = key4 self.left = None5 self.right = None6
7
8def insert(node, key):9 if node is None:10 return Node(key)11 if key < node.key:12 node.left = insert(node.left, key)13 elif key > node.key:14 node.right = insert(node.right, key)15 return node # duplicates are ignored16
17
18def search(node, key):19 if node is None:20 return False21 if key == node.key:22 return True23 if key < node.key:24 return search(node.left, key)25 return search(node.right, key)26
27
28def inorder(node):29 if node is None:30 return []31 return inorder(node.left) + [node.key] + inorder(node.right)32
33
34root = None35for key in [8, 3, 10, 1, 6, 14, 4, 7]:36 root = insert(root, key)37
38print("Inorder (sorted):", inorder(root))39print("search(6): ", search(root, 6))40print("search(5): ", search(root, 5))Código de Binary Search Tree em JavaScript
JavaScript
1class Node {2 constructor(value) {3 this.value = value;4 this.left = null;5 this.right = null;6 }7}8
9class BinarySearchTree {10 constructor() {11 this.root = null;12 }13
14 insert(value) {15 const attach = (node) => {16 if (!node) return new Node(value);17 if (value < node.value) node.left = attach(node.left);18 else node.right = attach(node.right);19 return node;20 };21 this.root = attach(this.root);22 }23
24 search(value) {25 let current = this.root;26 while (current) {27 if (value === current.value) return true;28 current = value < current.value ? current.left : current.right;29 }30 return false;31 }32
33 // Inorder traversal of a BST visits values in sorted order34 inorder(node = this.root, out = []) {35 if (!node) return out;36 this.inorder(node.left, out);37 out.push(node.value);38 this.inorder(node.right, out);39 return out;40 }41}42
43const bst = new BinarySearchTree();44for (const value of [8, 3, 10, 1, 6, 14, 4]) bst.insert(value);45console.log("Inorder:", bst.inorder().join(" "));46console.log("search(6):", bst.search(6));47console.log("search(7):", bst.search(7));Código de Binary Search Tree em Java
Java
1public class Main {2 static class Node {3 int key;4 Node left, right;5 Node(int key) { this.key = key; }6 }7
8 static Node insert(Node node, int key) {9 if (node == null) return new Node(key);10 // Smaller keys go left, larger keys go right11 if (key < node.key) node.left = insert(node.left, key);12 else if (key > node.key) node.right = insert(node.right, key);13 return node;14 }15
16 static boolean search(Node node, int key) {17 if (node == null) return false;18 if (key == node.key) return true;19 return key < node.key ? search(node.left, key) : search(node.right, key);20 }21
22 static void inorder(Node node, StringBuilder sb) {23 if (node == null) return;24 inorder(node.left, sb);25 sb.append(node.key).append(" ");26 inorder(node.right, sb);27 }28
29 public static void main(String[] args) {30 Node root = null;31 int[] keys = {8, 3, 10, 1, 6, 14, 4};32 for (int k : keys) root = insert(root, k);33
34 StringBuilder sb = new StringBuilder();35 inorder(root, sb);36 System.out.println("Inorder (sorted): " + sb.toString().trim());37 System.out.println("search 6: " + search(root, 6));38 System.out.println("search 7: " + search(root, 7));39 }40}Código de Binary Search Tree em C++
C++
1#include <iostream>2
3struct Node {4 int value;5 Node* left = nullptr;6 Node* right = nullptr;7 explicit Node(int v) : value(v) {}8};9
10Node* insert(Node* root, int value) {11 if (root == nullptr) return new Node(value);12 if (value < root->value) root->left = insert(root->left, value);13 else if (value > root->value) root->right = insert(root->right, value);14 return root; // duplicates are ignored15}16
17bool contains(const Node* root, int value) {18 // Walk down: smaller goes left, larger goes right19 while (root != nullptr) {20 if (value == root->value) return true;21 root = value < root->value ? root->left : root->right;22 }23 return false;24}25
26void inorder(const Node* node) {27 if (node == nullptr) return;28 inorder(node->left);29 std::cout << node->value << " ";30 inorder(node->right);31}32
33int main() {34 Node* root = nullptr;35 for (int value : {50, 30, 70, 20, 40, 60, 80}) {36 root = insert(root, value);37 }38 std::cout << "Sorted: ";39 inorder(root);40 std::cout << "\n" << std::boolalpha;41 std::cout << "contains(40): " << contains(root, 40) << "\n";42 std::cout << "contains(45): " << contains(root, 45) << "\n";43 return 0;44}Código de Binary Search Tree em C
C
1#include <stdbool.h>2#include <stdio.h>3#include <stdlib.h>4
5typedef struct Node {6 int value;7 struct Node* left;8 struct Node* right;9} Node;10
11Node* newNode(int value) {12 Node* n = malloc(sizeof(Node));13 n->value = value;14 n->left = n->right = NULL;15 return n;16}17
18Node* insert(Node* root, int value) {19 if (root == NULL) return newNode(value);20 if (value < root->value) root->left = insert(root->left, value);21 else if (value > root->value) root->right = insert(root->right, value);22 return root; // duplicates are ignored23}24
25bool contains(const Node* root, int value) {26 // Walk down: smaller goes left, larger goes right27 while (root != NULL) {28 if (value == root->value) return true;29 root = value < root->value ? root->left : root->right;30 }31 return false;32}33
34void inorder(const Node* node) {35 if (node == NULL) return;36 inorder(node->left);37 printf("%d ", node->value);38 inorder(node->right);39}40
41int main(void) {42 int values[] = {50, 30, 70, 20, 40, 60, 80};43 Node* root = NULL;44 for (int i = 0; i < 7; i++) root = insert(root, values[i]);45 printf("Sorted: ");46 inorder(root);47 printf("\n");48 printf("contains(40): %s\n", contains(root, 40) ? "true" : "false");49 printf("contains(45): %s\n", contains(root, 45) ? "true" : "false");50 return 0;51}Perguntas frequentes sobre a árvore binária de busca
Qual é a complexidade de tempo de uma árvore binária de busca?
Busca, inserção e remoção são
O(log n) em uma árvore balanceada, porque cada comparação descarta metade dos nós restantes. No pior caso, uma árvore desbalanceada em forma de cadeia por inserções ordenadas, elas degradam para O(n).Qual é a diferença entre uma árvore binária e uma árvore binária de busca?
Uma árvore binária é qualquer árvore em que cada nó tem no máximo dois filhos, sem regra de ordem. Uma árvore binária de busca acrescenta a invariante de que os valores da subárvore esquerda são menores e os da direita são maiores que o nó, o que possibilita buscas rápidas.
Por que uma árvore binária de busca pode ficar lenta?
Se os valores forem inseridos em ordem crescente (ou decrescente), cada novo nó vai para o mesmo lado, produzindo uma árvore alta e desbalanceada que se comporta como uma lista encadeada:
O(n) por operação. Árvores autobalanceadas (AVL, rubro-negra) rotacionam nós para evitar isso.Qual é a diferença entre uma árvore binária de busca e uma tabela hash?
Uma tabela hash oferece buscas
O(1) em média, mas armazena as chaves sem nenhuma ordem, então não pode responder consultas por intervalo ou de sucessor. Uma árvore binária de busca é um pouco mais lenta com O(log n), mas mantém as chaves ordenadas, permitindo percorrê-las em ordem e encontrar valores próximos. Escolha uma BST quando a ordem importa e uma tabela hash quando você só precisa de testes de pertencimento.Quando devo usar uma árvore autobalanceada em vez de uma BST simples?
Use uma árvore autobalanceada (AVL, rubro-negra) sempre que não puder controlar a ordem de inserção e precisar de desempenho
O(log n) garantido. Uma BST simples serve para ensino, para conjuntos pequenos ou quando as chaves chegam em ordem aleatória, mas não protege contra o pior caso desbalanceado.Um percurso em ordem de uma BST retorna valores ordenados?
Sim. Visitar a subárvore esquerda, depois o nó e então a subárvore direita produz as chaves em ordem crescente, o que decorre diretamente da invariante da BST. Um erro comum é esperar o mesmo de uma árvore binária simples: sem a regra de ordem, o percurso em ordem não produz nenhuma sequência significativa.
Recursos relacionados
Mais visualizações
