CS140 Homework 12

Suppose I want to create a searching application which supports the following three operations:
- insert a record into the search structure
- find a record in the search structure
- delete a record from the search structure
Further suppose that:
- the data is inserted almost in ascending order (i.e., the data is not completely ordered, but is close to being ordered).
- the number of insertions and deletions roughly equals the number of finds.
- ordered traversals and find min/find max operations are never required.
Which data structure would you choose to implement this search application? Justify your answer and be specific about which type of binary tree (balanced versus unbalanced), hash table (separate chaining versus open addressing), or linked list (singly-linked versus doubly-linked) you would use.

Show the hash table that results if the integers 22, 28, 17, 21, 32 are inserted into the following hash table using:

Linear probing, and
the hash function h(k) = k % 11

           -----------------------
      0    |                     |
	   |                     |
           -----------------------
      1	   |                     |
	   |                     |
           -----------------------
      2    |                     |
	   |                     |
           -----------------------
      3	   |                     |
	   |                     |
           -----------------------
      4	   |                     |
	   |                     |
           -----------------------
      5	   |                     |
	   |                     |
           -----------------------
      6	   |                     |
	   |                     |
           -----------------------
      7	   |                     |
	   |                     |
           -----------------------
      8	   |                     |
	   |                     |
           -----------------------
      9	   |                     |
	   |                     |
           -----------------------
     10	   |                     |
	   |                     |
           -----------------------

Show the hash table that results if the integers 22, 28, 17, 21, 32 are inserted into the following hash table using:

separate chaining, and
the hash function h(k) = k % 11

You should append integers to the end of your lists.

           -----------------------
      0    |                     |
	   |                     |
           -----------------------
      1	   |                     |
	   |                     |
           -----------------------
      2    |                     |
	   |                     |
           -----------------------
      3	   |                     |
	   |                     |
           -----------------------
      4	   |                     |
	   |                     |
           -----------------------
      5	   |                     |
	   |                     |
           -----------------------
      6	   |                     |
	   |                     |
           -----------------------
      7	   |                     |
	   |                     |
           -----------------------
      8	   |                     |
	   |                     |
           -----------------------
      9	   |                     |
	   |                     |
           -----------------------
     10	   |                     |
	   |                     |
           -----------------------

Show the binary search tree that results if the integers 22, 28, 17, 21, 32 are inserted into an initially empty tree.
Show the result of doing a single left rotation about the node 30. Do not worry if the rotation increases the height of the tree. All I care about is whether you know how to perform a rotation.
```
                          20
			/    \
		      10     30
		       \    /  \
		       15  25  35
```
Behold the following tree that violates the AVL condition:
```
                           ---100--
			  /        \
		       -50-        200
		      /    \          \
		    25     75        300
		          /  \
		         62  85
                            /
			   80
```
- Identify the bottom-most node that violates the AVL condition and explain why that node violates the AVL condition.
- In order to rebalance the tree do we have to use the zig-zig case or the zig-zag case? Justify your answer.
- Use the proper rotation(s) to rebalance the above tree so that it becomes a legitimate AVL tree.
Pretend that Dr. Plank's bstree library has been rewritten so that keys can be integers rather than char *'s. Everything else remains the same (i.e., function names, parameters, parameter types, etc). Write a function that reads integers from an inputstruct and inserts them into one of Dr. Plank's bstree's. For each integer store the line number associated with the integer. Do not worry about duplicate integers. Once all the integers have been read, print them in descending order, along with their line numbers. Do not worry about compiling or executing this function or about potential errors. Here is the function signature. You may assume that the inputstruct has already been created:
```
	void sort_integers(IS input_file);
	
```
If your input file is:
```
	23 18 17
	16 
	22 58
	
```
then your output would look like:
```
	58	3
	23	1
	22	3
	18	1
	17	1
	16	2
	
```