I wrote an article about Binary Search Trees a few weeks ago. AVL trees are a specialization of Binary Search Trees.
AVL trees (named after their inventors, Adelson-Velskii and Landis) were the first kind of self-balancing tree to be invented, so their implementation is somewhat simple compared to newer self-balancing trees.
This type of tree allows you to perform insertions, deletions and searches in O(log n). This tree keeps track of the heights of all the nodes. Every time one node is inserted or deleted, the balancing factor (difference between the heights of left and right subtree) of its ancestors is checked. If the balancing factor is greater than 1 or lower than -1, then the tree is rebalanced.
Search
Searching in an AVL tree works exactly the same as searching in a regular BST.
Balancing
Before jumping into insertion and deletion we need to explore balancing the tree. If at any moment the balance factor becomes greater than 1 or lower than -1, then we need to rebalance. Let’s look at an example:
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
Start with:
5 | Height of 5 is 2
/ \ | Height of 4 is 1
4 6 | Height of 6 is 1
| Balance factor of 5 is 0
Insert 3:
5 | Height of 5 is 3
/ \ | Height of 4 is 2
4 6 | Height of 6 is 1
/ | Height of 3 is 1
3 | Balance factor of 5 is 1
Insert 2:
5 | Height of 5 is 4
/ \ | Height of 4 is 3
4 6 | Height of 6 is 1
/ | Height of 3 is 2
3 | Height of 2 is 1
/ | Balance factor of 5 is 2. Rebalancing is needed.
2
After rebalancing:
4
/ \
3 5
/ \
2 6
Now that we roughly know when to rebalance a tree, we need to look at how to do it.
When a tree becomes unbalanced, it has to be balanced by performing what is called a rotation. There are four different rotations that we can use to balance a tree. I’ll use examples with only three nodes for simplicity, but the examples can be generalized. More specifically, once you find the node where the rotation needs to be made, you can make the rotation and disregard the sub-trees of the nodes below.
LL - Left-Left
An LL rotation is necessary when we have a tree that is too heavy on the right:
1
2
3
4
5
4
\
5
\
6
For the example above, we can imagine that we started by inserting 4, then 5 and finally 6. After the rotation we end with this:
1
2
3
5
/ \
4 6
The steps we followed to get there are:
- 4’s parent needs to point to 5 now
- 4 becomes 5’s left child
- 5’s left child, becomes 4’s right child
Those are all the changes needed. Everything else stays the same. Let’s add some markers to make this clearer:
This:
1
2
3
4
5
6
7
P
|
4
\
5
/ \
L 6
Becomes this:
1
2
3
4
5
6
7
P
|
5
/ \
4 6
\
L
RR - Right-Right
This is a mirror of LL:
This:
1
2
3
4
5
6
7
P
|
6
/
5
/ \
4 R
Becomes this:
1
2
3
4
5
6
7
P
|
5
/ \
4 6
/
R
The steps we followed are:
- 6’s parent to point to 5 now
- 6 becomes 5’s right child
- 5’s right child, becomes 6’s left child
LR - Left-Right
This is where things get a little more interesting. In some situations a single rotation is not enough:
1
2
3
4
5
4
\
6
/
5
We could try an LL, but that doesn’t really solve anything:
1
2
3
4
5
6
/
4
\
5
The way we solve this is by doing a right rotation on the right sub-tree:
This is where we started:
1
2
3
4
5
4
\
6
/
5
This is the right sub-tree of 4:
1
2
3
6
/
5
After right rotating, this is the tree we get:
1
2
3
5
\
6
And the whole thing looks like this now:
1
2
3
4
5
4
\
5
\
6
From here we can do our left rotation, and we’ll have a balanced tree.
RL - Right-Left
This is a mirror or LR. The process looks something like this:
This would be the starting point:
1
2
3
4
5
6
/
4
\
5
This is the left sub-tree of 6:
1
2
3
4
\
5
After left rotating this tree we get:
1
2
3
5
/
4
And the whole thing looks like this:
1
2
3
4
5
6
/
5
/
4
Balance factor
In order to decide when to rotate we need ot figure out the balance factors of the nodes. The formula to calculate the balance factor is:
1
balance factor = height of left subtree - height of right subtree
Calculating the heights of the sub-trees of the root node would require us to traverse the whole tree, which would be very inefficient. For this reason a better approach is to store and update the height of the nodes every time it is needed.
In the Binary Search Trees article we have a _createNode function. Let’s extend it so it includes the height:
1
2
3
4
5
6
7
8
9
_createNode(val, parent = null) {
return {
val: val,
parent: parent,
left: null,
right: null,
height: 1
}
}
This way, every time a node is inserted or deleted we don’t have to calculate all heights, since they will be stored with the node itself
Inserting
Let’s look at an example of an insertion. Let’s say we have this tree:
1
2
3
5
/ \
4 6
If we insert a 7 here, we end with this:
1
2
3
4
5
5
/ \
4 6
\
7
Besides doing the insertion of the new node, we also need to update the heights and rebalance the tree if necessary. The algorigthm goes like this:
Steps to insert 7:
- Search where 7 will be inserted (In this case, as the right child of 6)
- Create a new node (
_createNode(7, parentNode)) - Set 6’s right node to the new node (parentNode.right = newNode)
- Update 6, and all its ancesters’ heights if necessary
- Rebalance 6 and all its ancesters if necessary
Deleting
Deleting a node follows the same steps as with a normal Binary Search Tree. You can check my Binary Search Trees article for the instructions. The only difference is that heights of the ancestors of the deleted node might need to be updated, and they might need to be rebalanced.
Code
This code is an extension of the code from my Binary Search Trees article. If there are parts that are not clear, you might want to check it.
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
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
class AvlTree {
// Create a node
_createNode(val, parent = null) {
return {
val: val,
parent: parent,
left: null,
right: null,
height: 1
}
}
// Perform a left rotation on the given node
_leftRotate(node) {
const nodeRight = node.right;
if (node.parent) {
if (node.parent.left === node) {
node.parent.left = nodeRight;
} else if (node.parent.right === node) {
node.parent.right = nodeRight;
} else {
console.error('There was an error rotating:');
console.log(node);
}
}
nodeRight.parent = node.parent;
node.right = nodeRight.left;
if (nodeRight.left) {
nodeRight.left.parent = node.right;
}
nodeRight.left = node;
node.parent = nodeRight;
// Update the heights
let rh = node.right ? node.right.height : 0;
let lh = node.left ? node.left.height : 0;
node.height = Math.max(rh, lh) + 1;
let rrh = nodeRight.right ? nodeRight.right.height : 0;
let rlh = nodeRight.left ? nodeRight.left.height : 0;
nodeRight.height = Math.max(rrh, rlh) + 1;
}
// Perform a right rotation on the given node
_rightRotate(node) {
const nodeLeft = node.left;
if (node.parent) {
if (node.parent.left === node) {
node.parent.left = nodeLeft;
} else if (node.parent.right === node) {
node.parent.right = nodeLeft;
} else {
console.error('There was an error rotating ' + node);
}
}
nodeLeft.parent = node.parent;
node.left = nodeLeft.right;
if (nodeLeft.right) {
nodeLeft.right.parent = node.left;
}
nodeLeft.right = node;
node.parent = nodeLeft;
// Update the heights
let rh = node.right ? node.right.height : 0;
let lh = node.left ? node.left.height : 0;
node.height = Math.max(rh, lh) + 1;
let lrh = nodeLeft.right ? nodeLeft.right.height : 0;
let llh = nodeLeft.left ? nodeLeft.left.height : 0;
nodeLeft.height = Math.max(lrh, llh) + 1;
}
// Search for a value in this tree. If not found, returns
// the closest node (the node where the value would be
// inserted)
_findPosition(val) {
let current = this._root;
while (true) {
if (current.val === val) {
return current;
}
if (val > current.val && current.right) {
// The value we are searching for is greater.
// Continue on the right subtree
current = current.right;
} else if (val < current.val && current.left) {
// The value we are searching for is lower.
// Continue on the left subtree
current = current.left;
} else {
// No more tree to traverse
return current;
}
}
}
// Updates heights of the node and all its ancesters, based on the
// height of its children
_updateHeights(node) {
for (let current = node; current; current = current.parent) {
let rh = current.right ? current.right.height : 0;
let lh = current.left ? current.left.height : 0;
current.height = Math.max(rh, lh) + 1;
}
}
// Balances the tree if necessary. Updates the _root accordingly
_balance(node) {
let current = node;
let last = current;
while (current) {
let leftHeight = current.left ? current.left.height : 0;
let rightHeight = current.right ? current.right.height : 0;
let factor = leftHeight - rightHeight;
// LL or LR needed
if (factor < -1) {
let currentRight = current.right;
let lh = currentRight.left ? currentRight.left.height : 0;
let rh = currentRight.right ? currentRight.right.height : 0;
let diff = lh - rh;
if (diff === 1) {
// LR
this._rightRotate(current.right);
this._leftRotate(current);
} else {
// LL
this._leftRotate(current);
}
}
// RR or RL needed
if (factor > 1) {
let currentLeft = current.left;
let lh = currentLeft.left ? currentLeft.left.height : 0;
let rh = currentLeft.right ? currentLeft.right.height : 0;
let diff = lh - rh;
if (diff === -1) {
// RL
this._leftRotate(current.left);
this._rightRotate(current);
} else {
// RR
this._rightRotate(current);
}
}
last = current;
current = current.parent;
}
this._root = last;
}
// Deletes the given node. The node must have at most
// one child
_deleteSimple(node) {
if (!node.left && !node.right) {
// No children, simple delete
if (!node.parent) {
this._root = null;
} else if (node.parent.right == node) {
node.parent.right = null;
} else {
node.parent.left = null;
}
} else {
// Single child, link the child to the parent
if (!node.parent) {
if (node.left) {
this._root = node.left;
node.left.parent = node.parent;
} else {
this._root = node.right;
node.right.parent = node.parent;
}
} else if (node.parent.right == node) {
if (node.left) {
node.left.parent = node.parent;
node.parent.right = node.left;
} else {
node.right.parent = node.parent;
node.parent.right = node.right;
}
} else {
if (node.left) {
node.left.parent = node.parent;
node.parent.left = node.left;
} else {
node.right.parent = node.parent;
node.parent.left = node.right;
}
}
}
}
// Search for a value in this tree
search(val) {
const found = this._findPosition(val);
if (found && found.val === val) {
return found;
}
}
// insert a value
insert(val) {
// The case where this is the first value
if (!this._root) {
this._root = this._createNode(val);
return;
}
// Search for the value. If it is found we don't need
// to do anything
let position = this._findPosition(val);
if (position.val === val) {
return;
}
// Insert the new value in the tree
if (position.val > val) {
position.left = this._createNode(val, position);
} else {
position.right = this._createNode(val, position);
}
// For an AVL tree we need to update the heights and balance
this._updateHeights(position);
this._balance(position);
}
// Delete a value from the tree
delete(val) {
// Search for the value. If it is not found we don't
// need to do anything
let node = this.search(val);
if (!node) {
return;
}
let deleteParent = null;
if (node.left && node.right) {
// Node has two children
let lowestRightNode = node.right;
while (lowestRightNode.left) {
lowestRightNode = lowestRightNode.left;
}
let tempVal = lowestRightNode.val;
lowestRightNode.val = node.val;
node.val = tempVal;
this._deleteSimple(lowestRightNode);
deleteParent = lowestRightNode.parent;
} else {
this._deleteSimple(node);
deleteParent = node.parent;
}
// For an AVL tree we need to update the heights and balance
this._updateHeights(deleteParent);
this._balance(deleteParent);
}
}
// Create an AVL tree
let avl = new AvlTree();
// Test insertions and balancing:
avl.insert(1);
avl.insert(2);
avl.insert(3);
avl.insert(4);
avl.insert(5);
avl.insert(6);
// Test deletions and balancing:
avl.delete(6);
avl.delete(5);
console.log(avl._root);
programming javascript computer_science algorithms