1. Busca Sequencial A busca sequencial envolve percorrer todos os elementos de uma estrutura de dados (como um array ou lista) um por um, comparando cada elemento com o valor desejado até encontrar uma correspondência. Vantagens:

• Não requer que os dados estejam ordenados
• Pode ser implementada tanto em arrays quanto em listas ligadas
• Simplicidade de implementação Desvantagens:
• Ineficiente para grandes conjuntos de dados
• Tempo de execução aumenta linearmente com o tamanho da entrada Complexidade de tempo:
• Caso melhor (elemento é o primeiro): O(1)
• Caso médio: O(n/2)
• Caso pior (elemento é o último ou não existe): O(n) Inserir N elementos distintos em uma tabela vazia requer N2 comparações.

2. Busca Binária em Arrays Ordenados A busca binária é um algoritmo eficiente para encontrar elementos em arrays ordenados. Em cada passo, o algoritmo compara o elemento do meio com o valor procurado e descarta metade do array de busca. Implementação Iterativa:

public int buscaBinaria(Chave chave, Chave[] chaves) {
    int inicio = 0;
    int fim = chaves.length - 1;
    
    while (inicio <= fim) {
        int meio = inicio + (fim - inicio) / 2;
        int comparacao = chave.compareTo(chaves[meio]);
        
        if (comparacao < 0) {
            fim = meio - 1;
        } else if (comparacao > 0) {
            inicio = meio + 1;
        } else {
            return meio; // Elemento encontrado
        }
    }
    return inicio; // Elemento não encontrado
}

Implementação Recursiva:

public int buscaBinariaRecursiva(Chave chave, Chave[] chaves, int inicio, int fim) {
    if (fim < inicio) {
        return inicio;
    }
    
    int meio = inicio + (fim - inicio) / 2;
    int comparacao = chave.compareTo(chaves[meio]);
    
    if (comparacao < 0) {
        return buscaBinariaRecursiva(chave, chaves, inicio, meio - 1);
    } else if (comparacao > 0) {
        return buscaBinariaRecursiva(chave, chaves, meio + 1, fim);
    } else {
        return meio; // Elemento encontrado
    }
}

A busca binária é significativamente mais rápida que a busca sequencial para tabelas estáticas (sem inserções frequentes). No entanto, para tabelas dinâmicas com muitas inserções, a complexidade de inserção permanece O(n), tornando-a inadequada. A solução para garantir operações de busca e inserção eficientes (ambas em tempo logarítmico) é estruturas de dados mais complexas, como as árvores de busca binária.

3. Árvores de Busca Binária Uma árvore de busca binária é uma estrutura de dados em árvore onde cada nó contém uma chave e um valor associado. Para qualquer nó, todas as chaves na subárvore esquerda são menores que a chave do nó, e todas as chaves na subárvore direita são maiores. Implementação:

public class ArvoreBuscaBinaria<Chave extends Comparable<Chave>, Valor> {
    
    // Classe interna para representar um nó da árvore
    private class No {
        private Chave chave;
        private Valor valor;
        private No esquerdo, direito;
        private int tamanho; // Número de nós na subárvore
        
        public No(Chave chave, Valor valor, int tamanho) {
            this.chave = chave;
            this.valor = valor;
            this.tamanho = tamanho;
        }
    }
    
    private No raiz;
    
    // Retorna o número de pares chave-valor na árvore
    public int tamanho() {
        return tamanho(raiz);
    }
    
    private int tamanho(No no) {
        if (no == null) return 0;
        return no.tamanho;
    }
    
    // Retorna o valor associado à chave especificada
    public Valor buscar(Chave chave) {
        return buscar(raiz, chave);
    }
    
    private Valor buscar(No no, Chave chave) {
        if (no == null) return null;
        
        int comparacao = chave.compareTo(no.chave);
        
        if (comparacao < 0) {
            return buscar(no.esquerdo, chave);
        } else if (comparacao > 0) {
            return buscar(no.direito, chave);
        } else {
            return no.valor;
        }
    }
    
    // Insere um novo par chave-valor na árvore
    public void inserir(Chave chave, Valor valor) {
        raiz = inserir(raiz, chave, valor);
    }
    
    private No inserir(No no, Chave chave, Valor valor) {
        if (no == null) {
            return new No(chave, valor, 1);
        }
        
        int comparacao = chave.compareTo(no.chave);
        
        if (comparacao < 0) {
            no.esquerdo = inserir(no.esquerdo, chave, valor);
        } else if (comparacao > 0) {
            no.direito = inserir(no.direito, chave, valor);
        } else {
            no.valor = valor; // Atualiza o valor se a chave já existe
        }
        
        // Atualiza o tamanho do nó
        no.tamanho = tamanho(no.esquerdo) + tamanho(no.direito) + 1;
        return no;
    }
    
    // Retorna a menor chave da árvore
    public Chave minimo() {
        return minimo(raiz).chave;
    }
    
    private No minimo(No no) {
        if (no.esquerdo == null) return no;
        return minimo(no.esquerdo);
    }
    
    // Retorna a maior chave da árvore
    public Chave maximo() {
        return maximo(raiz).chave;
    }
    
    private No maximo(No no) {
        if (no.direito == null) return no;
        return maximo(no.direito);
    }
    
    // Retorna a chave de rank k (k-ésima menor chave)
    public Chave selecionar(int k) {
        return selecionar(raiz, k).chave;
    }
    
    private No selecionar(No no, int k) {
        if (no == null) return null;
        
        int tamanhoEsquerdo = tamanho(no.esquerdo);
        
        if (k < tamanhoEsquerdo) {
            return selecionar(no.esquerdo, k);
        } else if (k > tamanhoEsquerdo) {
            return selecionar(no.direito, k - tamanhoEsquerdo - 1);
        } else {
            return no;
        }
    }
    
    // Retorna o rank (posição) de uma chave
    public int rank(Chave chave) {
        return rank(raiz, chave);
    }
    
    private int rank(No no, Chave chave) {
        if (no == null) return 0;
        
        int comparacao = chave.compareTo(no.chave);
        
        if (comparacao < 0) {
            return rank(no.esquerdo, chave);
        } else if (comparacao > 0) {
            return 1 + tamanho(no.esquerdo) + rank(no.direito, chave);
        } else {
            return tamanho(no.esquerdo);
        }
    }
    
    // Remove o menor nó da árvore
    public void removerMinimo() {
        raiz = removerMinimo(raiz);
    }
    
    private No removerMinimo(No no) {
        if (no.esquerdo == null) {
            return no.direito;
        }
        
        no.esquerdo = removerMinimo(no.esquerdo);
        no.tamanho = tamanho(no.esquerdo) + tamanho(no.direito) + 1;
        return no;
    }
    
    // Remove um nó com a chave especificada
    public void remover(Chave chave) {
        raiz = remover(raiz, chave);
    }
    
    private No remover(No no, Chave chave) {
        if (no == null) return null;
        
        int comparacao = chave.compareTo(no.chave);
        
        if (comparacao < 0) {
            no.esquerdo = remover(no.esquerdo, chave);
        } else if (comparacao > 0) {
            no.direito = remover(no.direito, chave);
        } else {
            // Nó encontrado
            if (no.direito == null) return no.esquerdo;
            if (no.esquerdo == null) return no.direito;
            
            // Nó com dois filhos
            No temp = no;
            no = minimo(temp.direito);
            no.direito = removerMinimo(temp.direito);
            no.esquerdo = temp.esquerdo;
        }
        
        no.tamanho = tamanho(no.esquerdo) + tamanho(no.direito) + 1;
        return no;
    }
}

A eficiência dos algoritmos de árvore de busca binária depende da forma da árvore. No melhor caso, uma árvore com N nós está perfeitamente balanceada, e a altura da árvore é log N. No pior caso, a altura pode ser N (quando os nós são inseridos em ordem crescente ou decrescente). Essa variabilidade de desempenho pode ser resolvida com árvores de busca balanceadas, que garantem que a altura da árvore permaneça log N independentemente da ordem de inserção.

4. Árvores de Busca Balanceada Árvores de busca balanceada são estruturas que mantêm a árvore aproximadamente balanceada para garantir operações eficientes (tempo logarítmico). 4.1 Árvores 2-3 As árvores 2-3 introduzem flexibilidade permitindo que nós contenham múltiplas chaves:

• Nó 2-nó: Contém uma chave e dois filhos
• Nó 3-nó: Contém duas chaves e três filhos As árvores 2-3 crescem de baixo para cima (divisão de nós), garantindo a balanceamento. No entanto, sua implementação é complexa devido à necessidade de manter diferentes tipos de nós. 4.2 Árvores Vermelho-Negras As árvores vermelho-negras são uma representação de árvores 2-3 usando apenas nós 2-nós com links coloridos:
• Links vermelhos: Conectam dois 2-nós para formar um 3-nó
• Links pretos: Links normais da árvore 2-3 Propriedades das árvores vermelho-negras:

1. Todos os links vermeelhos são links à esquerda
2. Nenhum nó tem dois links vermelhos conectados a ele >A árvore está "perfeitamente balanceada em preto" - todos os caminhos de um nó folha até a raiz contêm o mesmo número de links pretos As operações de rotação e inversão de cores mantêm a árvore balanceada. As árvores vermelho-negras não buscam "balanceamento perfeito", mas apenas balanceamento parcial, reduzindo as exigências de rotação e melhorando o desempenho. Aplicações em Java:

• TreeMap e TreeSet na API Java Collections usam árvores vermehlo-negras
• Embora sejam mais lentos que HashMap e HashSet para inserções e buscas individuais, mantêm as chaves ordenadas, o que é vantajoso para muitas aplicações