Week 7

Question 1

What is a self balancing binary search trees ?

Answer 1

*A self balancing BST is one that automatically keeps its height, as small as possible, at all times
*Rotations are preformed on the tree, at key times, to reduce the height
*A rotation will changes the structure of the tree without changing the order of the elements

Question 2

Tree Rotation

Answer 2

*Is used to change the structure of the BST without changing the order of the elements

Question 3

AVL Trees

Answer 3

An AVL tree is a binary search tree in which:
*Heights of the left and right subtrees of the root node differ by at most one
*Left and right subtrees are again AVL trees - a recursive definition

Question 4

Balance Factors

Answer 4

*Each node of an AVL tree contains an additional variable called the balance factor
*Balance factor of a node is the height of its left subtree minus the height of its right subtree
*Balance factor +1, 0, or -1 is considered balanced
*Balance factor +2 or -2 is considered unbalanced and with require the tree to be rebalanced using a rotation

Question 5

Creating an AVL Tree

Answer 5

*AVL tree is created as the data items are inserted
*Initially tree is empty - satisfies rules for an AVL tree
*Data items are inserted into the AVL tree using the normal rules for insertion into a BST
*Balance factor of each node on the path from the point of insertion to the root may change
*Nodes with a balance factor ±1 may be changed to ±2. *Unbalanced nodes will have a balance factor of ±2 and the tree is unbalanced
*Unbalanced trees must be rebalanced, using a rotation
*Rotation will take place around the unbalanced node which is nearest to the inserted node

Question 6

Rotations for AVL Trees

Answer 6

Single Rotations
*Left-Left Rotation(LL)
*Right-Right Rotation(RR)
Double Rotations
*Left-Right Rotation(LR)
*Right-Left Rotation(RL)
*Rotations take place around the unbalanced node with a balance factor of ±2