Lista de Exercico Em Arvores Binarias

1 – O que são árvores balanceadas? Remonte a árvore base de modo que a mesma fique balanceada.
R- Uma árvore é balanceada quando, para cada nó da árvore, a diferença entre as alturas das suas sub-árvores (direita e esquerda) não é maior do que um. Caso a árvore não esteja balanceada é necessário seu balanceamento através da rotação simples ou rotação dupla. O balanceamento é requerido para as operações de inserção e remoção de elementos.

2 –
a) Explique o que é um movimento de rotação?
R- A rotação ocorre devido ao seu desbalanceamento, uma rotação simples ocorre quando um nó está desbalanceado e seu filho estiver no mesmo sentido da inclinação, formando uma linha reta. Uma rotação-dupla ocorre quando um nó estiver desbalanceado e seu filho estiver inclinado no sentido inverso ao pai, formando um "joelho". - Rotação à direita
Deve ser efetuada quando a diferença das alturas h dos filhos de P é igual a 2 e a diferença das alturas h dos filhos de FE é igual a 1. O nó FE deve tornar o novo pai e o nó P deve se tornar o filho da direita de FE. Segue pseudocódigo:
Seja Y o filho à esquerda de X
Torne o filho à direita de Y o filho à esquerda de X.
Torne X o filho à direita de Y

- Rotação à esquerda
Deve ser efetuada quando a diferença das alturas h dos filhos de P é igual a -2 e a diferença das alturas h dos filhos de FD é igual a -1. O nó FD deve tornar o novo pai e o nó P deve se tornar o filho da esquerda de FD. Segue pseudocódigo:
Seja Y o filho à direita de X
Torne o filho à esquerda de Y o filho à direita de X.
Torne X filho à esquerda de Y
b) A diferença então é que, enquanto a rotação à direita utiliza a diferença das alturas h pelos FE, a rotação à esquerda utiliza a diferença das alturas h pelos FD.

c) public void troca (No pai) { No p1 = pai.filhoDireita; No p2 = p1.filhoEsquerda; No p3 = p2.filhoEsquerda; pai.filhoDireita(p2); p2.filhoDireita(p1); }
Foi utilizado uma rotação à