[Solved] CSE222-Homework 7

PART 1:

Provide two partial implementations of NavigableSet interface:

1. Implement following methods of NavigableSet interface using skip-list a. insert
   1. delete
   2. descendingIterator
2. Implement following methods of NavigableSet interface using AVL tree a. insert
   1. iterator
   2. headSet
   3. tailSet PART 2:

Write method that takes a BinarySearchTree and checks whether the tree is

1. an AVL tree
2. a Red-Black tree (Suppose BinarySearchTree has a method isRed which returns a boolean value which indicates whether the root node is a red node or not.)

PART 3:

Compare insertion performance of the following data structures.

• Binary search tree implementation in the book
• Red-Black tree implementation in the book
• 2-3 tree implementation in the book
• B-tree implementation in the book
• Skip list implementation in the book

For each data structure,

• Construct an instance of each data structure by inserting a collection of randomly generated (non-repeating) numbers. Perform this operation 10 times for 10.000, 20.000, 40.000 and 80.000 random numbers (10 times for each). So, you will have 10 instances for each data structure and each different size (i.e., 200 instances in total).
• Compare the experimental run-time performance of the insertion operation for the data structures above as follows:
  • Insert 100 extra random numbers into the structures you built and measure the running time
  • Calculate the average running time for each data structure and problem size (i.e., number of elements in data structure). o Draw a graph for running-time vs problem size.
  • Compare the running times and their increase rate.