RS #3 -Binary Search Trees -Definitions -Vocabulary (root,child,height,etc) -Balance -Rules of insertion -AVL Trees -Definition -Rotations -Rules of Insertion -Bottom-up Approach -Adv/Disadv -Red-Black Trees -Definition -Rotations -Rules of insertion -Top-down Approach -Adv/Disadv Sample questions: Insert the following numbers into these trees Compare the balance of the following trees Is the following an AVL tree? Is the following a Red-Black tree? What is the significance of balanced trees? What is the worst case scenario for BST?