Question

Prerequisite Knowledge

• Understand binary search tree structure
• Understand binary search tree operations
• Understand binary search tree worst case and best case time.

Learning Outcomes

• Describe AVL tree structure
• Trace and implement AVL tree operations
• Explain and prove AVL tree performance

Answer 1

A

/ \

B C

Any tree structure for which every node has at max 2 child nodes is called a binary tree. For instance, the one above.

However, if the binary tree is such that for any node the left sbi tree holds values that are lower than or equal to itself while the right subtree holds higher values only, it is called a binary search tree (BST).

In the example above, the tree would be a BST if the following were true,

B <= A < C

So, the following would be a BST

7

/ \

3 11

/ \ / \

1 5 9 13

Operations and runtime -

Imagine you were to perform a Search operation (say for number 9 above), you would do the following -

1. Starting from the root node (e.g., 7 above)

2. Check if node = search value

3. If true return true and end search

4. Else, if search value is greater than current node, select right child as new node and repeat from step 2

5. Else, if search value is less than current node, sel2ct left child as new node and repeat from step 2

6. If all nodes are visited and you still don't find the node return false and end search.

What do you observe! At every step the remaining number of steps is halved, as you only traverse towards a subtree.

However, imagine if the tree were skewed like this,

13

/ \

1

/ \

3

/ \

5

/ \

11

/ \

9

Would you still have half iterations? Of course not.

I hope this gives you a fair idea. Also, log (n) and n are pretty different ?