Binary Tree e BST Explained

Árvore binária e BST explicada

Na computação, a árvore binária (ou binary tree, em inglês) é uma estrutura de dados hierárquica composta por nós, onde cada nó tem no máximo dois filhos: um filho à esquerda e um filho à direita. Esta estrutura é amplamente utilizada em várias áreas da ciência da computação, como organização de dados, algoritmos de busca, compressão de dados, entre outros.

Estrutura da Árvore Binária

Componentes da Árvore Binária

• Nó (Node): Cada elemento da árvore é chamado de nó. Ele contém um valor ou dado e referências (ponteiros) para seus filhos.
• Raiz (Root): O nó superior da árvore. É o ponto de entrada e não tem pai.
• Filhos (Children): Nós que descendem de um outro nó. Cada nó pode ter até dois filhos.
• Folhas (Leaves): Nós que não têm filhos.
• Subárvore (Subtree): Qualquer nó com todos os seus descendentes forma uma subárvore.

Tipos de Árvores Binárias

1. Árvore Binária Completa: Todos os níveis, exceto possivelmente o último, estão completamente preenchidos, e todos os nós estão o mais à esquerda possível.
2. Árvore Binária Perfeita: Todos os nós internos têm exatamente dois filhos, e todas as folhas estão no mesmo nível.
3. Árvore Binária Balanceada: A altura das subárvores esquerda e direita de qualquer nó diferem em no máximo uma unidade.
4. Árvore Binária de Busca (BST - Binary Search Tree): Para cada nó, todos os valores na subárvore à esquerda são menores, e todos os valores na subárvore à direita são maiores.

Funcionamento de uma Árvore Binária de Busca (BST)

Uma BST é uma árvore binária que mantém uma propriedade específica: para cada nó, todos os valores na subárvore à esquerda são menores e todos os valores na subárvore à direita são maiores.

Operações em BST

1. Inserção: Para inserir um novo valor, começa-se na raiz e compara-se o valor a ser inserido com o valor do nó atual. Se for menor, move-se para a subárvore à esquerda, se for maior, move-se para a subárvore à direita. Este processo continua até encontrar um nó folha onde o novo valor pode ser inserido.
2. Busca: Similar à inserção, começa-se na raiz e compara-se o valor buscado com o valor do nó atual, movendo-se para a esquerda ou direita conforme necessário até encontrar o valor ou concluir que ele não está na árvore.
3. Remoção: A remoção é mais complexa e varia dependendo do número de filhos do nó a ser removido (nenhum, um ou dois). O caso mais complicado é quando o nó tem dois filhos, onde se geralmente encontra-se o sucessor (o menor valor na subárvore à direita) para substituir o nó removido.

Desenho de uma BST

Aqui está um exemplo de uma BST:

        8
       / \
      3   10
     / \    \
    1   6    14
       / \   /
      4   7 13

Neste exemplo:

• A raiz é 8.
• O nó 3 é o filho esquerdo da raiz e 10 é o filho direito.
• O nó 1 é o filho esquerdo de 3, e 6 é o filho direito.
• O nó 4 é o filho esquerdo de 6 e 7 é o filho direito.
• O nó 14 é o filho direito de 10 e 13 é o filho esquerdo de 14.

Implementação em Python

Aqui está um exemplo básico de implementação de uma BST em Python:

class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key

class BST:
    def __init__(self):
        self.root = None

    def insert(self, key):
        if self.root is None:
            self.root = Node(key)
        else:
            self._insert(self.root, key)

    def _insert(self, root, key):
        if key < root.val:
            if root.left is None:
                root.left = Node(key)
            else:
                self._insert(root.left, key)
        else:
            if root.right is None:
                root.right = Node(key)
            else:
                self._insert(root.right, key)

    def search(self, key):
        return self._search(self.root, key)

    def _search(self, root, key):
        if root is None or root.val == key:
            return root
        if key < root.val:
            return self._search(root.left, key)
        else:
            return self._search(root.right, key)

# Exemplo de uso
bst = BST()
bst.insert(8)
bst.insert(3)
bst.insert(10)
bst.insert(1)
bst.insert(6)
bst.insert(4)
bst.insert(7)
bst.insert(14)
bst.insert(13)

# Busca
node = bst.search(6)
if node:
    print("Valor encontrado:", node.val)
else:
    print("Valor não encontrado.")

Neste exemplo, criamos uma classe Node para representar cada nó e uma classe BST para representar a árvore binária de busca. A árvore permite inserção e busca de valores, seguindo as regras mencionadas.

Árvore de Síntese Abstrata (AST) e Árvore de Análise (Parse Tree)

Em compiladores e linguagens de programação, as árvores de síntese abstrata (AST) e as árvores de análise (Parse Tree) são estruturas de dados essenciais usadas para representar a estrutura de programas de computador.

Árvore de Análise (Parse Tree)

A árvore de análise, também conhecida como árvore de derivação ou árvore de análise sintática, é uma representação detalhada de uma expressão conforme definida por uma gramática formal. Ela mostra como a entrada é derivada a partir das regras da gramática.

Características da Árvore de Análise

• Nodos Internos: Representam produções da gramática.
• Folhas: Representam tokens ou terminais da entrada.
• Representação Completa: Captura todos os detalhes da gramática utilizada para derivar a entrada.

Exemplo de Árvore de Análise

Considere a gramática simples para expressões aritméticas:

E -> E + T | T
T -> T * F | F
F -> ( E ) | id

E a expressão de entrada: id + id * id

A árvore de análise para esta expressão seria:

        E
       / \
      E   +
     / \   \
    T   id  T
   / \      / \
  F   *    F   id
 / \      / \
id id    id id

Árvore de Síntese Abstrata (AST)
A árvore de síntese abstrata (AST) é uma representação simplificada da árvore de análise. Ela elimina muitos dos detalhes sintáticos da árvore de análise, focando na estrutura hierárquica e na essência semântica do código.
Características da AST
Nodos Internos: Representam operações ou construtos significativos da linguagem.
Folhas: Representam operandos ou identificadores.
Simplificação: Elimina símbolos intermediários e focos sintáticos desnecessários.
Exemplo de AST
Para a mesma expressão id + id * id, a AST seria:
      +
     / \
   id   *
        / \
      id  id
Comparação: Parse Tree vs AST
Detalhamento: A árvore de análise detalha cada passo de acordo com a gramática, enquanto a AST abstrai para capturar apenas a estrutura semântica.
Complexidade: A árvore de análise é mais complexa devido à inclusão de todos os símbolos da gramática, enquanto a AST é mais compacta e fácil de manipular.

Implementação Básica em Java
Exemplo de Classes para Parse Tree e AST
Aqui está um exemplo simplificado de como representar e construir uma árvore de análise e uma AST em Java:
// Nodo básico para árvores
class Node {
    String value;
    List<Node> children;

    Node(String value) {
        this.value = value;
        this.children = new ArrayList<>();
    }

    void addChild(Node child) {
        children.add(child);
    }
}

// Construção de uma Parse Tree
Node parseTreeExample() {
    Node root = new Node("E");
    Node e1 = new Node("E");
    Node plus = new Node("+");
    Node t1 = new Node("T");
    Node t2 = new Node("T");
    Node id1 = new Node("id");
    Node id2 = new Node("id");
    Node id3 = new Node("id");
    Node star = new Node("*");

    root.addChild(e1);
    root.addChild(plus);
    root.addChild(t2);
    e1.addChild(t1);
    t1.addChild(id1);
    t2.addChild(t1);
    t2.addChild(star);
    t2.addChild(id3);

    return root;
}

// Construção de uma AST
Node astExample() {
    Node root = new Node("+");
    Node id1 = new Node("id");
    Node star = new Node("*");
    Node id2 = new Node("id");
    Node id3 = new Node("id");

    root.addChild(id1);
    root.addChild(star);
    star.addChild(id2);
    star.addChild(id3);

    return root;
}
Visualização das Estruturas
Parse Tree
        E
       / \
      E   +
     / \   \
    T   id  T
   / \      / \
  F   *    F   id
 / \      / \
id id    id id
AST
      +
     / \
   id   *
        / \
      id  id
Aplicações de AST e Parse Tree
Parse Tree: Usada principalmente para análise sintática durante a fase de parsing em compiladores.
AST: Usada para análise semântica, otimização de código, e geração de código durante a compilação.
As árvores de análise e síntese abstrata são fundamentais para a construção de compiladores e interpretes, permitindo a representação estruturada e manipulável de programas de computador.

Árvore de Análise (Parse Tree) em C
A árvore de análise, ou árvore sintática, é uma representação detalhada de uma expressão conforme definida por uma gramática formal.
Exemplo de Gramática
Vamos considerar uma gramática simples para expressões aritméticas:
E -> E + T | T
T -> T * F | F
F -> ( E ) | id
E a expressão de entrada: id + id * id
Estrutura da Parse Tree
A estrutura da árvore de análise para essa expressão seria:
        E
       / \
      E   +
     / \   \
    T   id  T
   / \      / \
  F   *    F   id
 / \      / \
id id    id id
Implementação em C
Vamos implementar a construção de uma Parse Tree em C. Primeiro, definimos a estrutura do nodo e depois construímos a árvore para a expressão id + id * id.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Estrutura de um nodo na árvore de análise
typedef struct Node {
    char *value;
    struct Node **children;
    int child_count;
} Node;

// Função para criar um novo nodo
Node* createNode(char *value, int child_count) {
    Node *node = (Node *)malloc(sizeof(Node));
    node->value = strdup(value);
    node->child_count = child_count;
    if (child_count > 0) {
        node->children = (Node **)malloc(sizeof(Node *) * child_count);
    } else {
        node->children = NULL;
    }
    return node;
}

// Função para imprimir a árvore (recursiva)
void printTree(Node *root, int level) {
    if (root == NULL) return;
    for (int i = 0; i < level; i++) printf("  ");
    printf("%s\n", root->value);
    for (int i = 0; i < root->child_count; i++) {
        printTree(root->children[i], level + 1);
    }
}

// Função principal para construir a árvore de análise da expressão "id + id * id"
Node* buildParseTree() {
    Node *root = createNode("E", 3);
    
    Node *e1 = createNode("E", 1);
    Node *plus = createNode("+", 0);
    Node *t2 = createNode("T", 3);

    Node *t1 = createNode("T", 1);
    Node *id1 = createNode("id", 0);
    Node *id2 = createNode("id", 0);
    Node *id3 = createNode("id", 0);
    Node *star = createNode("*", 0);

    root->children[0] = e1;
    root->children[1] = plus;
    root->children[2] = t2;
    
    e1->children[0] = t1;
    t1->children[0] = id1;
    
    t2->children[0] = t1;
    t2->children[1] = star;
    t2->children[2] = id3;

    return root;
}

int main() {
    Node *parseTree = buildParseTree();
    printTree(parseTree, 0);
    return 0;
}

Árvore de Síntese Abstrata (AST) em C
A árvore de síntese abstrata (AST) é uma representação simplificada da árvore de análise que captura a estrutura hierárquica e a essência semântica do código.
Estrutura da AST
Para a expressão id + id * id, a AST seria:
      +
     / \
   id   *
        / \
      id  id
Implementação em C
Vamos implementar a construção de uma AST para a mesma expressão id + id * id.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Estrutura de um nodo na AST
typedef struct Node {
    char *value;
    struct Node *left;
    struct Node *right;
} Node;

// Função para criar um novo nodo
Node* createASTNode(char *value, Node *left, Node *right) {
    Node *node = (Node *)malloc(sizeof(Node));
    node->value = strdup(value);
    node->left = left;
    node->right = right;
    return node;
}

// Função para imprimir a árvore (recursiva)
void printAST(Node *root, int level) {
    if (root == NULL) return;
    for (int i = 0; i < level; i++) printf("  ");
    printf("%s\n", root->value);
    printAST(root->left, level + 1);
    printAST(root->right, level + 1);
}

// Função principal para construir a AST da expressão "id + id * id"
Node* buildAST() {
    Node *id1 = createASTNode("id", NULL, NULL);
    Node *id2 = createASTNode("id", NULL, NULL);
    Node *id3 = createASTNode("id", NULL, NULL);
    
    Node *star = createASTNode("*", id2, id3);
    Node *plus = createASTNode("+", id1, star);

    return plus;
}

int main() {
    Node *ast = buildAST();
    printAST(ast, 0);
    return 0;
}
Comparação: Parse Tree vs AST
Parse Tree: Captura todos os detalhes da gramática utilizada para derivar a entrada. É mais detalhada e complexa.
AST: Simplifica a estrutura, removendo símbolos intermediários e focando na essência semântica da expressão. É mais compacta e fácil de manipular.
Conclusão
As árvores de análise e síntese abstrata são fundamentais na construção de compiladores e intérpretes. A árvore de análise fornece uma representação detalhada da estrutura gramatical, enquanto a AST fornece uma representação simplificada e semântica do código. Em C, essas estruturas podem ser implementadas utilizando estruturas de dados adequadas e funções recursivas para construção e manipulação.