1. Lista x Vetor
Vetor: Contínuos na memória.
<Desenho da memoria, subsecao de memoria>
Lista: Não contínua.
<Desenho, setinhas p la e p ca na memoria>
Lista Vetor
inserir 1 n
acessar n 1
buscar n n/logn se ordenado
remover 1 n
ordenar nlogn (merge)<link> nlogn (quick, etc)<links>
bubble, quick, merge sort
quick sort eh melhor com pivot aleatorio
Vetor: dinamico vs estatico
Estatico é rápido para alocar.<motivos> operacoes "rapido e rasteiro".
Na maratona a unica situação em q usamos dinamico eh qnd fazemos lista de adjacencia em grafo.<explicacao>
Nunca iremos usar malloc nem implementar lista na mão <usaremos a STL><destaque>
alocar dinamicamente é demorado pq depende do humor do SO.
2. Fila e Pilha
Fila é como fila de banco, o primeiro que entra é o primeiro que sai e furar fila é feio.
Pilha é como uma pilha de livros, você só poe ou tira livro do topo, senão tudo cai.
É bastante intuitivo então vou só botar o link da wikipédia para não ficar muito vazio.
Fila: http://pt.wikipedia.org/wiki/FIFO
Pilha: http://pt.wikipedia.org/wiki/LIFO
Usos bonitos de fila: BFS, Escalonador de Processos.
Usos bonitos de pilha: Parser XML, RPN ( http://en.wikipedia.org/wiki/Reverse_Polish_notation )
3. Árvores: BST, Heap
Árvore em estruturas discretas são: grafos conexos sem ciclos.<link p grafos>
<desenho de um grafo bobao>
Em estruturas de dados é a mesma coisa mais o conceito de raiz, que nesse ponto é um nó arbitrário.
Com isso vem uma hierarquia o conceito de pai e filho.
<desenho de arvore binaria>
Árvores Binárias são Arvores (de EDA) em que um nó pode ter no máximo 2 filhos.
Árvores Binárias de Busca (BST) são arvores binarias em q a ordenação dos nós é especial.
O valor dos nós a esquerda de um nó X é sempre menor que o valor dos nós da direita do mesmo.(geralmente, pode ser ao contrario…)
Busca na BST:
busca binaria intuitiva
A busca numa BST tem complexidade O(k), sendo k a altura da BST.<explicar>
<desenho da bst com o k do lado>
<inserção, remoção, rotação bla bla bla e complexidades>
rb tree -> stl usa em map e set <explicacao de set e map>
avl tree
Heap
p cada nó N, todos os filhos sao menores q N -> riz eh o maior de todos
(pode ser o contrário também, a raiz eh o menor e os filhos sao maiores)
argumento do ruan que tanto faz: multiplica tudo por -1.
inserir/(remover o maior/menor) logn
olhar o maior O(1)
no vetor:
qnd a raiz = 1
filho1 e filho2 do vertice v = 2*v e 2*v + 1, respectivamente
analogamente, como C arredonda p baixo, v=(f1 ou f2)/2
qnd a raiz = 1
filho1 e filho2 do vertice v = 2*v + 1 e 2*v + 2, respectivamente
analogamente, como C arredonda p baixo, v=((f1 ou f2)-1)/2