psa

Assignment 1…

AVL Trees

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?

• when we perform a rotation, what changes?
  • what pointers change?
  • which nodes have a different height after the rotation?

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.

rotations and insertion

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:

• left-left