Tree & Hash Table & Heap
Use the following integer keys 73, 58, 91, 42, 60, 130, 64, 87 to perform the followings:
a) Binary Search Tree
- Draw a binary search tree
- Retrieve the integers keys in post-order
- Retrieve the integers keys in pre-order
- Draw a binary search tree after node 58 is deleted
b) Create a Hash Table using the methods described
below. Show the final array after all integer keys are inserted.
Assumes that the Hash Table is implemented using an array of size
13. The integer keys are
73, 58, 91, 42, 60, 130, 64, 87
Numbers |
|||||||||||||
Index |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
Numbers |
|||||||||||||
Index |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
Numbers |
|||||||||||||
Index |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
b) Insertion and deletion in a Heap. Show the final array after all insertion and deletion are finished.
Numbers |
|||||||||||||
Index |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
Draw a binary tree from the heap array
Heap (Remove)
Numbers |
|||||||||||||
Index |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
Draw a binary tree from the heap array after the removal is performed
Tree & Hash Table & Heap Use the following integer keys 73, 58, 91, 42, 60,...
Tree & Hash Table & Heap Use the following integer keys 73, 58, 91, 42, 60, 130, 64, 87 to perform the followings: a) Binary Search Tree - Draw a binary search tree - Retrieve the integers keys in post-order - Retrieve the integers keys in pre-order - Draw a binary search tree after node 58 is deleted b) Create a Hash Table using the methods described below. Show the final array after all integer keys are inserted. Assumes that...
(g - 6 pts) Construct a hash table of the given array using a hash function H(K) = K mod 5. (h - 6 pts) For the hash table of (g), determine the average number of comparisons for a successful search and the worst case number of comparisons for an unsuccessful search. (i - 9 pts) Consider the elements of the array assigned to you are known only one at a time. Construct a sequence of priority queues (as max...
Assume data is to be stored in a hash table using the following keys: 62,77.26, 42, 52,76 Assume the hash table size is 7, the hash function used is the modulo function i.e. h/key) = key % table_size, and collisions are handled using linear probing. What's the content of the table after all keys are mapped to the hash table? (List keys starting from table index 0 and on Separate numbers by a comma and a single space, and indicate...
[Heap] Create a min-binary heap using following numbers (appearing/inserting in the given order): 5, 22, 19, 56, 50, 25, 1, 3, 10, 6, 32, 12, 11 [Hint: you can put the items in sequence in a binary tree and then use the buildHeap() method.] [Hashing] Consider a hash table where the hash function h is defined as the modulo 10 operation i.e., for any integer k, h(k) = k % 10 (the ‘modulo 10’ operator returns the remainder when k...
(c) Draw the binary heap structure that is equivalent to the following list (the root is first element). [5, 9, 8, 12, 15, 11, 19, 14, 20, 18, 17, 13] [4 marks] (d) Show the resulting tree after the value 6 is added to the heap in the part (c). Note that the binary heap properties must be restored after insertion. Show your working; you may show the data structure in tree or array form. [3 marks]
PROBLEM 6: Suppose we insert keys below into an initially empty binary search tree in the given order 6, 9, 2, 1, 5, 7, 10, 8, 3,4 (a) Draw the resulting binary search tree. (b) List the keys according to: A pre-order traversal An in-order traversal A post-order traversal (c) Now we perform some deletions using the "deletion by copying" strategy in which promoted keys are always drawn from a node's right subtree (so that there is only one correct...
PROBLEM 6: Suppose we insert keys below into an initially empty Vanilla binary search tree in the given order: 6, 9, 2, 1, 5, 7, 10, 8, 3, 4 (a) Draw the resulting binary search tree. (b) List the keys according to: A pre-order traversal An in-order traversal A post-order traversal (c) Now we perform some deletions using the “deletion by copying” strategy in which promoted keys are always drawn from a node’s right subtree (so that there is only...
3. (8 points) Using the implementation of binary search tree operations we discussed in class, draw the trees that result from the following operations: (a) Inserting 142, 400, 205, 127, 100, 320, 160, 141, and 110 into an initially-empty tree (in that order). (b) Deleting 142 from the tree you drew for part (a). 4. (8 points) Draw the unique binary tree that has a preorder traversal of 4, 1, 6, 3, 7, 5, 9, 2, 8 and an inorder...
Question 3. a. Draw the binary min heap represented by the following array: (5 points) 1 2 4 6 7 Value 4 9 12 29 17 14 16 b. Show the result of calling deleteMin twice on the heap you drew in part (a). Show the heap after each deleteMin, and circle the final heap. (5 points) c. Starting with the heap you ended up with in part (b), insert values 11 & 2 in that order. Draw the heap...
NOTE: Completing the Third Chart is the most important. This is one question with three parts. (4 pts) Is the following array-based tree a min-heap or a max-heap or not a heap at all? 85 91 S8 95 100 92 a. Min-heap b. Max-heap c. Not a heap 5 pts) Turn the following array-based binary tree into a max-heap. Show your work step by step. (You will not need all the columns) 34 7 12 47 19 5 pts) Show...