Avl - arvore binaria

Relat´rio Arvore Bin´ria AVL o ´ a
Carlos Eduardo Domingues e Rafael Dantas 28/9/2012

Cap´ ıtulo 1

Inser¸˜o ca
1.1 Problema:

Obtenha uma ´rvore AVL atrav´s da inser¸˜o da seguinte sequˆncia de valores: 14, 17, 11, 7, 53, a e ca e 4, 13, 12, 10

Inserindo: 1) 14, 17, 11, 7, 53; Para inserir esses 5 valores n˜o foi necess´rio efetuar nenhuma rota¸˜o, pois a diferen¸a entre a a a ca c altura do lado esquerdo e altura direita est´ entre -1 e 1, dif : [−1, 1]. a

Figura 1.1: Inserindo os valores 14, 17, 11, 7, 53 na ´rvore, e pode-se observar os fatores a de balaceamento dos respectivos n´s da ´rvore o a 2) 4; Inserindo o valor 4 na ´rvore percebe-se que ocorre um desbalanceamento cuja a diferen¸a da a c altura do n´ ´ de −2 e a diferen¸a de altura do n´ desbalanceado ´ de −1. Dessa forma foi o e c o e necess´rio rotacionar o n´ pai para a direita e o n´ filho do n´ desbalanceado para esquerda. a o o o

´ Figura 1.2: Arvore desbalanceada ap´s a inser¸˜o do 4 o ca

1

´ Figura 1.3: Arvore balanceada ap´s a rota¸˜o para direita do n´ desbalanceado o ca o 3) 13; Ao inserir o valor 13 nenhuma modifica¸˜o foi necess´ria j´ pois o fator de balanceamento est´ ca a a a dentro do intervalo dif : [−1, 1].

´ Figura 1.4: Arvore balanceada continua balanceada ap´s a inser¸˜o do 13 o ca 4) 12; Inserindo o valor 12 na ´rvore faz necess´rio modific´-la, pois mesma encontra-se desbalancea a a ada.Para resolver esse problema realiza-se uma rota¸˜o dupla com filho para direita e pai para ca esquerda. Esse tipo de rota¸˜o ´ feita quando fator de balanceamento do n´ pai vale 2 e o fator ca e o de balanceamento do n´ filho do n´ desbalanceado vale -1. o o

´ Figura 1.5: Arvore desbalanceada ap´s a inser¸˜o do 12 o ca

´ Figura 1.6: Arvore balanceada ap´s a rota¸˜o dupla com filho para direita e pai para o ca esquerda

2

5) 10; No caso da inser¸˜o do 10, ser˜o realizadas duas rota¸˜es para balancear ´rvore. Primeiro ser´ ca a co a a feita uma rota¸˜o dupla do n´