Untitled

mail@pastecode.io avatar
unknown
plain_text
7 months ago
9.5 kB
6
Indexable
Never
public class AVL {
	 Node root ;
	 
	 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) {
			this.data = data;
			this.height = height;
			this.size = size;
		}  
	}

	 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) {
		 return x == null ? 0 : 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;
	    }
	 
	 // MIN and MAX:
	 public Node min(Node x) {
	        if (x.left == null) return x;
	        return min(x.left);
	    }
	 public Node max(Node x) {
	        if (x.right == null) return x;
	        return max(x.right);
	    }
	 // INSERT
	 private Node insert(Node x, int data) {
		 // Leaf: new node: data, h = 1, size = 1;
	        if (x == null) return new Node(data, 1, 1);
	     
	        int cmp = Integer.compare(data, x.data);
	        if (cmp < 0) {
	            x.left = insert(x.left, data);
	        }
	        else if (cmp > 0) {
	            x.right = insert(x.right, data);
	        }
	        else {
	            x. data = data;
	            return x;
	        }
	        x.size = 1 + size(x.left) + size(x.right);
	        x.height = 1 + Math.max(height(x.left), height(x.right));
	        return balance(x);
	    }
	 public void insert(int data){
		 root = insert(root, data);
	 }
	// Delete: search + xoá thật
	// Hàm phụ trợ: xoá min of subtree 'x'-> gọi sau khi clone: nút cần xoá = minRight -> clear minRight
	 // @param Node x...chính là cây con phải của nút cần xoá:
	 private Node deleteMin(Node x) {
	        if (x.left == null) return x.right;
	        x.left = deleteMin(x.left);
	        x.size = 1 + size(x.left) + size(x.right);
	        x.height = 1 + Math.max(height(x.left), height(x.right));
	        return balance(x);
	 }
	 private Node delete(Node x, int data) {
		 // Search 
		 int cmp = Integer.compare(data, x.data);
	        if (cmp < 0) {
	            x.left = delete(x.left, data);
	        }
	        else if (cmp > 0) {
	            x.right = delete(x.right, data);
	        }
	     // found
	        else {
	            if (x.left == null) 
	                return x.right;

	            else if (x.right == null) 
	                return x.left;
	            
	            // đủ 2 con
	            else {
	                Node temp = x;
	                x = min(temp.right);
	                x.right = deleteMin(temp.right);
	                x.left = temp.left;
	            }
	        }
	        x.size = 1 + size(x.left) + size(x.right);
	        x.height = 1 + Math.max(height(x.left), height(x.right));
	        return balance(x);
	    }
	 public void delete(int data){
		 if (!contains(data)) return;
		 root = delete(root, data);
	 }
	 
	 /// FLOOR: find x <= K, nhỏ hơn hoặc bằng K ~ ưu tiên cao hơn
	 private Node floor(Node x, int data) {

	        if (x == null) return null;
	     
	        int cmp = Integer.compare(data, x.data);
	        
	        if (cmp < 0) return floor(x.left,data);
	        
	        if (cmp == 0) return x;
	        
	        Node temp  = floor(x.right,data);
	        return temp == null ? x : temp;
	    }
	 public int floor(int data){
		 Node x = floor(root, data);
		 return x == null ? null : x.data;
	 }
	 
	 // Ceiling: find x >= K (ưu tiên thấp hơn)
	 private Node ceiling(Node x, int data) {

	        if (x == null) return null;
	     
	        int cmp = Integer.compare(data, x.data);
	        
	        if (cmp > 0) return ceiling(x.right,data);
	        
	        if (cmp == 0) return x;
	        
	        Node temp  = ceiling(x.left,data);
	        return temp == null ? x : temp;
	    }
	 public int ceiling(int data){
		 Node x = ceiling(root, data);
		 return x == null ? null : x.data;
	 }
	 
	 // Kth smallest : tính từ 0 -> 5th ~ select(4)
	 private Node select(Node x, int Kth) {
	        if (x == null) return null;
	        int t = size(x.left); // số lượng < x ~ rankASC(x) in subtree x
	        if (t > Kth) return select(x.left, Kth);
	        else if (t < Kth) return select(x.right, Kth - t - 1);
	        else return x;
	    }
	 public int select(int Kth){
		 if (Kth < 0 || Kth >= size()) return -1;
			 
		 return select(root, Kth).data;
	 } 
	 public int selectDSC(int Kth){
		 int k = size() - (Kth+1);
		 if (k < 0 || k >= size()) return -1;
		 
		 return select(root,k).data;
	 }
	 // Rank(data) -> chính xác từ 1 -> N
	 public int rankDSC(int data){
	        return   size() + 1 - rankASC(data);
	        
	    }
	 public int rankASC(int data) {
	        return rankASC(root,data,0);
	        
	    }
	 private int rankASC(Node x, int data, int currentRank) {
		if(x==null) return currentRank;
			
		int cmp = Integer.compare(data, x.data);
		if(cmp>=0){
			 if(x.left == null) 
				 currentRank += 1;
			 else 	
				 currentRank += 1 + size(x.left);
			
			return rankASC(x.right,data,currentRank);
		}else
			return rankASC(x.left,data,currentRank);
	 }
	 
	 // tính từ 0 ->  cần chỉnh ở hàm public
	 private int rankASC1(Node x, int data) {
			if(x==null) return 0;
				
			int cmp = Integer.compare(data, x.data);
			
			if(cmp > 0) return 1 + size(x.left) + rankASC1(x.right,data);
			else if (cmp < 0) return rankASC1(x.left,data);
			else return size(x.left);
		 }
	 // Count number of element in range between 2 nodes include 2 nodes
	 public int sizeIN(int low, int high) {
		 // return contains(high)? rankASC(high) - rankASC(low) + 1 : rankASC(high) - rankASC(low);
		 return rankASC(high) - rankASC(low) + 1 ;
	    }
	 public static void main(String[] args) {
	        AVL avl  = new AVL();
	        avl.insert(100);
	        avl.insert(200);
	        avl.insert(300);
	        avl.insert(820);
	        avl.insert(510);
	        avl.insert(282);
	        avl.insert(150);
	        avl.insert(182);
	        //avl.delete(300);
//	        for(int i = 0; i< avl.size();i++ ) // từ 1 -> N
//	        	System.out.println(avl.selectDSC(i));
//	        System.out.println();
//	        for(int i = 0; i< avl.size();i++ ) // từ 1 -> N
//	        	System.out.println(avl.select(i));
//	        System.out.println(avl.rankDSC(100));
//	        System.out.println(avl.rankDSC(150));
//	        System.out.println(avl.rankDSC(182));
//	        System.out.println(avl.rankDSC(200));
//	        System.out.println(avl.rankDSC(282));
//	        System.out.println(avl.rankDSC(300));
//	        System.out.println(avl.rankDSC(510));
	        System.out.println(avl.sizeIN(100,800));
	        System.out.println(avl.sizeIN(100,820));
	       
	        //System.out.println(avl.root.data);
	    }
}