Árvore binária

Programação Java
#1

Tô precisando de um código de remoção em árvores binárias.

Só achei aqui o de inserção.

public void Inserir(No novo, No anterior){  
      if (anterior != null){  
         if (novo.ObtemValor() < anterior.ObtemValor())  
             //Como o novo nó tem valor menor do que o do nó anterior, desce para a esquerda do nó anterior.  
             inicio.filho_Esq=this.Insere(novo, anterior.filho_Esq);  
         else  
             if(novo.ObtemValor()>anterior.ObtemValor())  
                //Como o novo nó tem valor maior do que o do nó anterior, desce para a direita do nó anterior.  
                anterior.p_Dir=this.Insere(filho, anterior.filho_Dir);  
             else  
                //Caso seja um nó já existente, sai do método.  
                return;  
      }else  
           //Insere o novo nó como folha.  
           anterior = novo;  
  }

Alguém pode me ajudar aê?

#2

http://www.google.com.br
Pesquisa por binary tree java / árvore binária java ou remove node from binary tree java

Vai haver muitos resultados lá.

Se não entender algum, posta aqui o código que tentaremos ajudar.

#3

Vocês podem me dizer quais são as operações de uma árvore binária?

Uma função recursiva é quando ela chama a si mesma, certo?

#4

Inserir e, se preciso, balancear. Remover e, se preciso, balancear. Basicamente, isto.

Sim, recursividade é a ação de chamar a si mesmo.

#5

Como assim balancear?

#6

Amigo, uma árvore binária precisa, a cada inserção, verificar se os elementos estão balanceados. Simples, pense que você inseriu 5 elementos, vamos representá-los por valores 1, 5, 3, 10 e 8. Como a árvore ordena os elementos à maneira que chegam, respeitando o “valor” maior para direita e menor à esquerda, teríamos algo

  1
      5
    3  8
          10

//ou

                1
           3
              5
           8
        10

Certo?
A árvore está errada, pendendo para o lado direito (há mais níveis no lado direito que no esquerdo do nó principal, o 1).
Para isto, a árvore terá de se reordenar ou seja, balancear.
Ela fará rotações dos nós até ter o formato mais equilibrado

     5
  3   8
1      10
//ou

 1
   3
     5
   8
10

Percebeu?
O nó 1 é o menor, portanto, ele será deslocado para a posição mais à esquerda. O elemento 5 é o mais equilibrado, fica como nó principal. O elemento 10 é o maior, fica como último, à direita. 3 e 8 são intermediários.
Caso você adicione 2

       5
    2    8
  1 3    10
//ou

  1
     2
  3     5
     8
  10

Entendeu?

Essa é a estrutura básica de uma árvore binária.

Sugiro ler um pouco sobre ela.

#7

Então se a árvore não tiver balanceada eu faço o que chamam de heap sort? Um algoritmo de ordenação…

#8

Não.
Heap sort, bobble sort ou afins não se aplicam diretamente à árvores.
Você até pode criar uma árvore binária sem balanceamento, mas ela perde a “funcionalidade”. Haja visto o exemplo que dei.
O que você precisa fazer, ao implementar a árvore binária é “prever” estas condições.
Ela pode ter rotação simples ou dupla à direita ou à esquerda, ou ainda, rotação simples direita-esquerda, dependendo do que for inserido nela.
Sempre haverá a verificação, para o nó principal, sendo o valor inserido maior que o nó principal, este elemento será colocado à sua esquerda. No próximo nível, a comparação é refeita, se for maior, vai para à direita, até encontrar um nó ao qual possa se encaixar.
Se menor, vai para à esquerda. Assim sucessivamente.
Quando um lado possui profundidade (diferença entre o nível que possui os últimos nós até o principal) maior que o outro, é preciso fazer o balanceamento.

Tem muita coisa na net, eu vi isto em C, mas é fácil compreender como funciona.

#9

Então o heap sort é outro tipo de estrutura de dados, certo?

#10

Sort = organizar. Ele serve para ordenar determinadas estruturas (eu usava com vetores e matrizes)

#11