słownik

package avl2;

import java.io.DataInputStream;
import java.io.DataOutputStream;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Scanner;

public class AvlTree<AnyType extends Comparable<? super AnyType>>
{

 public AvlTree( )
 {
     root = null;
 }

 public void insert( AnyType x, ArrayList<String> s )
 {
     root = insert( x,s, root );
 }

 public void remove( AnyType x )
 {
     root = remove( x, root );
 }

 private AvlNode<AnyType> remove( AnyType x, AvlNode<AnyType> t )
 {
     if( t == null )
         return t;   // Item not found; do nothing

     int compareResult = x.compareTo( t.element );

     if( compareResult < 0 ){
         porównania++;
         t.left = remove( x, t.left );}
     else if( compareResult > 0 ){
         porównania++;
         t.right = remove( x, t.right );}
     else if( t.left != null && t.right != null ) // Two children
     {
         porównania++;
         t.element = findMin( t.right ).element;
         t.right = remove( t.element, t.right );
     }
     else
         t = ( t.left != null ) ? t.left : t.right;
     return balance( t );
 }

 public AnyType findMin( )
 {
     if( isEmpty( ) )
         return null;
     return findMin( root ).element;
 }

 public AnyType findMax( )
 {
     if( isEmpty( ) )
         return null;
     return findMax( root ).element;
 }

 public ArrayList<String> find( AnyType x )
 {
     return find( x, root );
 }

 private ArrayList<String> find( AnyType x, AvlNode<AnyType> t )
 {
     while( t != null )
         if( x.compareTo( t.element ) < 0 ){
             porównania++;
             t = t.left;}
         else if( x.compareTo( t.element ) > 0 ){
             porównania++;
             t = t.right;}
         else
             return t.meaning;    // Match

     ArrayList<String> tmp = new ArrayList<>();
     tmp.add("Brak tlumaczen slowa ....");
     return tmp;   // No match
 }

 public boolean contains( AnyType x )
 {
     return contains( x, root );
 }

 public void makeEmpty( )
 {
     root = null;
 }

 public boolean isEmpty( )
 {
     return root == null;
 }

 public void printTree( )
 {
     if(isEmpty())
         System.out.println( "Pusty Plik" );
     else
         printTree( root );
 }

 public void binaryWrite() throws IOException
 {
     if(isEmpty())
         System.out.println( "Pusty Plik" );
     else
     {
         DataOutputStream DIS = new DataOutputStream(new FileOutputStream("file"));
         DIS.close();
         binaryWrite(root);
     }
 }

 public void binaryRead()
 {
     binaryRead(root);
 }

 private void binaryRead( AvlNode<AnyType> t)
 {
         try {
            DataInputStream DIS = new DataInputStream(new FileInputStream("file"));
            int k = (DIS.available()/2);
            String s = new String();
            String bufor = new String();
            ArrayList<String> mean = new ArrayList<>();
            char h;
            while((k--) != 0)
            {
                h = DIS.readChar();
                if(h == '|')
                {
                    s = bufor;
                    bufor = new String();
                }
                else if(h == '@')
                {
                    mean.add(bufor);
                    bufor = new String();
                }
                else if(h == '#')
                {
                    root = insert((AnyType)s, mean, root);
                    bufor = new String();
                    mean = new ArrayList<>();
                }
                else
                {
                    bufor += h;
                }
            }
            DIS.close();
        }
         catch (FileNotFoundException e) {
            System.out.println("Nie ma takiego pliku");
         }
         catch(IOException e) {
              e.printStackTrace();
              System.out.println("Blad I/O");
         }
 }

 private void  binaryWrite(AvlNode<AnyType> t) throws IOException
 {
     if(t != null)
     {
         DataOutputStream DOS = new DataOutputStream(new FileOutputStream("file", true));
         DOS.writeChars((String) t.element);
         DOS.writeChar('|');
         for(int i =0; i < t.meaning.size(); ++i)
         {
             DOS.writeChars(t.meaning.get(i));
             DOS.writeChar('@');
         }
         DOS.writeChar('#');
         DOS.close();
         binaryWrite(t.left);
         binaryWrite(t.right);
     }
 }

 private static final int ALLOWED_IMBALANCE = 1;

 private AvlNode<AnyType> balance( AvlNode<AnyType> t )
 {
     if( t == null )
         return t;

     if( height( t.left ) - height( t.right ) > ALLOWED_IMBALANCE )
         if( height( t.left.left ) >= height( t.left.right ) )
             t = rotateWithLeftChild( t );
         else
             t = doubleWithLeftChild( t );
     else
     if( height( t.right ) - height( t.left ) > ALLOWED_IMBALANCE )
         if( height( t.right.right ) >= height( t.right.left ) )
             t = rotateWithRightChild( t );
         else
             t = doubleWithRightChild( t );

     t.height = Math.max( height( t.left ), height( t.right ) ) + 1;
     return t;
 }

 public void checkBalance( )
 {
     checkBalance( root );
 }

 private int checkBalance( AvlNode<AnyType> t )
 {
     if( t == null )
         return -1;

     if( t != null )
     {
         int hl = checkBalance( t.left );
         int hr = checkBalance( t.right );
         if( Math.abs( height( t.left ) - height( t.right ) ) > 1 ||
                 height( t.left ) != hl || height( t.right ) != hr )
             System.out.println( "OOPS!!" );
     }

     return height( t );
 }
 static int porównania=0;
 private AvlNode<AnyType> insert( AnyType x,ArrayList<String> s , AvlNode<AnyType> t )
 {
     if( t == null )
         return new AvlNode<>( x,s, null, null );

     int compareResult = x.compareTo( t.element );

     if( compareResult < 0 ){
         porównania++;
         t.left = insert( x,s, t.left );}
     else if( compareResult > 0 ){
         porównania++;
         t.right = insert( x,s, t.right );}
     else
         ;  // Duplicate; do nothing
     return balance( t );
 }

 private AvlNode<AnyType> findMin( AvlNode<AnyType> t )
 {
     if( t == null )
         return t;

     while( t.left != null )
         t = t.left;
     return t;
 }

 private AvlNode<AnyType> findMax( AvlNode<AnyType> t )
 {
     if( t == null )
         return t;

     while( t.right != null )
         t = t.right;
     return t;
 }

 private boolean contains( AnyType x, AvlNode<AnyType> t )
 {
     while( t != null )
     {
         int compareResult = x.compareTo( t.element );

         if( compareResult < 0 )
             t = t.left;
         else if( compareResult > 0 )
             t = t.right;
         else
             return true;    // Match
     }

     return false;   // No match
 }

 private void printTree( AvlNode<AnyType> t )
 {
     if( t != null )
     {
         printTree( t.left );
         System.out.println( t.element );
         printTree( t.right );
     }
 }

 private int height( AvlNode<AnyType> t )
 {
     return t == null ? -1 : t.height;
 }
static int rotacja=0;
 private AvlNode<AnyType> rotateWithLeftChild( AvlNode<AnyType> k2 )
 {
     AvlNode<AnyType> k1 = k2.left;
     k2.left = k1.right;
     k1.right = k2;
     k2.height = Math.max( height( k2.left ), height( k2.right ) ) + 1;
     k1.height = Math.max( height( k1.left ), k2.height ) + 1;
     rotacja++;
     return k1;
 }

 private AvlNode<AnyType> rotateWithRightChild( AvlNode<AnyType> k1 )
 {
     AvlNode<AnyType> k2 = k1.right;
     k1.right = k2.left;
     k2.left = k1;
     k1.height = Math.max( height( k1.left ), height( k1.right ) ) + 1;
     k2.height = Math.max( height( k2.right ), k1.height ) + 1;
     rotacja++;
     return k2;
 }
 static int rotacja2=0;
 private AvlNode<AnyType> doubleWithLeftChild( AvlNode<AnyType> k3 )
 {
     k3.left = rotateWithRightChild( k3.left );
     rotacja2++;
     return rotateWithLeftChild( k3 );
 }

 private AvlNode<AnyType> doubleWithRightChild( AvlNode<AnyType> k1 )
 {
     k1.right = rotateWithLeftChild( k1.right );
     rotacja2++;
     return rotateWithRightChild( k1 );
 }

 private static class AvlNode<AnyType>
 {
     AvlNode( AnyType theElement,ArrayList<String> m ,AvlNode<AnyType> lt, AvlNode<AnyType> rt )
     {
         element  = theElement;
         meaning =  m;
         left     = lt;
         right    = rt;
         height   = 0;
     }

     AnyType           element;      // The data in the node
     ArrayList<String> meaning;
     AvlNode<AnyType>  left;         // Left child
     AvlNode<AnyType>  right;        // Right child
     int               height;       // Height
 }


 private AvlNode<AnyType> root;

 public static void main( String [ ] args ) throws IOException
 {
     AvlTree<String> t = new AvlTree<>( );
     Scanner sc = new Scanner(System.in);
     int opt = 1;
     while(opt != 0)
     {
         System.out.println("rotacje1:"+rotacja);
         System.out.println("rotacje2:"+rotacja2);
         System.out.println("porównania:"+porównania);
        System.out.println("0- Zakoncz program, 1- Wstaw, 2- Szukaj, 3- Skasuj, 4- Zapisz slownik, 5- Wczytaj slownik, 6- Wypisz elementy slownika");
        opt = sc.nextInt();
        switch(opt)
        {
            case 1:
            {
                System.out.println("Podaj slowo do wstawienia");
                String s = sc.next();
                System.out.println("Podaj tlumaczenie, 0 - koniec");
                ArrayList<String> meanings = new ArrayList<>();
                String e;
                while(true)
                {
                    e = sc.next();
                    if(e.equals("0"))
                      break;
                    meanings.add(e);
                }
                t.insert(s, meanings);
                break;
            }
            case 2:
            {
                System.out.println("Podaj slowo do tlumaczenia");
                String s = sc.next();
                System.out.println(t.find(s));

                break;
            }
            case 3:
            {
                System.out.println("podaj slowo do skasowania");
                String s = sc.next();
                t.remove(s);
                break;
            }
            case 4:
            {

                t.binaryWrite();
                break;
            }
            case 5:
            {
                t.binaryRead();
                break;
            }
            case 6:
            {
                t.printTree();
                break;
            }
            default:
            {
                opt = 0;
                break;
            }

        }

     }
     sc.close();
 }
}