Aula nº 23

Nesta aula, trataremos dos seguintes tópicos:

Antes de explicar como se elimina, recordemos do seguinte:

  • Definição:
      A árvore AVL é uma árvore de procura binária (binary search tree - BST) cuja a altura das sub-árvores, esquerda e direita, da raiz diferem no máximo em 1, sendo estas sub-árvores também árvores AVL.

  • Árvore AVL também é árvore AVL.

  • Para representar o balaceamento de uma árvore AVL, usamos a seguinte representação:
    • "=" - Ambas das sub-árvores do nó comtêm a mesma altura.
    • "\" - A sub-árvore direita do nó contêm +1 de altura do a da esquerda.
    • "/" - A sub-árvore esquerda do nó contêm +1 de altura do a da direita.
Notas:
  • Nos exemplos ilustrados, h representa a altura da sub-árvore.
  • A eliminação é representada por um X (riscos :) ) a vermelho.
    • Na eliminação em árvores AVL, temos os seguintes casos:
      Caso 1 :
        O nó pai tem altura balanceada.
        Eliminamos um dos seus filhos (esquerda ou direita).

        Ex:
        AVL: Caso 1

        A árvore continua balanceada.

      Caso 2 :
        O nó pai tem altura maior um dos lados (esquerda ou direita).
        Eliminamos no lado que contêm maior altura.

        Ex:
        AVL: Caso 2

        A altura da árvore pode ter mudado. É necessário fazer verificações na parte restante da árvore.

      Caso 3 :
        O nó pai tem altura maior um dos lados (esquerda ou direita).
        Eliminamos no lado que contêm menor altura.

        Ex:
        AVL: Caso 3

        A diferença de altura nesse nó fica a 2, o que invalida a sua condição de árvore AVL, neste caso é necessário proceder-se a uma rotação do nó do lado maior para o lugar o pai.
        A parte restante da árvore não sofre alterações.

      Caso 4 :
        O nó pai tem altura maior um dos lados (esquerda ou direita).
        O nó do lado maior tem também altura maior num dos lados (esquerda ou direita).
        A eliminação é feita no lado menor do nó pai.

        Ex:
        AVL: Caso 4

        É necessário rebalancear a árvore, pois no nó C existe o problema da altura, sendo preciso fazer 2 rotações: C para B e C para A.
        A altura da árvore pode ter mudado. É necessário fazer verificações na parte restante da árvore.

      Caso 5 :
        (muito parecido ao caso anterior, mas só precisa de 1 rotação)
        O nó pai tem altura maior um dos lados (esquerda ou direita).
        O nó do lado maior tem também altura maior num dos lados (esquerda ou direita).
        A eliminação é feita no lado menor do nó pai.

        Ex:
        AVL: Caso 5

        É necessário rebalancear a árvore, pois no nó B existe o problema da altura, sendo preciso fazer 1 rotações: B para A.
        A altura da árvore pode ter mudado. É necessário fazer verificações na parte restante da árvore.

    Eliminação em árvoresRED-BLACK

    Antes de explicar como se elimina, relembre-mos as propriedades de uma árvore RED-BLACK.
    1. Só existem nós pretos e vermelhos;
    2. A raiz da àrvore nunca é preta;
    3. A altura em nós pretos em cada folha é sempre igual;
    4. Nunca existem 2 nós vermelhos juntos (se um nó é vermelho, os filhos e/ou o pai deste são sempre pretos);
    5. A inserção de um novo nó é sempre vermelho;
    6. Cada nil é sempre preto.

    Notas:
  • A eliminação deve ser feita da mesma forma duma árvore binária.

  • O nó desejado a ser eliminado tem, no máximo, um nó filho.

  • Nos casos ilustrados, o X representa o filho do nó eliminado.

  • Para melhor interpretação, considere também que os nós podem ser sub-árvores RED-BLACK.

    • Se eliminarmos um nó vermelho, ficamos sempre com uma árvore RED-BLACK, pois esta nunca tem 2 nós vermelhos seguidos e a altura de nós pretos em cada folha mantêm-se.

    Mas se eliminarmos um nó preto, teremos de resolver o seguintes problemas:


    • Se o filho do nó eliminado for vermelho:
        O filho passa a preto e faz-se uma rotação.
        (O filho passa para o lugar do pai).

    • Se o filho do nó eliminado for preto, este assume a posição do pai e verificamos os seguintes casos:

      Legenda:
      RED BLACK: Legenda
        Caso 1:
          O irmão de X é vermelho.
          RED BLACK: Caso 1

          Rotação D para B, e muda de cor. Transforma-se num caso 2b.

        Caso 2a:

          O irmão de X é preto.
          Os sobrinhos de X são pretos.

          RED BLACK: Caso 2a

          Diminiu-se a altura da árvore em 1.

        Caso 2b:

          O irmão de X é preto
          Os sobrinhos de X são pretos.
          O pai de X é vermelho.

          RED BLACK: Caso 2b

          Caso terminal. A árvore é Red-Black.

        Caso 3:

          O pai de X pode ser de qualquer cor (vermelho, preto)
          O irmão de X é preto
          O sobrinho direito de X é preto.
          O sobrinho esquerdo de X é vermelho.

          RED BLACK: Caso 3

          Transforma-se num caso 4.

        Caso 4:

          O pai de X pode ser de qualquer cor (vermelho, preto)
          O irmão de X é preto
          O sobrinho direito de X é vermelho.
          O sobrinho esquerdo de X é qualquer cor.

          RED BLACK: Caso 4

          Caso terminal, a árvore é RED-BLACK.

    Página feita pelos alunos:
    Ana Figueiredo
    Artur Jorge Martins
    no âmbito da cadeira de Programação e Estruturação de Dados da Universidade do Algarve.