Repository navigation
Expand file tree
/
Copy pathAVLTree.java
More file actions
169 lines (136 loc) · 4.27 KB
/
Copy pathAVLTree.java
File metadata and controls
169 lines (136 loc) · 4.27 KB
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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
/**
* AVL Tree Implementation
* A self-balancing Binary Search Tree (BST) where the difference of heights
* of left and right subtrees cannot be more than one for all nodes.
*/
public class AVLTree {
class Node {
int key, height;
Node left, right;
Node(int d) {
key = d;
height = 1;
}
}
Node root;
// Get height of the tree
int height(Node N) {
if (N == null)
return 0;
return N.height;
}
// Get balance factor of node N
int getBalance(Node N) {
if (N == null)
return 0;
return height(N.left) - height(N.right);
}
// Right rotate subtree rooted with y
Node rightRotate(Node y) {
Node x = y.left;
Node T2 = x.right;
x.right = y;
y.left = T2;
y.height = Math.max(height(y.left), height(y.right)) + 1;
x.height = Math.max(height(x.left), height(x.right)) + 1;
return x;
}
// Left rotate subtree rooted with x
Node leftRotate(Node x) {
Node y = x.right;
Node T2 = y.left;
y.left = x;
x.right = T2;
x.height = Math.max(height(x.left), height(x.right)) + 1;
y.height = Math.max(height(y.left), height(y.right)) + 1;
return y;
}
Node insert(Node node, int key) {
if (node == null)
return (new Node(key));
if (key < node.key)
node.left = insert(node.left, key);
else if (key > node.key)
node.right = insert(node.right, key);
else
return node;
node.height = 1 + Math.max(height(node.left), height(node.right));
int balance = getBalance(node);
// Left Left Case
if (balance > 1 && key < node.left.key)
return rightRotate(node);
// Right Right Case
if (balance < -1 && key > node.right.key)
return leftRotate(node);
// Left Right Case
if (balance > 1 && key > node.left.key) {
node.left = leftRotate(node.left);
return rightRotate(node);
}
// Right Left Case
if (balance < -1 && key < node.right.key) {
node.right = rightRotate(node.right);
return leftRotate(node);
}
return node;
}
public void insert(int key) {
root = insert(root, key);
}
// Inorder traversal of the tree
public void inorder() {
System.out.println("\nInorder traversal:");
inorderRec(root);
}
private void inorderRec(Node root) {
if (root != null) {
inorderRec(root.left);
System.out.print(root.key + " ");
inorderRec(root.right);
}
}
// Method to print level order traversal
public void printLevelOrder() {
System.out.println("\nLevel order traversal:");
int h = height(root);
for (int i = 1; i <= h; i++) {
printGivenLevel(root, i);
System.out.println();
}
}
private void printGivenLevel(Node root, int level) {
if (root == null)
return;
if (level == 1)
System.out.print(root.key + " ");
else if (level > 1) {
printGivenLevel(root.left, level - 1);
printGivenLevel(root.right, level - 1);
}
}
// Main method to test the AVL Tree implementation
public static void main(String[] args) {
AVLTree tree = new AVLTree();
/* Constructing tree given in the above figure */
tree.insert(10);
tree.insert(20);
tree.insert(30);
tree.insert(40);
tree.insert(50);
tree.insert(25);
System.out.println("AVL Tree created successfully!");
// Print different traversals
tree.inorder();
tree.printLevelOrder();
// Demonstrate tree balance
System.out.println("\nTree root: " + tree.root.key);
System.out.println("Root balance factor: " + tree.getBalance(tree.root));
// Additional insertions to show self-balancing
System.out.println("\nInserting more elements...");
tree.insert(5);
tree.insert(15);
// Print updated tree
tree.inorder();
tree.printLevelOrder();
}
}