programming-language/AVLTree.java at main · praggCode/programming-language · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
packageBinaryTrees;

publicclassAVL {
intcount = 5;
publicclassNode{
privateintval;
privateintheight;
Nodeleft;
Noderight;
publicNode(intval){
this.val = val;
 }
publicintgetVal(){
returnval;
 }
 }
publicNoderoot;
publicintheight(Nodenode){
if(node==null){
return -1;
 }
returnnode.height;
 }
publicbooleanisEmpty(){
returnroot==null;
 }
publicvoidinsert(intval){
root = insert(root,val);
 }
publicNodeinsert(Nodenode,intval){
if(node==null){
node = newNode(val);
returnnode;
 }
if(node.val>val){
node.left = insert(node.left,val);
 }
if(node.val<val) {
node.right = insert(node.right, val);
 }
node.height = Math.max(height(node.left),height(node.right))+1;
returnrotate(node);
 }
privateNoderotate(Nodenode){
if(height(node.left)-height(node.right)>1){
//left heavy
if(height(node.left.left)-height(node.left.right)>0){
returnrightRotate(node);
 }
if(height(node.left.left)-height(node.left.right)<0){
node.left = leftRotate(node.left);
returnrightRotate(node);
 }
 }
if((height(node.left) - height(node.right)) < -1){
//right heavy
if(height(node.right.left)-height(node.right.right)<0){
returnleftRotate(node);
 }
if(height(node.right.left)-height(node.right.right)>0){
node.right = rightRotate(node.right);
returnleftRotate(node);
 }
 }
returnnode;
 }
publicNoderightRotate(Nodep){
Nodec = p.left;
Nodet = c.right;
c.right = p;
p.left = t;

p.height = Math.max(height(p.left),height(p.right))+1;
c.height = Math.max(height(c.left),height(c.right))+1;

returnc;
 }
publicNodeleftRotate(Nodep){
Nodec = p.right;
Nodet = c.left;
c.left = p;
p.right = t;

p.height = Math.max(height(p.left),height(p.right))+1;
c.height = Math.max(height(c.left),height(c.right))+1;
returnc;
 }
publicvoiddisplay(){
display2D(root,0);
 }
publicvoiddisplay2D(Noderoot, intspace){
if(root==null){
return;
 }
space+=count;
display2D(root.right,space);
System.out.println();
for(inti=count;i<space;i++){
System.out.print(" ");
 }
System.out.println(root.val);
display2D(root.left,space);
 }
publicvoidpopulateSorted(int[] nums){
populateSorted(nums,0,nums.length);
 }
publicvoidpopulateSorted(int[] nums,ints,inte){
if(s>=e){
return ;
 }
intmid = (s+e)/2;
this.insert(nums[mid]);
populateSorted(nums,s,mid);
populateSorted(nums,mid+1,e);
 }
publicbooleanisBalanced(Nodenode){
if(node==null){
returntrue;
 }
returnMath.abs(height(node.left)-height(node.right))<=1 && isBalanced(node.left) && isBalanced(node.right);
 }
}