Cabula AED
May The Force Be With You
Diogo Sousa, Helder Martins, Daniel Parreira
5 de Fevereiro de 2012
1
Disclaimer
• Dictionary
– boolean isEmpty()
Se algo estiver errado avisem, mas se chumbarem no exame porque o que
aqui está não está correcto, i couldn’t care less.
– int size()
– V find(K k)
2
Resolução de Recorrências
2.1
– V remove(K k)
Recorrência I
– Iterator<Entry<K,V>> iterator()
Seja a ≥ 0, b ≥ 1 e c ≥ 1 constantes.
a
T (n) =
b · T (n − 1) + c
O(n)
b=1
=
O(bn ) b > 1
2.2
– V insert(K k, V v)
• Ordered Dictionary
– Todos os métodos de Dictionary.
n=0
n>0
– Entry<K,V> minEntry()
– Entry<K,V> maxEntry()
• Priority Queue
– boolean isEmpty()
Recorrência II (Master Theorem)
– int size()
Seja a ≥ 0, b ≥ 1 e c > 1 constantes e f (n) = O(nk ), para qualquer
k ≥ 0.
a
n=0
T (n) =
n>0
b · T(n
c ) + f (n)

k
 O(n )
=
O(nk logc (n))

O(nlogc (b) )
– Entry<K,V> minEntry()
– void insert(K k, V v)
– Entry<K,V> removeMin()
• Iterator<E>
b < ck
b = ck
b > ck
– boolean hasNext()
– E next()
– void rewind()
3
Tipos Abstractos de Dados
3.1
• TwoWayIterator<E>
– Todos os métodos de Iterator<E>
Operações
– boolean hasPrevious()
• Stack
– E previous()
– void fullForward()
– boolean isEmpty()
– int size()
• Entry<K,V>
– E top()
– K getKey()
– void push(E e)
– V getValue()
– E pop()
3.2
• Queue
Implementações
• Stack
– boolean isEmpty()
• Queue
– int size()
• List
– void enqueue(E e)
– E dequeue()
– Lista Ligada
∗
∗
∗
∗
• List
– boolean isEmpty()
– int size()
Simples
Dupla
Apenas com cabeça
Com cabeça e cauda
• Dictionary
– Iterator<E> iterator()
– E getFirst()
– Hashtable
∗ Separate Chaining (Dispersão Aberta)
∗ Open Addressing (Dispersão Fechada)
· Linear Probing (Sondagem linear)
· Double Hashing (Dispersão dupla)
– E getLast()
– E get(int p)
– int find(E e)
– void add(int p, E e)
• Ordered Dictionary
– void addFirst(E e)
– Binary Search Tree
– void addLast(E e)
– Red-Black Tree
– E remove(int p)
– AVL Tree
– E removeFirst()
• Priority Queue
– E removeLast()
– boolean remove(E e)
– Heap
1
3.3
Nós de EDs
4.3
AVL/Red-Black Tree
• BSTnode
Pesquisa
Insersão
Remoção
Min/Max
Iterar †
– BSTNode(K key, V value)
– BSTNode(K key, V value, BSTNode<K,V> left, BSTNode<K,V> right)
– EntryClass<K,V> getEntry()
Melhor caso
O(1)
O(lg(n))
O(lg(n))
O(lg(n))
O(n)
Pior Caso
O(lg(n))
O(lg(n))
O(lg(n))
O(lg(n))
O(n)
Caso Esperado
O(lg(n))
O(lg(n))
O(lg(n))
O(lg(n))
O(n)
† Isto é o custo de iterar, não de obter o iterador!
– K getKey()
– V getValue()
– BSTNode<K,V> getLeft()
4.4
– BSTNode<K,V> getRight()
– void setEntry(EntryClass<K,V> newEntry)
Criar c/ n
elementos
Inserir
Mı́nimo
Remover
Mı́nimo
– void setEntry(K newKey, V newValue)
– void setKey(K newKey)
– void setValue(V newValue)
– void setLeft(BSTNode<K,V> newLeft)
– void setRight(BSTNode<K,V> newRight)
4.5
– boolean isLeaf()
• DListNode
DListNode<E>
thePrevious,
– E getElement()
– DListNode<E> getPrevious()
– DListNode<E> getNext()
5
– void setElement(E newElement)
– void setPrevious(DListNode<E> newPrevious)
Pior Caso
O(n)
O(n)
Caso Esperado
O(n)
O(1)
O(1)
O(lg(n))
O(1)
O(lg(n))
O(1)
O(1)
O(lg(n))
O(lg(n))
Melhor caso
O(n)
O(n2 )
O(n2 )
O(n)
O(n lg(n))
O(n lg(n))
O(∞)
Pior Caso
O(n2 )
O(n2 )
O(n2 )
O(n lg(n))
O(n lg(n))
O(n2 )
O(∞)
Caso Esperado
O(n2 )
O(n2 )
O(n2 )
O(n lg(n))
O(n lg(n))
O(n lg(n))
O(∞)
Estavel
Sim
Sim
Não
Não
Sim
Não
?
Generalidades
5.1
– void setNext(DListNode<E> newNext)
Melhor caso
Ordenação
Insertion
Bubble
Selection
Heap
Merge
Quick
Jogo
– DListNode(E theElement)
– DListNode(E theElement,
DListNode<E> theNext)
Binary Heap
Árvores Binárias
• Uma árvore com n nós tem n + 1 sub-árvores vazias.
• AVLNode
• Uma árvore com n nós tem altura entre dlg(n + 1)e e n.
– AVLNode(K key, V value)
• Uma árvore diz-se perfeitamente equilibrada se para todo o nó o
número de nós no seu ramo esquerdo varia no máximo em uma
unidade absoluta do número de nós no seu ramo direito.
– AVLNode(K key, V value, char balance, AVLNode<K,V>
left, AVLNode<K,V> right)
– char getBalance()
• Uma árvore diz-se equilibrada se para todo o nó a altura do seu
ramo esquerdo varia no máximo em uma unidade absoluta da altura
do seu ramo direito.
– void setBalance(char newBalance)
• RBNode
• Percursos
– RBNode(K key, V value)
– RBNode(K key, V value, boolean colour, RBNode<K,V>
left, RBNode<K,V> right)
– Prefixo — raiz, sub-árvore esquerda, sub-árvore direita.
– Infixo — sub-árvore esquerda, raiz, sub-árvore direita.
– boolean getColour()
– Sufixo — sub-árvore esquerda, sub-árvore direita, raiz.
– boolean isRed()
– boolean isBlack()
5.2
– void setColour(boolean newColour)
– void makeRed()
– void makeBlack()
4
1. Cada nó é preto ou vermelho.
2. A raiz é preta.
Complexidades Temporais das
Estruturas de Dados
3. Filhos de nós vermelhos são pretos.
4. Todos os caminhos da raiz a qualquer árvore vazia têm o mesmo
número de nós pretos.
São omitidas as seguintes estruturas de dados por terem complexidade
constante em todas as operações, em todos os casos: Stack com lista
ligada, Queue com lista ligada. A lista ligada é omitida só porque sim!
4.1
HashTable (Separate Chaining )
Assume-se que a resolução de colisões é feita com a OrderedDLL.
Melhor caso
Pior Caso
Caso Esperado
Pesquisa
O(1)
O(n)
O(1 + λ)
Insersão
O(1)
O(n)
O(1 + λ)
Remoção
O(1)
O(n)
O(1 + λ)
4.2
Binary Search Tree
Pesquisa
Insersão
Remoção
Min/Max
Iterar †
Melhor caso
O(1)
O(1)
O(1)
O(1)
O(n)
Red-Black Tree
Mantém as seguintes propriedades:
Pior Caso
O(n)
O(n)
O(n)
O(n)
O(n)
Caso Esperado
O(lg(n))
O(lg(n))
O(lg(n))
O(lg(n))
O(n)
† Isto é o custo de iterar, não de obter o iterador!
2