1.(Lazy deletion)
There are (at least) two approaches to dealing with deletions from binary search trees. The first, as used in lectures, is to remove the tree node containing the deleted value and re-arrange the pointers within the tree. The second is to not remove nodes, but simply to mark them as being "deleted".
For this question, assume that we are going to re-implement Binary Search Trees so that they use mark-as-deleted rather than deleting any nodes. Under this scheme, no nodes are ever removed from the tree; instead, when a value is deleted, its node remains (and continues to retain the same value) but is marked so that it can be recognised as deleted.
To implement this idea of "lazy" deletion, consider the following modification to the BST data structure:
typedef struct Node {
bool deleted;
int data;
Tree left, right;
...
} Node;
a.Modify the search algorithm (week 7 lecture) for a "conventional" binary search tree to take into account deleted nodes.
b.One significant advantage of deletion-by-marking is that it makes the deletion operation simpler. All that deletion needs to do is search for a node containing the value to be deleted. If it finds such a node, it simply "marks" it as deleted. If it does not find such a node, the tree is unchanged.
Write a deletion algorithm that takes a BST t and a value v and returns a new tree with the node with value v marked as deleted.
c.Modify this week's Binary Search Tree ADT (BST.h, BST.c) from the lecture by an implementation of lazy deletion. Specifically, you should implement your answers to a. and b. by modifying
the data structure struct Node;
the functions newNode(it), TreeSearch(t,it), TreeDelete(t,it);
the function TreeInsert(t,it) so that if it is already in the tree but marked as deleted, then it gets "un-deleted."
Do not change BST.h.
You can test your program with the treeLab.c client from the lecture. An example of the program executing is shown below.
./treeLab
> i 20
New Tree: #nodes = 1, height = 0
20
> i 10
New Tree: #nodes = 2, height = 1
20
/
/
10
> s 10
Found!
> d 10
New Tree: #nodes = 2, height = 1
20
/
/
10
> s 10
Not found
> q
Bye.
As you can see, node 10 is still in the tree after deleting it, but TreeSearch() returns false when searching for this value after it has been marked as deleted.
We have created a script that can automatically test your program. To run this test you can execute the dryrun program that corresponds to this exercise. It expects to find the file named BST.c in the current directory with your implementation of lazy deletion.
You can use dryrun as follows:
9024 dryrun BST
2.(Red-black trees)
a.Show how a red-black tree would be constructed if the following values were inserted into an initially empty tree in the order given:
b.1 2 3 4 5 8 6 7 9 10
Once you have built the tree, compute the cost (#comparisons) of searching for each of the following values in the tree:
1 7 9 13
c.Implement the pseudocode for Red-Black Tree Insertion from the lecture (slides 70–74) in our Red-Black Tree ADT (RBTree.h, RBTree.c) as the function:
d.Tree TreeInsert(Tree t, Item it) { ... }
Note: Ensure that you implement the pseudocode from the lecture. Other algorithms will not score full marks for this exercise even if they also result in the correct insertion of the new element.
We have created a script that can automatically test your program. To run this test you can execute the dryrun program that corresponds to this exercise. It expects to find the file named RBTree.c in the current directory with your implementation of the function TreeInsert().
You can use dryrun as follows:
9024 dryrun RBTree