AVL Trees

Question 1

what is an AVL tree

Answer 1

A binary search tree with the height balance property.

Adds an extra retracing step after altering the tree

Question 2

what is the height of an AVL tree

Answer 2

O(log n)

where n is the number of nodes

Question 3

what is retracing

Answer 3

travel up from an updated node and perform rotations if balance factor becomes left heavy (-2) or right heavy (2)

Question 4

describe a left heavy tree and the action that should be taken

Answer 4

A is left of B
bf(B) = -2, bf(A) = 0 -> left right
bf (B) = -2, bf(A) = -1 -> right

Question 5

describe a right heavy tree and the action that should be taken

Answer 5

A is right child of B
bf(B)=2, bf(A)=0 -> right left
bf(B)=2, bf(A)=1 -> left