Baixe o app para aproveitar ainda mais
Prévia do material em texto
ECOI08 – Balanceamento e DSW Prof. Rafael Santos Email: rsantos@unifei.edu.br Balanceando uma árvore binária ◼ Uma das grandes vantagens das árvores ◼ possuir um processo de busca rápido ◼ depende muito de como é a árvore. ◼ Para garantir que todos os nós da árvore possuem um “processo de busca rápido” precisamos que a árvore esteja balanceada. ◼ Uma árvore binária é balanceada em altura ou simplesmente balanceada se: ◼ a diferença na altura de ambas as subárvores de qualquer nó na árvore é zero ou um. Balanceando uma árvore binária Altura Nós em um nível Nós em todos os níveis 1 20 = 1 1 = 21 – 1 2 21 = 2 3 = 22 – 1 3 22 = 4 7 = 23 – 1 4 23 = 8 15 = 24 – 1 : : : 11 210 = 1024 2047 = 211 – 1 : : : 14 213 = 8192 16383 = 214 – 1 : : : h 2h-1 n = 2h – 1 : : : Balanceando uma árvore binária ◼ Baseado na técnica de pesquisa binária 1. Armazene os dados em um vetor 2. Ordene o vetor 3. Designe para a raiz o elemento do meio do vetor 4. Agora o vetor tem duas submatrizes, refaça o passo 3 e 4 para cada submatriz até que todos os elementos tenham sido utilizados Balanceando uma árvore binária void balancear (TipoNo dados[], int primeiro, int ultimo, TipoApontador &p){ if(primeiro <= ultimo) { int meio = (primeiro + ultimo)/2; insere(dados[meio],p); balancear(dados, primeiro, meio-1, p); balancear(dados, meio+1, ultimo, p); } } Baseado na técnica de pesquisa binária Balanceando uma árvore binária ◼ Baseado na técnica de pesquisa binária Este algoritmo tem um sério inconveniente: todos os dados precisam ser armazenados em um vetor antes de construir a árvore. O algoritmo não é muito interessante em árvores dinâmicas pois teríamos que destruir e reconstruir a árvore a cada nova inserção. ◼ Neste caso não seria necessário o uso de métodos de ordenação, basta utilizar o percurso em in-ordem. Balanceando uma árvore binária ◼ O Algoritmo DSW Foi idealizado por Colin Day e melhorado por Quentin F. Stout e Bette L Warren. ◼ O algoritmo DSW (2 passos) 1. Transfigura uma árvore binária arbitrária em uma árvore parecida com lista ligada (espinha dorsal). 2. Então, essa árvore alongada é transformada em uma série de passes em uma árvore perfeitamente balanceada, girando repetidamente cada segundo nó da espinha dorsal ao redor de seu ascendente. Balanceando uma árvore binária ◼ O Algoritmo DSW O essencial para as transformações de árvores nesse algoritmo é a rotação. ◼ Há dois tipos de rotação simétricas A esquerda A direita. Balanceando uma árvore binária ◼ O Algoritmo DSW ◼ A rotação à direita do nó Ch com relação ao seu ascendente Par é realizada de acordo com o seguinte algoritmo: RotateRight (Gr, Par, Ch) if Par não é a raiz da árvore //isto e, se Gr não e nulo o avô Gr do filho Ch se torna o ascendente de Ch´s substituindo Par; a subárvore direita de Ch se torna a árvore esquerda do ascendente Par de Ch; o nó Ch obtém Par como seu filho direito; Gr Par Ch R P Q Gr Par Ch R P Q Balanceando uma árvore binária ◼ Primeira Fase (espinha dorsal) createBackbone(root, n) tmp = root; while (tmp != 0) if tmp tem um filho esquerdo gire esse filho ao redor de tmp; ajuste tmp para o filho que se tornou o ascendente; else ajuste tmp para o filho direito;
Compartilhar