Listas Ligadas

Listas ligadas são estruturas de dados que permitem a criação de listas de elementos de forma dinâmica. Cada elemento da lista é chamado de nó e contém um valor e um ponteiro para o próximo nó da lista. O último nó da lista aponta para NULL.

ADT Lista Ligada

  • build(X): Cria uma nova lista ligada.
  • insert(X, L): Insere um novo elemento na lista.
  • delete(X, L): Remove um elemento da lista.
  • search(X, L): Busca um elemento na lista.
  • traverse(L): Percorre a lista.

Desafio: Inverter uma lista ligada.

Cache Misses

Árvores

Árvores Binárias

Uma árvore binária é uma estrutura de dados que consiste de um nó raiz e dois nós filhos, esquerdo e direito. Cada nó pode ter até dois filhos.

Árvores são estruturas recursivas todo nó é raiz de uma subárvore.

ADT Árvore Binária

  • build(X): Cria uma nova árvore binária.
  • insert(X, T): Insere um novo elemento na árvore.
  • delete(X, T): Remove um elemento da árvore.

Heap (Priority Queues/Binary Heap)

https://www.cs.usfca.edu/~galles/visualization/Heap.html

Árvores de Busca Binária

Uma árvore de busca binária é uma árvore binária onde cada nó tem um valor associado e a propriedade de que o valor de um nó é maior que todos os valores na subárvore à esquerda e menor que todos os valores na subárvore à direita.

Balanceamento de Árvores

Imagine que temos uma árvore de busca binária e inserimos a sequência de valores 1, 2, 3, 4, 5. A árvore resultante é uma lista ligada. Isso é ruim porque a complexidade de busca é O(n) e nosso objetivo com uma árvore de busca binária é obter complexidade O(log n).

Para resolver essa situação devemos fazer um balanceamento da árvore. Uma operação que envolve rotacionar certos nós da árvore baseado em alguns critérios.

Rotações

Ante de focarmos em critérios, vamos entender como uma árvore pode ser rotacionada. Rotacionar um nó x à esquerda envolve:

  1. Obter a subárvore da direita de x (seja y essa subárvore)
  2. A subárvore da esquerda de y se torna a subárvore da direita de x
  3. x se torna a subárvore da esquerda de y

O processo para rotacionar à direita é análogo. Basta inverter as direções.

NOTA: Aqui podemos pensar em pivôs. Ao rotacionar um nó x à esquerda, x.direita é o pivô. Ilustração: https://upload.wikimedia.org/wikipedia/commons/3/31/Tree_rotation_animation_250x250.gif.

AVLs

Árvores AVL são árvores de busca binária balanceadas. A propriedade que garante o balanceamento é que a diferença entre as alturas das subárvores de cada nó é no máximo 1.

Em uma AVL cada nó possui uma infomação que sua altura, deifnida como: 1 + max(altura(nó.esquerda), altura(nó.direita)). Assim uma árvore com um único nó, por exemplo, tem esse único nó (que é a raiz) como a altura sendo um.

A cada inserção a altura dos nós é atualizada de forma recursiva. Importante notar que a atulização é feita só naquela subárvore a qual o nó foi adicionado.

Rotações

Falando de rotações, elas acontecem assim que um desbalanceamento é detectado. Um desbalanceamento é detectado quando a diferença entre as alturas das subárvores de um nó é maior que 1.

Para rotacionar temos dois casos:

  1. Rotação simples: necessária sempre que o desbalanceamento é em linha reta. Ou seja, o nó desbalanceado é filho à direita de um filho à direita ou filho à esquerda de um filho à esquerda.
  2. Rotação dupla: necessária sempre que o desbalanceamento é em zig-zag. Ou seja, o nó desbalanceado é filho à direita de um filho à esquerda ou filho à esquerda de um filho à direita. A primeira rotação se livra do zig-zag assim voltando para o caso (1) e a segunda rotação resolve o desbalanceamento.

B-Trees

B-Trees são árvores balanceadas que permitem a inserção e remoção de elementos em tempo O(log n). São utilizadas em sistemas de arquivos e bancos de dados.