Guest User

Untitled

a guest
Jul 22nd, 2018
91
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 2.44 KB | None | 0 0
  1.  
  2.  
  3. public class L2Q1 {
  4.  
  5.     static class No {
  6.         int t;
  7.         int q;
  8.         No esquerda;
  9.         No direita;
  10.  
  11.         No(int t, int q) {
  12.             this.t = t;
  13.             this.q = q;
  14.             this.esquerda = null;
  15.             this.direita = null;
  16.         }
  17.     }
  18.  
  19.     static int altura(No raiz, No atual) {
  20.         int resposta = -1;
  21.         if (raiz == null) {
  22.             return -1;
  23.         }
  24.         if (atual.t > raiz.t) {
  25.             resposta = altura(raiz.direita, atual);
  26.         } else if (atual.t < raiz.t) {
  27.             resposta = altura(raiz.esquerda, atual);
  28.         }
  29.         return 1 + resposta;
  30.     }
  31.  
  32.     static No buscar(int t, No raiz) {
  33.         No resposta = raiz;
  34.         if (raiz != null) {
  35.             if (t > raiz.t) {
  36.                 resposta = buscar(t, raiz.direita);
  37.             } else if (t < raiz.t) {
  38.                 resposta = buscar(t, raiz.esquerda);
  39.             } else {
  40.                 resposta = raiz;
  41.             }
  42.         }
  43.         return resposta;
  44.     }
  45.  
  46.     static No resposta = null;
  47.     static No inserir(int t, int q, No raiz) {
  48.         if (raiz != null) {
  49.             if (t > raiz.t) {
  50.                 if (raiz.direita == null) {
  51.                     raiz.direita = new No(t, q);
  52.                     resposta = raiz.direita;
  53.                 } else {
  54.                     inserir(t, q, raiz.direita);
  55.                 }
  56.             } else {
  57.                 if (raiz.esquerda == null) {
  58.                     raiz.esquerda = new No(t, q);
  59.                     resposta = raiz.esquerda;
  60.                 } else {
  61.                     inserir(t, q, raiz.esquerda);
  62.                 }
  63.             }
  64.         }
  65.         return resposta;
  66.     }
  67.  
  68.     static No remover(int t, No raiz) {
  69.         No resposta = null;
  70.         if (raiz.direita != null) {
  71.             // sucessor
  72.         } else if (raiz.esquerda != null) {
  73.             // filho esquerda
  74.         } else {
  75.             // proprio no
  76.             resposta = null;
  77.         }
  78.         return resposta;
  79.     }
  80.  
  81.     public static void main(String[] args) {
  82.  
  83.         Arquivo arquivo = new Arquivo("L2Q1.in", "L2Q1.out");
  84.         No raiz = null;
  85.  
  86.         while (!arquivo.isEndOfFile()) {
  87.             int c = arquivo.readInt();
  88.             int t = arquivo.readInt();
  89.             int q = arquivo.readInt();
  90.             int altura = -1;
  91.             int quantidade = 0;
  92.             No atual = buscar(t, raiz);
  93.  
  94.             if (c == 0) {
  95.                 if (atual != null) {
  96.                     atual.q = atual.q + q;
  97.                 } else {
  98.                     if (raiz == null) {
  99.                         raiz = new No(t, q);
  100.                         atual = raiz;
  101.                     } else {
  102.                         atual = inserir(t, q, raiz);
  103.                     }
  104.                 }
  105.             } else {
  106.                 // TERMINAR O REMOVER
  107.                 if (atual != null) {
  108.                     if (q < atual.q) {
  109.                         atual.q = atual.q - q;
  110.                     } else {
  111.                         remover(t, raiz);
  112.                         atual = null;
  113.                     }
  114.                 }
  115.             }
  116.  
  117.             if (atual != null) {
  118.                 altura = altura(raiz, atual);
  119.                 // A RAIZ TÁ MUDANDO
  120.                 quantidade = atual.q;
  121.             }
  122.  
  123.             arquivo.println(altura + " " + quantidade);
  124.  
  125.         }
  126.  
  127.         arquivo.close();
  128.  
  129.     }
  130.  
  131. }
Add Comment
Please, Sign In to add comment