Untitled

https://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/AVLTreeST.java.html

public class AVL {
	 public class Node {
        private int data;		// info
        private int height;      // height of the subtree
        private int size;        // number of nodes in subtree
        private Node left;       // left subtree
        private Node right;      // right subtree
        
		public Node(int data, int height, int size, Node left, Node right) {
			this.data = data;
			this.height = height;
			this.size = size;
			this.left = left;
			this.right = right;
		}  
	}
	 Node root;
	 
	 public boolean isEmpty() {
	        return root == null;
	    }
	 // size 
	 public int size(Node x) {
	      return x == null ? 0 : x.size;
	    }
	 public int size() {
	        return size(root);
	    }
	 
	 // lấy chiều cao
	 private int height(Node x) {
	        if (x == null) return -1;
	        return x.height;
	    }
	 public int height() {
	        return height(root);
	    }
	 
	 // Search + check if present
	 private Node get(Node x, int data) {
	        if (x == null) return null;
	        int cmp = Integer.compare(data, x.data);
	        if (cmp < 0) return get(x.left, data);
	        else if (cmp > 0) return get(x.right, data);
	        else return x;
	    }
	 public boolean contains(int data) {
	        return get(root,data) != null;
	    }
	 
	 // Tìm hệ số cân bằng
	 private int balanceFactor(Node x) {
	        return height(x.left) - height(x.right);
	    }
	 // Quay trái:  
	 /*
	  * 		3						6
	  * 	  	  *			--->  	  *	  *
	  * 		    6			    3	    9
	  * 		  *	  *				  *
	  * 		5		9				5
	  * */
	 private Node rotateLeft(Node top) {
	        Node mid = top.right;
	        top.right = mid.left;
	        mid.left = top;
	        mid.size = top.size;
	        top.size = 1 + size(top.left) + size(top.right);
	        top.height = 1 + Math.max(height(top.left), height(top.right));
	        mid.height = 1 + Math.max(height(mid.left), height(mid.right));
	        return mid;
	    }
	 
	 // Quay phải: ngược lại
	 private Node rotateRight(Node top) {
	        Node mid = top.left;
	        top.left = mid.right;
	        mid.right = top;
	        mid.size = top.size;
	        top.size = 1 + size(top.left) + size(top.right);
	        top.height = 1 + Math.max(height(top.left), height(top.right));
	        mid.height = 1 + Math.max(height(mid.left), height(mid.right));
	        return mid;
	    }
	 
	 // Cây cân bằng khi hiệu chiều cao 2 chị em tối đa là 1 -> sai thì xoay: 4 trường hợp:
	 private Node balance(Node x) {
		 // hiệu < -1 (3-5) ~ cây nghiêng phải: Right -> Right-Right + Right-Left
	        if (balanceFactor(x) < -1) {
	            if (balanceFactor(x.right) > 0) {
	                x.right = rotateRight(x.right);
	            }
	            x = rotateLeft(x);
	        }
	     // hiệu > 1 (5-3) ~ cây nghiêng trái: Left -> Left - right + left - left
	        else if (balanceFactor(x) > 1) {
	            if (balanceFactor(x.left) < 0) {
	                x.left = rotateLeft(x.left);
	            }
	            x = rotateRight(x);
	        }
	        return x;
	    }
}