-
Notifications
You must be signed in to change notification settings - Fork 0
/
AVLTree.java
132 lines (122 loc) · 3.96 KB
/
AVLTree.java
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
package com.interview.tree;
/**
* Date 07/04/2014
* @author tusroy
*
* Video link - https://youtu.be/rbg7Qf8GkQ4
*
* Write a program to insert into an AVL tree.
*
* AVL tree is self balancing binary tree. Difference of height of left or right subtree
* cannot be greater than one.
*
* There are four different use cases to insert into AVL tree
* left left - needs ones right rotation
* left right - needs one left and one right rotation
* right left - needs one right and one left rotation
* right right - needs one left rotation
*
* Follow rotation rules to keep tree balanced.
*
* At every node we will also keep height of the tree so that we don't
* have to recalculate values again.
*
* Runtime complexity to insert into AVL tree is O(logn).
*
* References
* http://en.wikipedia.org/wiki/AVL_tree
* http://www.geeksforgeeks.org/avl-tree-set-1-insertion/
*
*/
public class AVLTree {
private Node leftRotate(Node root){
Node newRoot = root.right;
root.right = root.right.left;
newRoot.left = root;
root.height = setHeight(root);
root.size = setSize(root);
newRoot.height = setHeight(newRoot);
newRoot.size = setSize(newRoot);
return newRoot;
}
private Node rightRotate(Node root){
Node newRoot = root.left;
root.left = root.left.right;
newRoot.right = root;
root.height = setHeight(root);
root.size = setSize(root);
newRoot.height = setHeight(newRoot);
newRoot.size = setSize(newRoot);
return newRoot;
}
private int setHeight(Node root){
if(root == null){
return 0;
}
return 1 + Math.max((root.left != null ? root.left.height : 0), (root.right != null ? root.right.height : 0));
}
private int height(Node root){
if(root == null){
return 0;
}else {
return root.height;
}
}
private int setSize(Node root){
if(root == null){
return 0;
}
return 1 + Math.max((root.left != null ? root.left.size : 0), (root.right != null ? root.right.size : 0));
}
public Node insert(Node root, int data){
if(root == null){
return Node.newNode(data);
}
if(root.data <= data){
root.right = insert(root.right,data);
}
else{
root.left = insert(root.left,data);
}
int balance = balance(root.left, root.right);
if(balance > 1){
if(height(root.left.left) >= height(root.left.right)){
root = rightRotate(root);
}else{
root.left = leftRotate(root.left);
root = rightRotate(root);
}
}else if(balance < -1){
if(height(root.right.right) >= height(root.right.left)){
root = leftRotate(root);
}else{
root.right = rightRotate(root.right);
root = leftRotate(root);
}
}
else{
root.height = setHeight(root);
root.size = setSize(root);
}
return root;
}
private int balance(Node rootLeft, Node rootRight){
return height(rootLeft) - height(rootRight);
}
public static void main(String args[]){
AVLTree avlTree = new AVLTree();
Node root = null;
root = avlTree.insert(root, -10);
root = avlTree.insert(root, 2);
root = avlTree.insert(root, 13);
root = avlTree.insert(root, -13);
root = avlTree.insert(root, -15);
root = avlTree.insert(root, 15);
root = avlTree.insert(root, 17);
root = avlTree.insert(root, 20);
TreeTraversals tt = new TreeTraversals();
tt.inOrder(root);
System.out.println();
tt.preOrder(root);
}
}