Estruturas de Dados

Uma estrutura de dados é uma organização de itens com uma regra de onde inserir e de onde procurar: essa regra fixa o custo de inserção, busca e remoção.

Busca, percursos e rebalanceamento deste tópico — e árvores B, conjuntos disjuntos e listas de adjacência nos tópicos seguintes — partem dessa disciplina.

As páginas se agrupam em quatro blocos. O primeiro organiza coleções lineares: empilha no topo, enfileira na frente e no trás (anel circular) e liga nós em lista.

O segundo mapeia a chave a um índice em {0,…,m−1} e trata colisão por lista ou por sondagem. O comprimento médio é α = n/m.

O terceiro organiza a árvore binária de busca: esquerda menor, direita maior. Busca, in-ordem crescente e remoção em três casos; sem teto extra a altura chega a n−1.

O quarto limita a altura a O(log n). AVL corrige FB com rotações; rubro-negra pinta nós e iguala a altura preta BH; SBB orienta apontadores em vertical ou horizontal.

A remoção em três casos e os percursos pré/in/pós-ordem estão em Árvores de Busca Binária. A inserção com rotações LL, RR, LR ou RL está em Árvores AVL.

Árvores AVL calcula FB = hₑ − h_d ∈ {−1, 0, 1} em cada nó. Árvores Rubro-Negras testa as cinco propriedades de cor e calcula BH.

O critério por cor do nó está em Árvores Rubro-Negras. O critério por orientação vertical ou horizontal do apontador está em Árvores SBB.

Colisão no mesmo h(k), com média Θ(1+α) e pior Θ(n), está em Tabelas Hash. Empilhar, enfileirar e religar nós está em Estruturas de Dados Elementares.