fork download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6. import java.util.Scanner;
  7. import java.util.ArrayList;
  8.  
  9. class Ideone {
  10.  
  11.     public static void main(String[] args) {
  12.         Scanner entrada = new Scanner(System.in);
  13.         ArvoreAvl Avl = new ArvoreAvl();
  14.         int numero, op;
  15.         System.out.println("1 para inserir");
  16.         op = entrada.nextInt();
  17.         do {
  18.  
  19.             System.out.println("Informe o numero a ser inserido");
  20.             numero = entrada.nextInt();
  21.             Avl.inserir(numero);
  22.             System.out.println("1 para inserir");
  23.             op = entrada.nextInt();
  24.  
  25.         } while (op != 0);
  26.         System.out.println(Avl.inorder());
  27.         System.out.println("Qual valor deseja remover ?");
  28.         op = entrada.nextInt();
  29.         Avl.remover(op);
  30.         System.out.println(Avl.inorder());
  31.  
  32.     }
  33.  
  34. }
  35.  
  36. class ArvoreAvl {
  37.  
  38.     protected No raiz;
  39.     private int qtd = 0;
  40.  
  41.     public void inserir(int k) {
  42.         No n = new No(k);
  43.         inserirAVL(this.raiz, n);
  44.     }
  45.  
  46.     public void inserirAVL(No aComparar, No aInserir) {
  47.  
  48.         if (aComparar == null) {
  49.             this.raiz = aInserir;
  50.  
  51.         } else {
  52.  
  53.             if (aInserir.getChave() < aComparar.getChave()) {
  54.  
  55.                 if (aComparar.getEsquerda() == null) {
  56.                     aComparar.setEsquerda(aInserir);
  57.                     aInserir.setPai(aComparar);
  58.                     verificarBalanceamento(aComparar);
  59.  
  60.                 } else {
  61.                     inserirAVL(aComparar.getEsquerda(), aInserir);
  62.                 }
  63.  
  64.             } else if (aInserir.getChave() > aComparar.getChave()) {
  65.  
  66.                 if (aComparar.getDireita() == null) {
  67.                     aComparar.setDireita(aInserir);
  68.                     aInserir.setPai(aComparar);
  69.                     verificarBalanceamento(aComparar);
  70.  
  71.                 } else {
  72.                     inserirAVL(aComparar.getDireita(), aInserir);
  73.                 }
  74.  
  75.             } else {
  76.                 // O nó já existe
  77.             }
  78.         }
  79.     }
  80.  
  81.     public void verificarBalanceamento(No atual) {
  82.         setBalanceamento(atual);
  83.         int balanceamento = atual.getBalanceamento();
  84.  
  85.         if (balanceamento == -2) {
  86.  
  87.             if (altura(atual.getEsquerda().getEsquerda()) >= altura(atual.getEsquerda().getDireita())) {
  88.                 qtd++;
  89.                 atual = rotacaoDireita(atual);
  90.  
  91.             } else {
  92.                 qtd++;
  93.                 atual = duplaRotacaoEsquerdaDireita(atual);
  94.             }
  95.  
  96.         } else if (balanceamento == 2) {
  97.  
  98.             if (altura(atual.getDireita().getDireita()) >= altura(atual.getDireita().getEsquerda())) {
  99.                 qtd++;
  100.                 atual = rotacaoEsquerda(atual);
  101.  
  102.             } else {
  103.                 qtd++;
  104.                 atual = duplaRotacaoDireitaEsquerda(atual);
  105.             }
  106.         }
  107.  
  108.         if (atual.getPai() != null) {
  109.             verificarBalanceamento(atual.getPai());
  110.         } else {
  111.             this.raiz = atual;
  112.         }
  113.     }
  114.  
  115.     public void remover(int k) {
  116.         removerAVL(this.raiz, k);
  117.     }
  118.  
  119.     public void removerAVL(No atual, int k) {
  120.         if (atual == null) {
  121.             return;
  122.         } else {
  123.  
  124.             if (atual.getChave() > k) {
  125.                 removerAVL(atual.getEsquerda(), k);
  126.  
  127.             } else if (atual.getChave() < k) {
  128.                 removerAVL(atual.getDireita(), k);
  129.  
  130.             } else if (atual.getChave() == k) {
  131.                 removerNoEncontrado(atual);
  132.             }
  133.         }
  134.     }
  135.  
  136.     public void removerNoEncontrado(No aRemover) {
  137.         No r;
  138.  
  139.         if (aRemover.getEsquerda() == null || aRemover.getDireita() == null) {
  140.  
  141.             if (aRemover.getPai() == null) {
  142.                 this.raiz = null;
  143.                 aRemover = null;
  144.                 System.out.println("Quantidade de rotações necessárias= " + this.qtd);
  145.                 return;
  146.             }
  147.             r = aRemover;
  148.  
  149.         } else {
  150.             r = sucessor(aRemover);
  151.             aRemover.setChave(r.getChave());
  152.         }
  153.  
  154.         No p;
  155.         if (r.getEsquerda() != null) {
  156.             p = r.getEsquerda();
  157.         } else {
  158.             p = r.getDireita();
  159.         }
  160.  
  161.         if (p != null) {
  162.             p.setPai(r.getPai());
  163.         }
  164.  
  165.         if (r.getPai() == null) {
  166.             this.raiz = p;
  167.         } else {
  168.             if (r == r.getPai().getEsquerda()) {
  169.                 r.getPai().setEsquerda(p);
  170.             } else {
  171.                 r.getPai().setDireita(p);
  172.             }
  173.             verificarBalanceamento(r.getPai());
  174.         }
  175.  
  176.         r = null;
  177.         System.out.println("Quantidade de rotações necessarias " + this.qtd);
  178.     }
  179.  
  180.     public No rotacaoEsquerda(No inicial) {
  181.  
  182.         No direita = inicial.getDireita();
  183.         direita.setPai(inicial.getPai());
  184.  
  185.         inicial.setDireita(direita.getEsquerda());
  186.  
  187.         if (inicial.getDireita() != null) {
  188.             inicial.getDireita().setPai(inicial);
  189.         }
  190.  
  191.         direita.setEsquerda(inicial);
  192.         inicial.setPai(direita);
  193.  
  194.         if (direita.getPai() != null) {
  195.  
  196.             if (direita.getPai().getDireita() == inicial) {
  197.                 direita.getPai().setDireita(direita);
  198.  
  199.             } else if (direita.getPai().getEsquerda() == inicial) {
  200.                 direita.getPai().setEsquerda(direita);
  201.             }
  202.         }
  203.  
  204.         setBalanceamento(inicial);
  205.         setBalanceamento(direita);
  206.  
  207.         return direita;
  208.     }
  209.  
  210.     public No rotacaoDireita(No inicial) {
  211.  
  212.         No esquerda = inicial.getEsquerda();
  213.         esquerda.setPai(inicial.getPai());
  214.  
  215.         inicial.setEsquerda(esquerda.getDireita());
  216.  
  217.         if (inicial.getEsquerda() != null) {
  218.             inicial.getEsquerda().setPai(inicial);
  219.         }
  220.  
  221.         esquerda.setDireita(inicial);
  222.         inicial.setPai(esquerda);
  223.  
  224.         if (esquerda.getPai() != null) {
  225.  
  226.             if (esquerda.getPai().getDireita() == inicial) {
  227.                 esquerda.getPai().setDireita(esquerda);
  228.  
  229.             } else if (esquerda.getPai().getEsquerda() == inicial) {
  230.                 esquerda.getPai().setEsquerda(esquerda);
  231.             }
  232.         }
  233.  
  234.         setBalanceamento(inicial);
  235.         setBalanceamento(esquerda);
  236.  
  237.         return esquerda;
  238.     }
  239.  
  240.     public No duplaRotacaoEsquerdaDireita(No inicial) {
  241.         inicial.setEsquerda(rotacaoEsquerda(inicial.getEsquerda()));
  242.         return rotacaoDireita(inicial);
  243.     }
  244.  
  245.     public No duplaRotacaoDireitaEsquerda(No inicial) {
  246.         inicial.setDireita(rotacaoDireita(inicial.getDireita()));
  247.         return rotacaoEsquerda(inicial);
  248.     }
  249.  
  250.     public No sucessor(No q) {
  251.         if (q.getDireita() != null) {
  252.             No r = q.getDireita();
  253.             while (r.getEsquerda() != null) {
  254.                 r = r.getEsquerda();
  255.             }
  256.             return r;
  257.         } else {
  258.             No p = q.getPai();
  259.             while (p != null && q == p.getDireita()) {
  260.                 q = p;
  261.                 p = q.getPai();
  262.             }
  263.             return p;
  264.         }
  265.     }
  266.  
  267.     private int altura(No atual) {
  268.         if (atual == null) {
  269.             return -1;
  270.         }
  271.  
  272.         if (atual.getEsquerda() == null && atual.getDireita() == null) {
  273.             return 0;
  274.  
  275.         } else if (atual.getEsquerda() == null) {
  276.             return 1 + altura(atual.getDireita());
  277.  
  278.         } else if (atual.getDireita() == null) {
  279.             return 1 + altura(atual.getEsquerda());
  280.  
  281.         } else {
  282.             return 1 + Math.max(altura(atual.getEsquerda()), altura(atual.getDireita()));
  283.         }
  284.     }
  285.  
  286.     private void setBalanceamento(No no) {
  287.         no.setBalanceamento(altura(no.getDireita()) - altura(no.getEsquerda()));
  288.     }
  289.  
  290.     final protected ArrayList<No> inorder() {
  291.         ArrayList<No> ret = new ArrayList<No>();
  292.         inorder(raiz, ret);
  293.         return ret;
  294.     }
  295.  
  296.     final protected void inorder(No no, ArrayList<No> lista) {
  297.         if (no == null) {
  298.             return;
  299.         }
  300.         inorder(no.getEsquerda(), lista);
  301.         lista.add(no);
  302.         inorder(no.getDireita(), lista);
  303.     }
  304.  
  305. }
  306.  
  307. class No {
  308.  
  309.     private No esquerda;
  310.     private No direita;
  311.     private No pai;
  312.     private int chave;
  313.     private int balanceamento;
  314.  
  315.     public No(int k) {
  316.         setEsquerda(setDireita(setPai(null)));
  317.         setBalanceamento(0);
  318.         setChave(k);
  319.     }
  320.  
  321.     public String toString() {
  322.         return Integer.toString(getChave());
  323.     }
  324.  
  325.     public int getChave() {
  326.         return chave;
  327.     }
  328.  
  329.     public void setChave(int chave) {
  330.         this.chave = chave;
  331.     }
  332.  
  333.     public int getBalanceamento() {
  334.         return balanceamento;
  335.     }
  336.  
  337.     public void setBalanceamento(int balanceamento) {
  338.         this.balanceamento = balanceamento;
  339.     }
  340.  
  341.     public No getPai() {
  342.         return pai;
  343.     }
  344.  
  345.     public No setPai(No pai) {
  346.         this.pai = pai;
  347.         return pai;
  348.     }
  349.  
  350.     public No getDireita() {
  351.         return direita;
  352.     }
  353.  
  354.     public No setDireita(No direita) {
  355.         this.direita = direita;
  356.         return direita;
  357.     }
  358.  
  359.     public No getEsquerda() {
  360.         return esquerda;
  361.     }
  362.  
  363.     public void setEsquerda(No esquerda) {
  364.         this.esquerda = esquerda;
  365.     }
  366. }
  367.  
  368.  
Runtime error #stdin #stdout #stderr 0.08s 2184192KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1 para inserir
stderr
copy 
Exception in thread "main" java.util.NoSuchElementException
	at java.util.Scanner.throwFor(Scanner.java:862)
	at java.util.Scanner.next(Scanner.java:1485)
	at java.util.Scanner.nextInt(Scanner.java:2117)
	at java.util.Scanner.nextInt(Scanner.java:2076)
	at Ideone.main(Main.java:16)
https://ideone.com/0gFo9T
language:
Java (HotSpot 12)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!