Implementando uma Árvore de Busca Binária

Introdução

Neste laboratório, aprenderemos como implementar uma Árvore de Busca Binária (Binary Search Tree) em Java. Uma Árvore de Busca Binária é uma estrutura de dados de árvore binária na qual o valor de cada nó é maior ou igual aos valores em sua subárvore esquerda e menor ou igual aos valores em sua subárvore direita.

Criando a Classe BSTNode

Primeiramente, vamos criar uma classe Java que representa o nó de uma árvore de busca binária e chamá-la de BSTNode. Um nó em uma árvore de busca binária deve ter um valor e dois nós filhos - um à sua esquerda e outro à sua direita.

class BSTNode {
    int value;
    BSTNode leftChild;
    BSTNode rightChild;

    BSTNode(int val) {
        this.value = val;
        this.leftChild = null;
        this.rightChild = null;
    }
}

Inserindo Elementos na Árvore de Busca Binária

Para inserir elementos na árvore de busca binária, seguimos o seguinte algoritmo:

• Se o novo valor for menor que o valor do nó atual, então recursivamente vá para o filho esquerdo.
• Se o novo valor for maior que o valor do nó atual, então recursivamente vá para o seu filho direito.
• Se o nó atual for nulo, então adicione o novo valor nesta posição.

public static BSTNode insert(int value, BSTNode current) {
    if (current == null) {
        BSTNode newNode = new BSTNode(value);
        return newNode;
    } else {
        if (value < current.value)
            current.leftChild = insert(value, current.leftChild);
        else
            current.rightChild = insert(value, current.rightChild);
    }
    return current;
}

Para testar este método, crie a árvore de busca binária e insira alguns elementos:

public static void main(String[] args) {
    BSTNode root = new BSTNode(12);
    root = insert(7, root);
    root = insert(20, root);
    root = insert(5, root);
    root = insert(9, root);
    root = insert(21, root);

    // Print out the tree to verify the insertion
    System.out.println("Traversal after insertion: ");
    inorderTraversal(root);
}

// Function to traverse the tree inorder
public static void inorderTraversal(BSTNode current) {
    if (current == null)
        return;
    inorderTraversal(current.leftChild);
    System.out.print(current.value + " ");
    inorderTraversal(current.rightChild);
}

Saída:

Traversal after insertion:
5 7 9 12 20 21

Buscando um Elemento na Árvore de Busca Binária

Para buscar um elemento na árvore de busca binária, seguimos o seguinte algoritmo:

• Se o valor do nó atual corresponder ao valor que estamos tentando encontrar, então retorne verdadeiro (true).
• Se o valor do nó atual for maior que o valor que estamos tentando encontrar, então recursivamente vá para o filho esquerdo.
• Se o valor do nó atual for menor que o valor que estamos tentando encontrar, então recursivamente vá para o filho direito.
• Se o nó atual for nulo, então retorne falso (false).

public static boolean search(int key, BSTNode current) {
    if (current == null)
        return false;
    if (current.value == key)
        return true;
    else {
        if (key < current.value)
            return search(key, current.leftChild);
        else
            return search(key, current.rightChild);
    }
}

Para testar este método, busque por alguns elementos:

public static void main(String[] args) {
    BSTNode root = new BSTNode(12);
    root = insert(7, root);
    root = insert(20, root);
    root = insert(5, root);
    root = insert(9, root);
    root = insert(21, root);

    // Search for elements
    System.out.println(search(7, root));
    System.out.println(search(9, root));
    System.out.println(search(17, root));
}

Saída:

true
true
false

Removendo um Elemento de uma Árvore de Busca Binária

Excluir um elemento de uma árvore de busca binária é um pouco mais complexo do que os passos anteriores, pois precisamos lidar com diferentes casos dependendo do tipo de nó:

• Se o nó não tiver filhos (um nó folha), simplesmente remova-o.
• Se o nó tiver apenas um filho, substitua-o por seu único filho.
• Se o nó tiver dois filhos, substitua-o pelo valor mínimo da subárvore direita ou pelo valor máximo da subárvore esquerda.

public static BSTNode delete(int value, BSTNode current) {
    if (current == null)
        return current;
    if (value < current.value)
        current.leftChild = delete(value, current.leftChild);
    else if (value > current.value)
        current.rightChild = delete(value, current.rightChild);
    else if (value == current.value) {
        if (current.leftChild != null && current.rightChild != null) {
            int min = current.rightChild.value;
            BSTNode temp = current.rightChild;
            while (temp.leftChild != null) {
                min = temp.leftChild.value;
                temp = temp.leftChild;
            }
            current.value = min;
            current.rightChild = delete(min, current.rightChild);
        } else if (current.leftChild == null)
            return current.rightChild;
        else if (current.rightChild == null)
            return current.leftChild;
    }
    return current;
}

Para testar este método, exclua alguns nós e imprima a árvore:

public static void main(String[] args) {
    BSTNode root = new BSTNode(12);
    root = insert(7, root);
    root = insert(20, root);
    root = insert(5, root);
    root = insert(9, root);
    root = insert(21, root);

    // Delete some nodes
    root = delete(12, root);
    root = delete(20, root);
    root = delete(9, root);

    // Print the tree to verify the deletion
    System.out.println("Traversal after deletion: ");
    inorderTraversal(root);
}

Saída:

Traversal after deletion:
5 7 21

Percorrendo a Árvore de Busca Binária

Podemos percorrer uma árvore de busca binária de diferentes maneiras:

• Inorder Traversal (Esquerda-Raiz-Direita)
• Preorder Traversal (Raiz-Esquerda-Direita)
• Postorder Traversal (Esquerda-Direita-Raiz)
• Level-order Traversal (BFS)

public static void inorderTraversal(BSTNode current) {
    if (current == null)
        return;
    inorderTraversal(current.leftChild);
    System.out.print(current.value + " ");
    inorderTraversal(current.rightChild);
}

public static void preorderTraversal(BSTNode current) {
    if (current == null)
        return;
    System.out.print(current.value + " ");
    preorderTraversal(current.leftChild);
    preorderTraversal(current.rightChild);
}

public static void postorderTraversal(BSTNode current) {
    if (current == null)
        return;
    postorderTraversal(current.leftChild);
    postorderTraversal(current.rightChild);
    System.out.print(current.value + " ");
}

public static void levelOrderTraversal(BSTNode root) {
    Queue<BSTNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        BSTNode temp = queue.poll();
        System.out.print(temp.value + " ");
        if (temp.leftChild != null)
            queue.add(temp.leftChild);
        if (temp.rightChild != null)
            queue.add(temp.rightChild);
    }
}

Para testar esses métodos, imprima a árvore usando cada técnica de travessia:

public static void main(String[] args) {
    BSTNode root = new BSTNode(12);
    root = insert(7, root);
    root = insert(20, root);
    root = insert(5, root);
    root = insert(9, root);
    root = insert(21, root);

    System.out.print("Inorder Traversal: ");
    inorderTraversal(root);
    System.out.print("\nPreorder Traversal: ");
    preorderTraversal(root);
    System.out.print("\nPostorder Traversal: ");
    postorderTraversal(root);
    System.out.print("\nLevel-order Traversal: ");
    levelOrderTraversal(root);
}

Saída:

Inorder Traversal: 5 7 9 12 20 21
Preorder Traversal: 12 7 5 9 20 21
Postorder Traversal: 5 9 7 21 20 12
Level-order Traversal: 12 7 20 5 9 21

Resumo

Neste laboratório, aprendemos como criar, inserir elementos, pesquisar um elemento, excluir um elemento e percorrer uma Árvore de Busca Binária em Java.

Primeiramente, criamos a classe BSTNode, que representa um nó na árvore de busca binária. Em seguida, implementamos as funcionalidades de inserção, pesquisa e exclusão usando algoritmos específicos para árvores de busca binária. Finalmente, aprendemos como percorrer a árvore de busca binária usando diferentes técnicas de travessia, como inorder, preorder, postorder e level-order traversal.

Com esses conceitos, você deve ser capaz de implementar árvores de busca binária em seus próprios programas Java.