|
| 1 | +public class AVLTree { |
| 2 | +private class Node{ |
| 3 | +int data; |
| 4 | +int height; |
| 5 | +Node left; |
| 6 | +Node right; |
| 7 | +Node(int data){ |
| 8 | +this.data=data; |
| 9 | +this.height=1; |
| 10 | +} |
| 11 | + |
| 12 | +} |
| 13 | +private Node root; |
| 14 | +public void insert(int data) { |
| 15 | +this.root=insert(this.root,data); |
| 16 | +} |
| 17 | +private Node insert(Node node,int item) { |
| 18 | +if(node==null) { |
| 19 | +Node add=new Node(item); |
| 20 | +return add; |
| 21 | +} |
| 22 | +if(node.data>item) { |
| 23 | +node.left=insert(node.left,item); |
| 24 | +} |
| 25 | +if(node.data<item) { |
| 26 | +node.right=insert(node.right,item); |
| 27 | +} |
| 28 | +node.height=Math.max(height(node.left),height(node.right))+1; |
| 29 | +int bf=bf(node); |
| 30 | +//LL case |
| 31 | +if(bf>1&&item<node.left.data) |
| 32 | +return rightRotate(node); |
| 33 | +//RR case |
| 34 | +if(bf<-1&&item>node.right.data) |
| 35 | +return leftRotate(node); |
| 36 | +//RL case |
| 37 | +if(bf<-1&&item<node.right.data) { |
| 38 | +node.right=rightRotate(node.right); |
| 39 | +return leftRotate(node); |
| 40 | +} |
| 41 | +//LR case |
| 42 | +if(bf>1&&item>node.left.data) { |
| 43 | +node.left=leftRotate(node.left); |
| 44 | +return rightRotate(node); |
| 45 | +} |
| 46 | + |
| 47 | +return node; |
| 48 | +} |
| 49 | +public void display() { |
| 50 | +this.display(this.root); |
| 51 | +System.out.println(this.root.height); |
| 52 | +} |
| 53 | +private void display (Node node) { |
| 54 | +String str=""; |
| 55 | +if(node.left!=null) |
| 56 | +str+=node.left.data+"=>"; |
| 57 | +else |
| 58 | +str+="END=>"; |
| 59 | +str+=node.data+""; |
| 60 | +if(node.right!=null) |
| 61 | +str+="<="+node.right.data; |
| 62 | +else |
| 63 | +str+="<=END"; |
| 64 | +System.out.println(str); |
| 65 | +if(node.left!=null) |
| 66 | +display(node.left); |
| 67 | +if(node.right!=null) |
| 68 | +display(node.right); |
| 69 | +} |
| 70 | +private int height(Node node) { |
| 71 | +if(node==null) { |
| 72 | +return 0; |
| 73 | +} |
| 74 | +return node.height; |
| 75 | + |
| 76 | +} |
| 77 | +private int bf(Node node) { |
| 78 | +if(node==null) |
| 79 | +return 0; |
| 80 | +return height(node.left)-height(node.right); |
| 81 | +} |
| 82 | + |
| 83 | +private Node rightRotate(Node c) { |
| 84 | +Node b=c.left; |
| 85 | +Node T3=b.right; |
| 86 | + |
| 87 | +b.right=c; |
| 88 | +c.left=T3; |
| 89 | +c.height=Math.max(height(c.left),height(c.right))+1; |
| 90 | +b.height=Math.max(height(b.left),height(b.right))+1; |
| 91 | +return b; |
| 92 | + |
| 93 | +} |
| 94 | +private Node leftRotate(Node c) { |
| 95 | +Node b=c.right; |
| 96 | +Node T3=b.left; |
| 97 | + |
| 98 | +b.left=c; |
| 99 | +c.right=T3; |
| 100 | +c.height=Math.max(height(c.left),height(c.right))+1; |
| 101 | +b.height=Math.max(height(b.left),height(b.right))+1; |
| 102 | +return b; |
| 103 | + |
| 104 | +} |
| 105 | + |
| 106 | +} |