Ternary Search Tree (TST)
This project is a programming assignment in C which aims to write an algorithm that will build a ternary search tree (TST) and makes necessary operations in this tree.
(40 points) Consider a TST where the only difference with a binary search tree is that a key that is greater than the current node’s key but less than or equal to the square of it is located at the middle child of the node. More formally expressed,
Key(LCA) < Key(A) < Key(MCA) ≤ (Key(A))2 < Key(RCA)
where A represents the current node, LCA, MCA and RCA denote the left child, the middle child and the right child of A, in respective order.
Write a recursive insert function that inserts a list of keys given you as an input file in the above TST!
Hint: Both the node structure and the function should be very similar to that of the binary search tree in your lecture notes.
(40 points) Write a remove function that searches for a given key in the above TST given in (a) and remove it and finally re-build the TST!
(20 points) Write a recursive find function that searches for a given key in the above TST given in (a)!
(50 points- BONUS) In (a), (b) and (c) parts the formula is given and you are expected to do the necessary operations. This time, find a formula that makes the tree has a minimum depth level. Before starting implementation, studying mathematical proof of this question will be useful for you. After you decide the formula, implement the (a),
(b) and (c) parts.
1
The main goal of this project is to be familiar with Trees. So, if you use arrays/linked lists instead of Trees then you will get zero, unfortunately.
In this project you are expected to develop an algorithm that is capable of finding a solution to the above problem and implement this algorithm in ANSI C that runs under either UNIX or Windows.
You are responsible for demonstrating your program to your TA Berna Altinel on the scheduled day that will be announced later.
CODE SUBMISSION:
You should use the following email address in order to submit your code:
cse225.marmara.2018 at gmail dot com
Your any submission after the project submission due date, will not taken into consideration.
You are required to exhibit an individual effort on this project. Any potential violation of this rule will lead everyone involved to failing from the course and necessary disciplinary actions will be taken.
Good luck!!!
2
