Estruturas de Dados

1 - Balanceamento estático se baseia em destruir a árvore e recontruí-la de forma ordenada. Deve ser utilizada em casos onde poucos dados são adicionados à estrutura.

2 - Balanceamento dinâmico se baseia em balancear a árvore a cada nova inserção ou remoção de dados, de forma a sempre mantê-la ordenada. Deve ser utilizado em casos onde a inserção e remoção de dados é constante.

3 -

Rotaciona RR(NO N){ NO temporario = n.esquerda; n.esquerda = n.direita; n.direita = n.esquerda.direita; n.esquerdo.direita = n.esquerda.esquerda; n.esquerda.esquerda = temporario; dado tempd = n.dado; n.dado = n.esquerda; n.esquerda.dado = tempd; }

Rotaciona LL(NO N){ NO temporario = n.direita; n.direita = n.esquerda; n.esquerda = n.direita.esquerda; n.direita.esquerda = n.direita.direita; n.direita.direita = temporario; dado tempd = n.dado; n.dado = n.direita.dado; n.direita.dado = tempd; }

Rotaciona RL (NO N){ LL(n.esquerda); RR(n); }

Rotaciona LR(NO N){ RR(n.direita); LL(n); }

Boolean balanceado(NO N){ if (n == null){ retorna 1; }if(!balanceado(raiz.esquerda)){ retorne 0; }if(!balanceado(raiz.direita)){ retorne 0; }if(altura(raiz.esquerda)-altura(raiz.direita)>1){ retorne 0; }else{ retorne 1; } }

Faz balanceamento(NO N){ if(!balanceado(NO N)){ if(n.fator0){ faz RR(n); }if(n.fator0){ faz LR(n); }if(n.fator>0 && n.direita.fatorV; v++); |b|[v] = -1; for(v = 0; v < G->V; v++){ if(|b|[v] == -1){ dfsR(GV); } } }

"A função dfsR supõe que o grafo é represenado por uma matriz de aduacência" void dfsR(Grafo G, vertice v){ vertice w; |b|[v] = conta++; for(w = 0; w < G->V; w++){ if(G->adj[v][w] !=0){ if(|b|[w] == 1){ dfsR(G, w); } } } }