Untitled
unknown
plain_text
2 years ago
9.5 kB
9
Indexable
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);
}
}
Editor is loading...