Árvore de pesquisa binária em Java

binary search tree java implementation code examples

Experimente Nosso Instrumento Para Eliminar Problemas

Selecione O Sistema Operacional Escolha Um Programa De Projeção (Opcionalmente)

Descreva Seu Problema

Este tutorial cobre a árvore de pesquisa binária em Java. Você aprenderá a criar um BST, inserir, remover e pesquisar um elemento, atravessar e implementar um BST em Java:

Uma árvore de pesquisa binária (doravante referida como BST) é um tipo de árvore binária. Ele também pode ser definido como uma árvore binária baseada em nós. O BST também é conhecido como 'Árvore binária ordenada'. No BST, todos os nós da subárvore esquerda têm valores menores que o valor do nó raiz.

Da mesma forma, todos os nós da subárvore direita do BST têm valores maiores que o valor do nó raiz. Essa ordenação de nós também deve ser verdadeira para as respectivas subárvores.

=> Visite aqui a série exclusiva de tutoriais de treinamento em Java.

O que você aprenderá:

Árvore de pesquisa binária em Java
Conclusão
- Leitura recomendada

Um BST não permite nós duplicados.

O diagrama abaixo mostra uma representação BST:

Acima é mostrado um exemplo de BST. Vemos que 20 é o nó raiz desta árvore. A subárvore esquerda possui todos os valores de nós menores que 20. A subárvore direita possui todos os nós maiores que 20. Podemos dizer que a árvore acima cumpre as propriedades BST.

A estrutura de dados do BST é considerada muito eficiente quando comparada aos Arrays e Lista vinculada no que diz respeito à inserção / exclusão e busca de itens.

O BST leva tempo O (log n) para pesquisar um elemento. Conforme os elementos são ordenados, metade da subárvore é descartada em todas as etapas durante a busca por um elemento. Isso se torna possível porque podemos determinar facilmente a localização aproximada do elemento a ser pesquisado.

Da mesma forma, as operações de inserção e exclusão são mais eficientes no BST. Quando queremos inserir um novo elemento, sabemos aproximadamente em qual subárvore (esquerda ou direita) iremos inserir o elemento.

Criação de uma árvore de pesquisa binária (BST)

Dada uma matriz de elementos, precisamos construir um BST.

Vamos fazer isso conforme mostrado abaixo:

Matriz fornecida: 45, 10, 7, 90, 12, 50, 13, 39, 57

Vamos primeiro considerar o elemento superior, ou seja, 45 como o nó raiz. A partir daqui, iremos criar o BST considerando as propriedades já discutidas.

Para criar uma árvore, compararemos cada elemento do array com a raiz. Em seguida, colocaremos o elemento em uma posição apropriada na árvore.

Todo o processo de criação do BST é mostrado abaixo.

BST concluído

Operações binárias da árvore de pesquisa

O BST oferece suporte a várias operações. A tabela a seguir mostra os métodos suportados pelo BST em Java. Discutiremos cada um desses métodos separadamente.

Método / operação	Descrição
Inserir	Adicione um elemento ao BST não violando as propriedades do BST.
Excluir	Remova um determinado nó do BST. O nó pode ser o nó raiz, não folha ou nó folha.
Procurar	Pesquise a localização do elemento fornecido no BST. Esta operação verifica se a árvore contém a chave especificada.

Insira um elemento no BST

Um elemento é sempre inserido como um nó folha no BST.

A seguir estão as etapas para inserir um elemento.

Comece pela raiz.
Compare o elemento a ser inserido com o nó raiz. Se for menor que a raiz, atravesse a subárvore esquerda ou atravesse a subárvore direita.
Percorra a subárvore até o final da subárvore desejada. Insira o nó na subárvore apropriada como um nó folha.

Vejamos uma ilustração da operação de inserção do BST.

Considere o seguinte BST e vamos inserir o elemento 2 na árvore.

figura 1

Figura 2

A operação de inserção para BST é mostrada acima. Na fig (1), mostramos o caminho que percorremos para inserir o elemento 2 no BST. Também mostramos as condições que são verificadas em cada nó. Como resultado da comparação recursiva, o elemento 2 é inserido como o filho direito de 1, conforme mostrado na fig (2).

Operação de pesquisa no BST

Para pesquisar se um elemento está presente no BST, começamos novamente da raiz e, em seguida, percorremos a subárvore esquerda ou direita, dependendo se o elemento a ser pesquisado é menor ou maior que a raiz.

Listados abaixo estão os passos que devemos seguir.

Compare o elemento a ser pesquisado com o nó raiz.
Se a chave (elemento a ser pesquisado) = raiz, retorna o nó raiz.
Else if key
Caso contrário, atravesse a subárvore direita.
Compare repetidamente os elementos da subárvore até que a chave seja encontrada ou o final da árvore seja alcançado.

Vamos ilustrar a operação de pesquisa com um exemplo. Considere que temos que pesquisar a chave = 12.

Na figura abaixo, traçaremos o caminho que seguimos para buscar esse elemento.

Conforme mostrado na figura acima, primeiro comparamos a chave com a raiz. Como a chave é maior, percorremos a subárvore direita. Na subárvore direita, comparamos novamente a chave com o primeiro nó na subárvore direita.

Descobrimos que a chave é menor que 15. Portanto, vamos para a subárvore esquerda do nó 15. O nó imediato à esquerda de 15 é 12 que corresponde à chave. Nesse ponto, paramos a pesquisa e retornamos o resultado.

Remova o elemento do BST

Quando excluímos um nó do BST, existem três possibilidades, conforme discutido abaixo:

Nó é um Nó Folha

Se um nó a ser excluído for um nó folha, podemos excluir diretamente esse nó, pois ele não possui nenhum nó filho. Isso é mostrado na imagem abaixo.

Conforme mostrado acima, o nó 12 é um nó folha e pode ser excluído imediatamente.

Nó tem apenas um filho

Quando precisamos excluir o nó que tem um filho, copiamos o valor do filho no nó e, em seguida, excluímos o filho.

No diagrama acima, queremos excluir o nó 90 que tem um filho 50. Assim, trocamos o valor 50 por 90 e, em seguida, excluímos o nó 90 que agora é um nó filho.

Node Tem Dois Filhos

Quando um nó a ser excluído tem dois filhos, então substituímos o nó pelo sucessor inordenado (raiz esquerda-direita) do nó ou simplesmente dizemos o nó mínimo na subárvore direita se a subárvore direita do nó não estiver vazia. Substituímos o nó por este nó mínimo e excluímos o nó.

No diagrama acima, queremos excluir o nó 45, que é o nó raiz do BST. Descobrimos que a subárvore direita desse nó não está vazia. Em seguida, percorremos a subárvore certa e descobrimos que o nó 50 é o nó mínimo aqui. Portanto, substituímos esse valor no lugar de 45 e, em seguida, excluímos 45.

Se verificarmos a árvore, vemos que ela cumpre as propriedades de um BST. Portanto, a substituição do nó foi correta.

Implementação da árvore de pesquisa binária (BST) em Java

O programa a seguir em Java fornece uma demonstração de todas as operações BST acima usando a mesma árvore usada na ilustração como exemplo.

adicionando um valor a um array

class BST_class { //node class that defines BST node class Node { int key; Node left, right; public Node(int data){ key = data; left = right = null; } } // BST root node Node root; // Constructor for BST =>initial empty tree BST_class(){ root = null; } //delete a node from BST void deleteKey(int key) { root = delete_Recursive(root, key); } //recursive delete function Node delete_Recursive(Node root, int key) { //tree is empty if (root == null) return root; //traverse the tree if (key root.key) //traverse right subtree root.right = delete_Recursive(root.right, key); else { // node contains only one child if (root.left == null) return root.right; else if (root.right == null) return root.left; // node has two children; //get inorder successor (min value in the right subtree) root.key = minValue(root.right); // Delete the inorder successor root.right = delete_Recursive(root.right, root.key); } return root; } int minValue(Node root) { //initially minval = root int minval = root.key; //find minval while (root.left != null) { minval = root.left.key; root = root.left; } return minval; } // insert a node in BST void insert(int key) { root = insert_Recursive(root, key); } //recursive insert function Node insert_Recursive(Node root, int key) { //tree is empty if (root == null) { root = new Node(key); return root; } //traverse the tree if (key root.key) //insert in the right subtree root.right = insert_Recursive(root.right, key); // return pointer return root; } // method for inorder traversal of BST void inorder() { inorder_Recursive(root); } // recursively traverse the BST void inorder_Recursive(Node root) { if (root != null) { inorder_Recursive(root.left); System.out.print(root.key + ' '); inorder_Recursive(root.right); } } boolean search(int key) { root = search_Recursive(root, key); if (root!= null) return true; else return false; } //recursive insert function Node search_Recursive(Node root, int key) // Base Cases: root is null or key is present at root if (root==null } class Main{ public static void main(String() args) { //create a BST object BST_class bst = new BST_class(); /* BST tree example 45 /  10 90 /  / 7 12 50 */ //insert data into BST bst.insert(45); bst.insert(10); bst.insert(7); bst.insert(12); bst.insert(90); bst.insert(50); //print the BST System.out.println('The BST Created with input data(Left-root-right):'); bst.inorder(); //delete leaf node System.out.println('
The BST after Delete 12(leaf node):'); bst.deleteKey(12); bst.inorder(); //delete the node with one child System.out.println('
The BST after Delete 90 (node with 1 child):'); bst.deleteKey(90); bst.inorder(); //delete node with two children System.out.println('
The BST after Delete 45 (Node with two children):'); bst.deleteKey(45); bst.inorder(); //search a key in the BST boolean ret_val = bst.search (50); System.out.println('
Key 50 found in BST:' + ret_val ); ret_val = bst.search (12); System.out.println('
Key 12 found in BST:' + ret_val ); } }

Resultado:

Binary Search Tree (BST) Traversal em Java

Uma árvore é uma estrutura hierárquica, portanto, não podemos percorrê-la linearmente como outras estruturas de dados, como arrays. Qualquer tipo de árvore precisa ser percorrido de maneira especial para que todas as suas subárvores e nós sejam visitados pelo menos uma vez.

Dependendo da ordem em que o nó raiz, a subárvore esquerda e a subárvore direita são percorridos em uma árvore, há certos percursos, conforme mostrado abaixo:

Inorder Traversal
Pré-encomenda Traversal
PostOrder Traversal

Todos os percursos acima usam a técnica de profundidade, ou seja, a árvore é percorrida em profundidade.

As árvores também usam a técnica de largura primeiro para travessia. A abordagem usando esta técnica é chamada “Ordem de Nível” Travessia.

Nesta seção, demonstraremos cada uma das travessias usando o BST a seguir como exemplo.

Com o BST conforme mostrado no diagrama acima, a passagem de ordem de nível para a árvore acima é:

Nível de ordem transversal: 10 6 12 4 8

Inorder Traversal

A abordagem de travessia em ordem atravessou o BST na ordem, Subárvore esquerda => RootNode => Subárvore direita . O percurso em ordem fornece uma sequência decrescente de nós de um BST.

O algoritmo InOrder (bstTree) para InOrder Traversal é fornecido abaixo.

Percorra a subárvore esquerda usando InOrder (left_subtree)
Visite o nó raiz.
Percorra a subárvore direita usando InOrder (right_subtree)

A travessia em ordem da árvore acima é:

4 6 8 10 12

Como visto, a sequência dos nós como resultado do percurso em ordem está em ordem decrescente.

Pré-encomenda Traversal

No percurso da pré-ordem, a raiz é visitada primeiro, seguida pela subárvore esquerda e pela subárvore direita. A passagem de pré-encomenda cria uma cópia da árvore. Também pode ser usado em árvores de expressão para obter a expressão de prefixo.

O algoritmo de passagem PreOrder (bst_tree) é fornecido abaixo:

Visite o nó raiz
Percorra a subárvore esquerda com PreOrder (left_subtree).
Percorra a subárvore direita com PreOrder (right_subtree).

A passagem de pré-encomenda para o BST fornecida acima é:

10 6 4 8 12

PostOrder Traversal

O percurso postOrder atravessa o BST na ordem: Subárvore esquerda-> Subárvore direita-> Nó raiz . A passagem PostOrder é usada para excluir a árvore ou obter a expressão pós-fixada no caso de árvores de expressão.

O algoritmo de travessia postOrder (bst_tree) é o seguinte:

Percorra a subárvore esquerda com postOrder (left_subtree).
Percorra a subárvore direita com postOrder (right_subtree).
Visite o nó raiz

A travessia postOrder para o exemplo acima BST é:

4 8 6 12 10

A seguir, implementaremos essas travessias usando a técnica de profundidade em uma implementação Java.

//define node of the BST class Node { int key; Node left, right; public Node(int data){ key = data; left = right = null; } } //BST class class BST_class { // BST root node Node root; BST_class(){ root = null; } //PostOrder Traversal - Left:Right:rootNode (LRn) void postOrder(Node node) { if (node == null) return; // first traverse left subtree recursively postOrder(node.left); // then traverse right subtree recursively postOrder(node.right); // now process root node System.out.print(node.key + ' '); } // InOrder Traversal - Left:rootNode:Right (LnR) void inOrder(Node node) { if (node == null) return; //first traverse left subtree recursively inOrder(node.left); //then go for root node System.out.print(node.key + ' '); //next traverse right subtree recursively inOrder(node.right); } //PreOrder Traversal - rootNode:Left:Right (nLR) void preOrder(Node node) { if (node == null) return; //first print root node first System.out.print(node.key + ' '); // then traverse left subtree recursively preOrder(node.left); // next traverse right subtree recursively preOrder(node.right); } // Wrappers for recursive functions void postOrder_traversal() { postOrder(root); } void inOrder_traversal() { inOrder(root); } void preOrder_traversal() { preOrder(root); } } class Main{ public static void main(String() args) { //construct a BST BST_class tree = new BST_class(); /* 45 // \ 10 90 // \ 7 12 */ tree.root = new Node(45); tree.root.left = new Node(10); tree.root.right = new Node(90); tree.root.left.left = new Node(7); tree.root.left.right = new Node(12); //PreOrder Traversal System.out.println('BST => PreOrder Traversal:'); tree.preOrder_traversal(); //InOrder Traversal System.out.println('
BST => InOrder Traversal:'); tree.inOrder_traversal(); //PostOrder Traversal System.out.println('
BST => PostOrder Traversal:'); tree.postOrder_traversal(); } }

Resultado:

perguntas frequentes

P # 1) Por que precisamos de uma árvore de pesquisa binária?

Responda : A maneira como procuramos elementos na estrutura de dados linear, como matrizes, usando a técnica de pesquisa binária, sendo a árvore uma estrutura hierárquica, precisamos de uma estrutura que possa ser usada para localizar elementos em uma árvore.

É aqui que surge a árvore de pesquisa binária que nos ajuda na busca eficiente de elementos na imagem.

P # 2) Quais são as propriedades de uma árvore de pesquisa binária?

Responda : Uma árvore de pesquisa binária que pertence à categoria de árvore binária tem as seguintes propriedades:

Os dados armazenados em uma árvore de pesquisa binária são exclusivos. Não permite valores duplicados.
Os nós da subárvore esquerda são menores que o nó raiz.
Os nós da subárvore direita são maiores que o nó raiz.

P # 3) Quais são as aplicações de uma árvore de busca binária?

Responda : Podemos usar árvores de busca binárias para resolver algumas funções contínuas em matemática. A pesquisa de dados em estruturas hierárquicas torna-se mais eficiente com árvores de pesquisa binárias. A cada etapa, reduzimos a pesquisa pela metade da subárvore.

P # 4) Qual é a diferença entre uma árvore binária e uma árvore binária de pesquisa?

Responda: Uma árvore binária é uma estrutura de árvore hierárquica em que cada nó conhecido como pai pode ter no máximo dois filhos. Uma árvore de pesquisa binária cumpre todas as propriedades da árvore binária e também tem suas propriedades exclusivas.

Em uma árvore de pesquisa binária, as subárvores esquerdas contêm nós que são menores ou iguais ao nó raiz e a subárvore direita possui nós que são maiores que o nó raiz.

P # 5) A árvore de busca binária é única?

Responda : Uma árvore de pesquisa binária pertence a uma categoria de árvore binária. É único no sentido de que não permite valores duplicados e também todos os seus elementos são ordenados de acordo com uma ordem específica.

Conclusão

As árvores de pesquisa binária fazem parte da categoria da árvore binária e são usadas principalmente para pesquisar dados hierárquicos. Ele também é usado para resolver alguns problemas matemáticos.

Neste tutorial, vimos a implementação de uma árvore de pesquisa binária. Também vimos várias operações realizadas no BST com sua ilustração e também exploramos os percursos para o BST.

=> Veja a série de treinamento simples em Java aqui.

Árvore de pesquisa binária em Java - exemplos de implementação e código