remember, in a normal Binary Search Tree, whilst average case for insert / search / delete is $O(\log n)=O(h)$, we have worst-case $O(n)$ if the tree is really unbalanced (and $n \approx h$)
an AVL Tree is basically a binary search tree that also performs rotations upon Insert
and Delete
operations to keep the tree height balanced
Do we need to revise rotations?
struct AVLNode {
int value;
int height;
struct AVLNode *left;
struct AVLNode *right;
}
We usually define height of a leaf node = 0, and height of NULL (i.e., empty tree) = -1.
insertAVL(tree, item):
if tree is empty:
return new node containing item
else if item = data(tree):
return tree
if item < data(tree):
left(tree) = insertAVL(left(tree), item)
else if item > data(tree):
right(tree) = insertAVL(right(tree), item)
LHeight = height(left(tree))
RHeight = height(right(tree))
# update height of current node
if (LHeight - RHeight) > 1:
if item > data(left(tree)):
left(tree) = rotateLeft(left(tree))
tree = rotateRight(tree)
else if (RHeight - LHeight) > 1:
if item < data(right(tree)):
right(tree) = rotateRight(right(tree))
tree = rotateLeft(tree)
return tree
take note of the four types of rotations: