Due: 1st week after the winter vac ation (submission through moodle before sessional class)
Section B1:
Implement the following methods of a Red-Black tree:
Insert (insert a key value)
Lookup (search for a key va lue in the tree)
Delete (delete a key value from the tree)
Print (print all of the key values in ascending order)
N:B: 1) The worst case running tim e of all the methods should be O(log N), where N is the number of nodes in the tree.
2) Implementation must be done in C/C++
Example:
Suppose you have inserted the foll owing key values consecutively:
10, 20, 5, 3, 9, 15, 2 0, 12
Now, the Red-black tree would be as follows:
After the insertions of these key values, if you search for 20, then the Lookup function will return true. If you search for 16, it will return false.
Now, if you delete the key value 9, then after the deletion the tree would be as follow s:
For the Print function, the values w ill be printed in the sorted order.
Section A1/ A2/ B2:
Implement the following methods of a Red-Black tree:
Insert (insert a key value)
Lookup (search for a key va lue in the tree)
Delete (delete a key value from the tree)
Print (print all of the key values in ascending order)
Min (return the minimum k ey value of the tree)
Max (return the maximum key value of the tree)
N:B: 1) The worst case running tim e of all the methods should be O(log N), where N is the number of nodes in the tree.
2) Implementation must be done in C/C++
Example:
Suppose you have inserted the foll owing key values consecutively:
10, 20, 5, 3, 9, 15, 2 0, 12
Now, the Red-black tree would be as follows:
After the insertions of these key values, if you search for 20, then the Lookup function will return true. If you search for 16, it will return false.
Now, if you delete the key value 9, then after the deletion the tree would be as follow s:
For the Print function, the values w ill be printed in the sorted order.
