Neste tutorial, você aprenderá como funciona a árvore de pesquisa binária. Além disso, você encontrará exemplos funcionais de árvore de pesquisa binária em C, C ++, Java e Python.
A árvore de pesquisa binária é uma estrutura de dados que nos permite manter rapidamente uma lista ordenada de números.
- É chamada de árvore binária porque cada nó da árvore tem no máximo dois filhos.
- É chamado de árvore de pesquisa porque pode ser usado para pesquisar a presença de um número no
O(log(n))tempo.
As propriedades que separam uma árvore de pesquisa binária de uma árvore binária regular são
- Todos os nós da subárvore esquerda são menores que o nó raiz
- Todos os nós da subárvore direita são mais do que o nó raiz
- Ambas as subárvores de cada nó também são BSTs, ou seja, têm as duas propriedades acima
Uma árvore com uma subárvore direita com um valor menor que a raiz é mostrada para demonstrar que não é uma árvore de pesquisa binária válida
A árvore binária à direita não é uma árvore de pesquisa binária porque a subárvore direita do nó "3" contém um valor menor que ele.
Existem duas operações básicas que você pode realizar em uma árvore de pesquisa binária:
Operação de Pesquisa
O algoritmo depende da propriedade do BST de que se cada subárvore esquerda tiver valores abaixo da raiz e cada subárvore direita tiver valores acima da raiz.
Se o valor estiver abaixo da raiz, podemos dizer com certeza que o valor não está na subárvore certa; precisamos pesquisar apenas na subárvore esquerda e se o valor estiver acima da raiz, podemos dizer com certeza que o valor não está na subárvore esquerda; precisamos pesquisar apenas na subárvore certa.
Algoritmo:
If root == NULL return NULL; If number == root->data return root->data; If number data return search(root->left) If number> root->data return search(root->right)
Vamos tentar visualizar isso com um diagrama.
4 não foi encontrado, atravessar pela subárvore esquerda de 8 
4 não foi encontrado, atravessar pela subárvore direita de 3 
4 não foi encontrado, então atravessar pela subárvore esquerda de 6 4 foi encontrado
Se o valor for encontrado, retornamos o valor para que seja propagado em cada etapa de recursão, conforme mostrado na imagem abaixo.
Se você deve ter notado, chamamos a pesquisa de retorno (nó de estrutura *) quatro vezes. Quando retornamos o novo nó ou NULL, o valor é retornado repetidas vezes até que a pesquisa (root) retorne o resultado final.
Se o valor for encontrado em qualquer uma das subárvores, ele é propagado para que no final seja retornado, caso contrário, é retornado nulo
Se o valor não for encontrado, eventualmente alcançamos o filho esquerdo ou direito de um nó folha que é NULL e é propagado e retornado.
Operação de inserção
Inserir um valor na posição correta é semelhante a pesquisar, porque tentamos manter a regra de que a subárvore esquerda é menor que a raiz e a subárvore direita é maior que a raiz.
Continuamos indo para a subárvore direita ou subárvore esquerda dependendo do valor e quando chegarmos a um ponto que a subárvore esquerda ou direita é nula, colocamos o novo nó lá.
Algoritmo:
If node == NULL return createNode(data) if (data data) node->left = insert(node->left, data); else if (data> node->data) node->right = insert(node->right, data); return node;
O algoritmo não é tão simples quanto parece. Vamos tentar visualizar como adicionamos um número a um BST existente.
4 <8 então, transversal ao filho esquerdo de 8 
4> 3 então, transversal ao filho direito de 8 
4 <6 então, transversal ao filho esquerdo de 6 
Insira 4 como um filho esquerdo de 6
Anexamos o nó, mas ainda temos que sair da função sem causar nenhum dano ao resto da árvore. É aqui que o return node;no final se torna útil. No caso de NULL, o nó recém-criado é retornado e anexado ao nó pai, caso contrário, o mesmo nó é retornado sem qualquer alteração à medida que subimos até retornarmos à raiz.
Isso garante que, conforme subimos na árvore, as outras conexões de nó não sejam alteradas.
Imagem mostrando a importância de retornar o elemento raiz no final para que os elementos não percam sua posição durante a etapa de recursão ascendente.
Operação de Exclusão
Existem três casos para excluir um nó de uma árvore de pesquisa binária.
Caso I
No primeiro caso, o nó a ser excluído é o nó folha. Nesse caso, simplesmente exclua o nó da árvore.
4 deve ser excluído 
Exclua o nó
Caso II
No segundo caso, o nó a ser excluído encontra-se com um único nó filho. Nesse caso, siga as etapas abaixo:
- Substitua esse nó por seu nó filho.
- Remova o nó filho de sua posição original.
6 deve ser excluído, 
copie o valor de seu filho para o nó e exclua a 
árvore final filho
Caso III
No terceiro caso, o nó a ser excluído possui dois filhos. Nesse caso, siga as etapas abaixo:
- Obtenha o sucessor em ordem desse nó.
- Substitua o nó pelo sucessor do pedido.
- Remova o sucessor inorder de sua posição original.
3 deve ser excluído Copie o valor do sucessor em ordem (4) para o nó 
Exclua o sucessor em ordem
Exemplos de Python, Java e C / C ++
Python Java C C ++ # Binary Search Tree operations in Python # Create a node class Node: def __init__(self, key): self.key = key self.left = None self.right = None # Inorder traversal def inorder(root): if root is not None: # Traverse left inorder(root.left) # Traverse root print(str(root.key) + "->", end=' ') # Traverse right inorder(root.right) # Insert a node def insert(node, key): # Return a new node if the tree is empty if node is None: return Node(key) # Traverse to the right place and insert the node if key < node.key: node.left = insert(node.left, key) else: node.right = insert(node.right, key) return node # Find the inorder successor def minValueNode(node): current = node # Find the leftmost leaf while(current.left is not None): current = current.left return current # Deleting a node def deleteNode(root, key): # Return if the tree is empty if root is None: return root # Find the node to be deleted if key root.key): root.right = deleteNode(root.right, key) else: # If the node is with only one child or no child if root.left is None: temp = root.right root = None return temp elif root.right is None: temp = root.left root = None return temp # If the node has two children, # place the inorder successor in position of the node to be deleted temp = minValueNode(root.right) root.key = temp.key # Delete the inorder successor root.right = deleteNode(root.right, temp.key) return root root = None root = insert(root, 8) root = insert(root, 3) root = insert(root, 1) root = insert(root, 6) root = insert(root, 7) root = insert(root, 10) root = insert(root, 14) root = insert(root, 4) print("Inorder traversal: ", end=' ') inorder(root) print("Delete 10") root = deleteNode(root, 10) print("Inorder traversal: ", end=' ') inorder(root)
// Binary Search Tree operations in Java class BinarySearchTree ( class Node ( int key; Node left, right; public Node(int item) ( key = item; left = right = null; ) ) Node root; BinarySearchTree() ( root = null; ) void insert(int key) ( root = insertKey(root, key); ) // Insert key in the tree Node insertKey(Node root, int key) ( // Return a new node if the tree is empty if (root == null) ( root = new Node(key); return root; ) // Traverse to the right place and insert the node if (key root.key) root.right = insertKey(root.right, key); return root; ) void inorder() ( inorderRec(root); ) // Inorder Traversal void inorderRec(Node root) ( if (root != null) ( inorderRec(root.left); System.out.print(root.key + " -> "); inorderRec(root.right); ) ) void deleteKey(int key) ( root = deleteRec(root, key); ) Node deleteRec(Node root, int key) ( // Return if the tree is empty if (root == null) return root; // Find the node to be deleted if (key root.key) root.right = deleteRec(root.right, key); else ( // If the node is with only one child or no child if (root.left == null) return root.right; else if (root.right == null) return root.left; // If the node has two children // Place the inorder successor in position of the node to be deleted root.key = minValue(root.right); // Delete the inorder successor root.right = deleteRec(root.right, root.key); ) return root; ) // Find the inorder successor int minValue(Node root) ( int minv = root.key; while (root.left != null) ( minv = root.left.key; root = root.left; ) return minv; ) // Driver Program to test above functions public static void main(String() args) ( BinarySearchTree tree = new BinarySearchTree(); tree.insert(8); tree.insert(3); tree.insert(1); tree.insert(6); tree.insert(7); tree.insert(10); tree.insert(14); tree.insert(4); System.out.print("Inorder traversal: "); tree.inorder(); System.out.println("After deleting 10"); tree.deleteKey(10); System.out.print("Inorder traversal: "); tree.inorder(); ) )
// Binary Search Tree operations in C #include #include struct node ( int key; struct node *left, *right; ); // Create a node struct node *newNode(int item) ( struct node *temp = (struct node *)malloc(sizeof(struct node)); temp->key = item; temp->left = temp->right = NULL; return temp; ) // Inorder Traversal void inorder(struct node *root) ( if (root != NULL) ( // Traverse left inorder(root->left); // Traverse root printf("%d -> ", root->key); // Traverse right inorder(root->right); ) ) // Insert a node struct node *insert(struct node *node, int key) ( // Return a new node if the tree is empty if (node == NULL) return newNode(key); // Traverse to the right place and insert the node if (key key) node->left = insert(node->left, key); else node->right = insert(node->right, key); return node; ) // Find the inorder successor struct node *minValueNode(struct node *node) ( struct node *current = node; // Find the leftmost leaf while (current && current->left != NULL) current = current->left; return current; ) // Deleting a node struct node *deleteNode(struct node *root, int key) ( // Return if the tree is empty if (root == NULL) return root; // Find the node to be deleted if (key key) root->left = deleteNode(root->left, key); else if (key> root->key) root->right = deleteNode(root->right, key); else ( // If the node is with only one child or no child if (root->left == NULL) ( struct node *temp = root->right; free(root); return temp; ) else if (root->right == NULL) ( struct node *temp = root->left; free(root); return temp; ) // If the node has two children struct node *temp = minValueNode(root->right); // Place the inorder successor in position of the node to be deleted root->key = temp->key; // Delete the inorder successor root->right = deleteNode(root->right, temp->key); ) return root; ) // Driver code int main() ( struct node *root = NULL; root = insert(root, 8); root = insert(root, 3); root = insert(root, 1); root = insert(root, 6); root = insert(root, 7); root = insert(root, 10); root = insert(root, 14); root = insert(root, 4); printf("Inorder traversal: "); inorder(root); printf("After deleting 10"); root = deleteNode(root, 10); printf("Inorder traversal: "); inorder(root); )
// Binary Search Tree operations in C++ #include using namespace std; struct node ( int key; struct node *left, *right; ); // Create a node struct node *newNode(int item) ( struct node *temp = (struct node *)malloc(sizeof(struct node)); temp->key = item; temp->left = temp->right = NULL; return temp; ) // Inorder Traversal void inorder(struct node *root) ( if (root != NULL) ( // Traverse left inorder(root->left); // Traverse root cout right); ) ) // Insert a node struct node *insert(struct node *node, int key) ( // Return a new node if the tree is empty if (node == NULL) return newNode(key); // Traverse to the right place and insert the node if (key key) node->left = insert(node->left, key); else node->right = insert(node->right, key); return node; ) // Find the inorder successor struct node *minValueNode(struct node *node) ( struct node *current = node; // Find the leftmost leaf while (current && current->left != NULL) current = current->left; return current; ) // Deleting a node struct node *deleteNode(struct node *root, int key) ( // Return if the tree is empty if (root == NULL) return root; // Find the node to be deleted if (key key) root->left = deleteNode(root->left, key); else if (key> root->key) root->right = deleteNode(root->right, key); else ( // If the node is with only one child or no child if (root->left == NULL) ( struct node *temp = root->right; free(root); return temp; ) else if (root->right == NULL) ( struct node *temp = root->left; free(root); return temp; ) // If the node has two children struct node *temp = minValueNode(root->right); // Place the inorder successor in position of the node to be deleted root->key = temp->key; // Delete the inorder successor root->right = deleteNode(root->right, temp->key); ) return root; ) // Driver code int main() ( struct node *root = NULL; root = insert(root, 8); root = insert(root, 3); root = insert(root, 1); root = insert(root, 6); root = insert(root, 7); root = insert(root, 10); root = insert(root, 14); root = insert(root, 4); cout << "Inorder traversal: "; inorder(root); cout << "After deleting 10"; root = deleteNode(root, 10); cout << "Inorder traversal: "; inorder(root); )
Complexidades binárias da árvore de pesquisa
Complexidade de tempo
| Operação | Melhor caso de complexidade | Complexidade média do caso | Pior Caso Complexidade |
| Pesquisa | O (log n) | O (log n) | Em) |
| Inserção | O (log n) | O (log n) | Em) |
| Eliminação | O (log n) | O (log n) | Em) |
Aqui, n é o número de nós na árvore.
Complexidade do Espaço
A complexidade do espaço para todas as operações é O (n).
Aplicativos de árvore de pesquisa binária
- Na indexação multinível no banco de dados
- Para classificação dinâmica
- Para gerenciar áreas de memória virtual no kernel Unix
