CS 130A (Fall 2020) Programming Assignment 3
1 Project Description
AVL tree is a self balancing Binary Search Tree where the height of the two child subtrees at any node can differ by at most one. In this project, you will implement a variant of AVL tree, referred as k-AVL tree. In k-AVL tree, the height of the two child subtrees can differ by at most k, where k ¡Ý 1. k = 1 refers to the traditional AVL tree. The implementation approach for k-AVL tree will be very similar to that of AVL tree. One key difference is, you will need to re-balance a node when the height difference of its children exceeds k.
2 Specification
Each node of your k-AVL tree will contain customized form of a non-negative single digit precision decimal value. A decimal value has two parts: i) whole part ii) fraction. In this project, each decimal number to be stored in a node will be represented as a tuple (wholepart,fraction). The fraction will contain exactly one digit . The whole part can contain one or more digits but will be less than maximum value of a 32 bit integer. Either of the whole part and fraction can have the value 0. However, there will be no leading zero for a non-zero whole part value. For example the numbers 3.2, 5.0, and 1234.5 can be represented as (3, 2), (5, 0), and (1234, 5) respectively. Please note that, you must follow this format to store the numbers in tree nodes for this project. Storing the numbers as float or double will not be acceptable. (Hint: Use two integers) The value of k will be passed as an input to the program. Figure 1 demonstrates an instance of k-AVL tree where the value of k is 2.
Figure 1: A k-AVL Tree with k = 2
The k-AVL tree class in your implementation needs to have the following functions:
1
1. Constructor: Takes k as parameter and constructs an empty k-AVL tree. 2. Insert: Insert a value into the k-AVL tree.
3. Delete: Delete a value from the k-AVL tree.
4. Search: Search a value in the k-AVL tree.
5. Approximate Search: Find the closest value in the k-AVL tree.
6. In Order Print: Print the tree according to an in-order traversal 7. Pre Order Print: Print the tree according to a pre-order traversal. 8. Destructor: Clean up memory.
The project needs to be implemented in C++ and uploaded to Gradescope¡¯s ¡°Project 3¡± assign- ment. It will be graded using autograder, so be very precise about the input and output formats discussed later. Your submission should contain source files along with a makefile. The name of the makefile should start with a lower case ¡®m¡¯. The name of the executable generated by makefile must be ¡°project3.out¡±. Please note that it is possible that your program could have some unex- pected behavior on Gradescope¡¯s autograder compared to whatever machine you wrote the code on, so submit your program early and make sure it is bug free on Gradescope. Please note that, the submissions will be manually checked to verify k-AVL tree properties. Gradescope score will be manually overridden if any inconsistency is found.
3 Input and Output
Gradescope will pass a single input string via argv[1] (similar to project 1). The string will begin with the value of k followed by a comma. Then there will be a number of commands separated by a comma.
The input output format for each functionality is as followed:
1. Search a value: The search command will be followed by two integers a and b where b will always be of single digit. If the tuple (a,b) is present in the k-AVL tree, it should print ¡°a.b found¡±. Otherwise it should print ¡°a.b not found¡±. For both cases, the output string should end with a newline.
Example: Consider the tree in Figure 1:
search 4 5 4.5 found
search 11 0 11.0 not found
2. Approximate Search: The approx search command will be followed by two integers a and b where b will always be of single digit. This function should find out the closest value to a.b that is present in the k-AVL tree. If a.b itself is present in the tree, then it should be the closest value. Otherwise, it should consider the value with smallest absolute difference as the closest value. If there are more than one values having the same absolute difference, the smallest of them should be considered. You should print nothing if the tree is empty while approx search is called. The output string should end with a newline.
Example: Consider the tree in Figure 1:
approx search 12 3 closest to 12.3 is 12.3
2
approx search 1 7 closest to 1.7 is 1.8
approx search 4 3 closest to 4.3 is 4.2
3. Insert: The insert command will be followed by two integers a and b where b will always be of single digit. If the value is already present, print nothing. Otherwise, insert the node (a, b) into the tree and print ¡°a.b inserted¡±. You have to do the necessary operations required to maintain the integrity of k-AVL tree. The output string should end with a newline.
Example: insert 9 3 9.3 inserted
4. Delete: The delete command will be followed by two integers a and b where b will always be of single digit. If a.b is not present in the tree, print nothing. Otherwise, delete the corresponding node from the tree and print ¡°a.b deleted¡±. Please note that, while deleting an internal node, this project requires you to replace the internal node with its in-order predecessor first and then delete the predecessor. You must maintain the integrity of k-AVL tree. The output string should end with a newline.
Example: Consider the tree in Figure 1: delete 4 2
4.2 deleted
5. In order print: The command used for this is in order. You should traverse the entire k- AVL tree in an in-order manner and print each node in a.b format followed by a space. There should be no space after the last value. The output string should end with a newline. If the tree is empty, print nothing (do not print an empty line).
Example: Consider the tree in Figure 1:
in order
1.8 3.5 4.2 4.4 4.5 12.3
6. Pre order print: The command used for this is pre order. You should traverse the entire k-AVL tree in a pre-order manner and print each node in a.b format followed by a space. There should be no space after the last value. The output string should end with a newline. If the tree is empty, print nothing (do not print an empty line).
Example: Consider the tree in Figure 1:
pre order
3.5 1.8 4.5 4.2 4.4 12.3
For example, you should be able to run your program by entering the following command in your terminal:
./project3.out “2, insert 2 2, insert 5 2, search 2 2, approx_search 5 1,
in_order, pre_order, delete 2 2”
3