Binary Search Trees (BST) Exercises

1. Draw the resulting BST after inserting the following strings (in the order provided) into an empty BST:
   

   BS,  AVL,  TT,   TTF,   RB,  Splay

2. Draw the resulting BST after inserting the following strings (in the order provided) into an empty BST:
   

   Splay,  BS,  RB,   AVL,  TT,   TTF

   Now insert

   TT

   into the existing BST. What considerations are there?
3. Draw the resulting BST after inserting the following strings (in the order provided) into an empty BST:
   

   AVL,  BS,   RB,  Splay,  TT,   TTF

4. Given the following BST, draw the resulting tree after removing A.
   Then, draw the tree after removing C.
   
5. Given the following BST, draw the resulting tree after removing B.
   Then, draw the tree after removing E.
   
6. Write in the Big-Oh for the following operations on a BST.

   	Average-case	Worst-case
   Retrieval
   Insertion
   Deletion
   Traversal

Last Modified: