import java.io.*;
import java.lang.*;
import java.util.*;

public class ArbreAVL {

  // \esc{De'claration d'un arbre, voir page \pageref{prog:declaration-arb}}
  int         contenu;
  ArbreAVL    filsG;
  ArbreAVL    filsD;
  int         bal;

  ArbreAVL (int v, ArbreAVL a, ArbreAVL b) {
      contenu = v;
      filsG = a;
      filsD = b;
  }

  public static ArbreAVL nouvelArbreAVL (int v, ArbreAVL a, ArbreAVL b) {
  // \esc{Ajouter dans un arbre, voir page \pageref{prog:ajouter-arb}}

      return new ArbreAVL (v, a, b);
  }

  static void imprimer (ArbreAVL a, int tab) {
  // \esc{Impression d'un arbre, voir page \pageref{prog:imprimer-arb}} 

    if (a != null) {
      System.out.print (lAligned (3, a.contenu + "") + "     "); 
        imprimer (a.filsD, tab + 8);
        if (a.filsG != null) {
            System.out.println ();
            for (int i = 1; i <= tab; ++i)
                System.out.print (" ");
        }
        imprimer (a.filsG, tab);
    }
  }

  static String lAligned (int size, String s) {

    StringBuffer t = new StringBuffer (s);
    for (int i = s.length(); i < size; ++i)
        t = t.append(" ");
    return new String (t);
  }

  static void imprimerArbre (ArbreAVL a) {
    imprimer (a, 0);
    System.out.println ();
  }

  static ArbreAVL recherche (int v, ArbreAVL a) {
  // \esc{ArbreAVL de recherche, voir page \pageref{prog:recherche-arb-recherche}} 
    ArbreAVL      r = null;
    if (a == null || v == a.contenu)
         return a;
    else
         if (v < a.contenu)
             return recherche (v, a.filsG);
         else
             return recherche (v, a.filsD);
  }

  public static void main(String args[]) {

    ArbreAVL a =
         ajouter (25, ajouter (21, ajouter (20, ajouter (28,
         ajouter (3, ajouter (12, ajouter (6, ajouter (8, 
         ajouter (13, null)))))))));
    imprimerArbre (a);
  }

  static class Paire {
    int      champ1;
    ArbreAVL champ2;
    
    Paire (int r, ArbreAVL a) {
       champ1 = r;
       champ2 = a;
    }
  }

  static ArbreAVL ajouter (int v, ArbreAVL a) {
    return ajouter1 (v, a).champ2;
  }

  static Paire ajouter1 (int v, ArbreAVL a) {
  // \esc{Ajout dans un AVL, voir page \pageref{prog:ajout-avl}} 

    int        incr, r;
    Paire      p;
    
    r = 0;
    if (a == null) {
        a = nouvelArbreAVL (v, null, null);
        a.bal = 0;
        r = 1;
    } else {
       if (v <= a.contenu) {
            p = ajouter1 (v, a.filsG);
            incr = -p.champ1;
            a.filsG = p.champ2;
       } else {
            p = ajouter1 (v, a.filsD);
            incr = p.champ1;
            a.filsD = p.champ2;
      }
        a.bal = a.bal + incr;
        if (incr != 0 && a.bal != 0) 
            if (a.bal < -1)
                /* \esc{La gauche est trop grande} */
                if (a.filsG.bal < 0)
                    a = rotD (a);
                else {
                    a.filsG = rotG (a.filsG); 
                    a = rotD (a);
                }
            else
            if (a.bal > 1)
                /* \esc{La droite est trop grande} */
                if (a.filsD.bal > 0)
                    a = rotG (a);
                else {
                    a.filsD = rotD (a.filsD); 
                    a = rotG (a);
                }
            else
               r = 1;
    }
    return new Paire (r, a);
  }

  static ArbreAVL rotD (ArbreAVL a) {
  // \esc{Rotation dans un AVL, voir page \pageref{prog:rotation-avl}} 

    ArbreAVL  b;
    int       bA, bB, bAnew, bBnew;

    b = a;
    a = a.filsG;
    bA = a.bal; bB = b.bal;
    b.filsG = a.filsD;
    a.filsD = b;
    // \esc{\it Recalculer le champ \prog|a.bal|}
    bBnew = 1 + bB - Math.min(0, bA);
    bAnew = 1 + bA + Math.max(0, bBnew);
    a.bal = bAnew;
    b.bal = bBnew;
    return a;
  }

  static ArbreAVL rotG (ArbreAVL a) {
  // \esc{Rotation dans un AVL, voir page \pageref{prog:rotation-avl}}

    ArbreAVL  b;
    int       bA, bB, bAnew, bBnew;

    b = a.filsD;
    bA = a.bal; bB = b.bal;
    a.filsD = b.filsG;
    b.filsG = a;
    // \esc{\it Recalculer le champ \prog|a.bal|}
    bAnew = bA - 1 - Math.max(0, bB);
    bBnew = bB - 1 + Math.min(0, bAnew);
    a.bal = bAnew;
    b.bal = bBnew;
    return b;
  }
}