::AVL Tree::

อัญชลี อริยะวุฒิพันธ์
483 06187 21


public class AvlNode {
	Comparable key;
    Object value;
    AvlNode left;
    AvlNode right;
    int height;
//Constructor
   public AvlNode(Comparable theKey, Object theValue) {
     this(theKey, theValue, null, null);
   }
//Constructor
   public AvlNode(Comparable theKey, Object theValue, AvlNode l, AvlNode r) {
    key = theKey;
    value = theValue;
    left = l;
    right = r;

   }
//Height of AVL Node
   public int height(AvlNode node) {
	     return (node == null) ? -1 : node.height;
	   }
 //Height of sub-AVL Tree
   public void setHeight() {
     height = 1 + Math.max(height(left), height(right));
   }

//Checking balanced value
   public int balancedValue() {
     return height(right) - height(left);
   }

 }



public class AvlTree {
	
	AvlNode root;
    int size;

   public AvlTree() {
     root = null;
     size = 0;
     
   }

   public int size() {
    return size;
  }

   public AvlNode getRoot() {
     return root;
  }

  public void insert(Comparable theKey, Object theValue) {
	     root = insert(root, theKey, theValue);
	   }
   private AvlNode insert(AvlNode n, Comparable x, Object v) {
     if (n == null) {
       n = new AvlNode(x, v);
       ++size;
     } else {
       if (x.compareTo(n.key) > 0)
         n.right = insert(n.right, x, v);
       else if (x.compareTo(n.key) < 0)
         n.left = insert(n.left, x, v);
     }
     n = rebalanced(n);
     return n;
   }

    

   public void remove(Comparable theKey) {
	     root = remove(root, theKey);
	   }
   private AvlNode remove(AvlNode n, Comparable x) {
    if (n == null)
       return n;
   
     if (x.compareTo(n.key) < 0)
       n.left = remove(n.left, x);
     else if (x.compareTo(n.key) > 0)
       n.right = remove(n.right, x);
     else {//node found
       if (n.left == null || n.right == null) {
         n = n.left == null ? n.right : n.left;
         --size;
       } else {
         AvlNode nRight = n.right;
         while (nRight.left != null)
           nRight = nRight.left;
         n.value = nRight.value;
         n.key = nRight.key;
         n.right = remove(n.right, nRight.key);
       }

     }
     n = rebalanced(n);
     return n;

   }

 
   public AvlTree findBetween(Comparable from, Comparable to) {
     return findBetween(root, from, to);
   }

 

   // ค้นหาโนดที่ from <= key <= to แล้วรีเทิร์น Avl tree

   // ที่สร้างจากโนดเหล่านี้

   private AvlTree findBetween(AvlNode n, Comparable from, Comparable to) {
    if (size == 0)
       return null;
     // แปลง tree เป็น array
     AvlNode[] arr = toArray();

     // สลับค่า from และ to ให้เป็น น้อย ==> มาก ตามลำดับ
     if (from.compareTo(to) > 0) {
       Comparable temp = from;
       from = to;
       to = temp;
     }

     // สร้าง tree ขึ้นมาใหม่ และใส่ของลงเฉพาะที่ from<= key <= to

     AvlTree re = new AvlTree();
     for (int i = 0; i < arr.length; ++i) {
       if ((arr[i].key.compareTo(from) >= 0)
           && (arr[i].key.compareTo(to) <= 0))
         re.insert(arr[i].key, arr[i].value);
     }

     // ถ้าไม่มี ลูกเลย retrun null

     if (re.size() == 0)
       return null;
     return re;

   }
// แปลง tree ไปเป็น array ของ AvlNode

   public AvlNode[] toArray() {
     if (size == 0)
       return null;
     AvlNode[] arr = new AvlNode[size];
     return toArray(root, arr, 0);
   }

 

   private AvlNode[] toArray(AvlNode r, AvlNode[] array, int index) {
     if (r != null) {
       array[index++] = r;
       toArray(r.left, array, index);
       int i = 0;
       for (i = 0; i < array.length; ++i)
         if (array[i] == null)
           break;
       index = i;
       toArray(r.right, array, index);

     }
     return array;
   }
 

   // หาว่าใน Tree มี โนดใดที่มี key เท่า กับตัวที่ต้องกสรไหม

   // ถ้ามี return Avlnode นั้นออกมา

   public AvlNode find(Comparable key) {
     if (root == null)
       return null;
     AvlNode re = root;
     while (re != null) {
       if (key.compareTo(re.key) > 0) {
         re = re.right;
       } else if (key.compareTo(re.key) < 0) {
         re = re.left;
       } else {
         return re;
       }

     }
     return null;
   }



   private AvlNode rotateLeftChild(AvlNode n) {
     AvlNode newRoot = n.left;
     n.left = newRoot.right;
     newRoot.right = n;
     newRoot.right.setHeight();
     newRoot.setHeight();
     return newRoot;
   }


   private AvlNode rotateRightChild(AvlNode n) {
     AvlNode newRoot = n.right;
     n.right = newRoot.left;
     newRoot.left = n;
     newRoot.left.setHeight();
     newRoot.setHeight();
     return newRoot;

   }


   private AvlNode rebalanced(AvlNode n) {
     if (n == null)
       return n;
    int balance = n.balancedValue();
     if (balance == -2) {
       if (n.left.balancedValue() == 1)
         n.left = rotateRightChild(n.left);
       n = rotateLeftChild(n);
     } else if (balance == 2) {
       if (n.right.balancedValue() == -1)
         n.right = rotateLeftChild(n.right);
       n = rotateRightChild(n);
     }
     n.setHeight();
    return n;
  }

 }

Hosted by www.Geocities.ws