Início » Posts etiquetados como 'árvores'

Arquivo da tag: árvores

[ED1] Aula 84 – Árvore AVL: Remoção

Olá pessoal

Depois de um pequeno descanso de carnaval, eis que chegamos a nossa última aula de árvore AVL: remoção de um nó.

Primeiramente, precisamos procurar recursivamente o nó a ser removido da árvore, o qual pode ser um nó folha ou um nó interno (que pode ser a raiz), com um ou dois filhos. Se este for um nó interno, é preciso reorganizar a árvore para que ela continue sendo uma árvore binária de busca.

Como na inserção, ao voltarmos da recursão é preciso tratar o balanceamento. Neste caso, valem as mesmas regras da inserção, mas com uma pequena diferença: remover um nó da sub-árvore da direita equivale a inserir um nó na sub-árvore da esquerda

Vamos a aula e até a próxima.

Anúncios

[ED1] Aula 83 – Árvore AVL: Inserção

Olá pessoal,

Hoje vamos ver como funciona a inserção na árvore AVL. Aqui, vamos tratar a inserção de forma recursiva. Assim, para inserir um valor “V” na árvore devemos seguir o seguinte conjunto de passos:

  • “raiz” é NULL: insira o nó
  • “V” é “menor” do que a raiz:  vá para a sub-árvore “esquerda”
  • “V” é “maior” do que a raiz: vá para a sub-árvore “direita”

Ao voltar na recursão, temos que recalcular as alturas de cada sub-árvore e aplicar a rotação necessária se o fator de balanceamento for +2 ou -2.

%d blogueiros gostam disto: