Doido Dev

Introdução às Árvores Vermelha e Preta A árvore vermelha e preta é uma variação de árvore binária de busca auto-balanceável que garante desempenho eficiente em operações de inserção, remoção e busca — todas com complexidade temporal O(log n). Em comparação com a árvore AVL, ela adota um equilíbrio mais flexível, permitindo alturas ligeiramente ...

1. Pilha Mínima (Min Stack) Descrição do Problema Implementar uma estrutura de pilha que suporte as operações padrão (push, pop, top) e também retorne o menor elemento em tempo constante (O(1)). A solução não pode percorrer a pilha para encontrar o mínimo a cada chamada. Análise do Algoritmo A abordagem clássica utiliza duas pilhas: uma pilha p ...

Conteúdo dos Problemas Os problemas abordam temas variados com complexidade crescente. T1 envolve manipulação de sequências binárias, T2 utiliza árvores binárias com operações matemáticas, T3 emprega travessia em grafos com detecção de ciclos, e T4 explora manipulação numérica com estratégias ótimas. T1: Contagem de Inversões Binárias Para tran ...

Problemas Clássicos com Árvores Binárias (sem DP em árvore) Os problemas abaixo não envolvem programação dinâmica em árvore, que será abordada em módulos futuros. Tópicos como árvores AVL e rotações também serão vistos posteriormente. 36.1 Travessia por Nível Método 1: Fila + tabela hash para níveis. Cada nó é armazenado na fila e seu nível ...

Introdução A travessia de árvores binárias pode ser implementada iterativamente utilizando estruturas de dados auxiliares. Abordaremos quatro variações: pré-ordem, em-ordem, pós-ordem e em nível. Pré-Ordem Visita o nó atual antes de seus descendnetes. Utiliza-se uma pilha para rastrear nós pendentes. A lógica consiste em: Empilhra a raiz Enqua ...