Data Structures

- Hash Table
Combinam uma tabela a uma função. Particiona o conjunto de dados a fim de facilitar a busca.
Aloca nos buckets
Vetor de vetores dinâmicos. Função matemática elaborada, ex: F(x) = x%10
Dispersão quando um buckets fica mais cheio. 16 bytes MD5, SHA-1

- Grafo
Grafo G consiste de um conjunto finito de elementos chamado vértice e um conjunto de pares não ordenados de vértices chamado arestas.
- algoritmo de bellman-ford
- Arvore
Binária
Raiz tem até dois filhos.
B
Raiz tem de 2 até N+1 filhos.
Nós interno tem [N/2]
Filhs [N/2]-1, N-1
Folhas sempre no mesmo nível
Ao remover
Redistribuição
Se os irmãos tiverem mais que o mínimo
Concatenação
Se os irmãos tiverem o mínimo
Ao remover o não folha, vai jogando pra baixo até virar folha.
Arvore Balanceada AVL
Se para cada nós as sub-arvores a direita ou esquerda tiverem a mesma altura ou de 1.
Fator de balanceamento(-1, 0 ou 1)
Se fator + rotação à esquerda
Se fator - rotação à direita
Arvore T
Baseada na AVL sendo binária e auto-balanceada.
Da B por ter estrutura de índice.
Balenaceamento como na AVL, mas com menos frequencia pq dados se movimento no nó.
Red-Black Tree
Tipo especial de arvore binária.
O nó raíz é negro.
Um nó vermelho só pode ter filhos negros. Nós inserido é sempre vermelho.
Todos os caminho a partir da raíz tem o mesmo número de nós pretos.
Splay tree
Itens mais acessados são movidos pra cima.
- Coloração de gráfico (coloring algorithm)
Para cada vértice, percorrer os seus vizinhos e colorí-los.
Escolher o nó com maior número de ligações.
- Minimax
Minimax for next move
Assume o oponente força vc a ir no pior caminho.
Maximizo a minha jogada e minimizo a adversário
- Alfta-Beta
Começa como o MinMax. Não expande a nós irrelevantes, pois faz a poda.
Na recursão pergunta se tem algum antecessor com valor "ctrário" maior ou menor.
Ex, se eu tive no MIN, pergunta se tem algum ancestral MAX maior que o elemento?
Se tiver no MAX, existe algum ancestral MIN menor que o elemento?