首页 >
> 详细

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” assignment. 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 unexpected 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 kAVL 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"

联系我们

- QQ：99515681
- 邮箱：99515681@qq.com
- 工作时间：8:00-23:00
- 微信：codinghelp2

- Cs2461-10实验程序代做、代写java，C/C++，Python编程设 2021-03-02
- 代写program程序语言、代做python，C++课程程序、代写java编 2021-03-02
- Programming课程代做、代写c++程序语言、Algorithms编程 2021-03-02
- 代写csc1-Ua程序、代做java编程设计、Java实验编程代做 代做留学 2021-03-02
- 代做program编程语言、代写python程序、代做python设计编程 2021-03-02
- 代写data编程设计、代做python语言程序、Python课程编程代写 代 2021-03-02
- Cse 13S程序实验代做、代写c++编程、C/C++程序语言调试 代写留学 2021-03-02
- Mat136h5编程代做、C/C++程序调试、Python，Java编程设计 2021-03-01
- 代写ee425x实验编程、代做python，C++，Java程序设计 帮做c 2021-03-01
- Cscc11程序课程代做、代写python程序设计、Python编程调试 代 2021-03-01
- 代写program编程、Python语言程序调试、Python编程设计代写 2021-03-01
- 代做r语言编程|代做database|代做留学生p... 2021-03-01
- Data Structures代写、代做r编程课程、代做r程序实验 帮做ha 2021-03-01
- 代做data留学生编程、C++，Python语言代写、Java程序代做 代写 2021-03-01
- 代写aps 105编程实验、C/C++程序语言代做 代写r语言程序|代写py 2021-03-01
- Fre6831 Computational Finance 2021-02-28
- Sta141b Assignment 5 Interactive Visu... 2021-02-28
- Eecs2011a-F20 2021-02-28
- Comp-251 Final Asssessment 2021-02-28
- 代写cs1027课程程序、代做java编程语言、代写java留学生编程帮做h 2021-02-28