Due: Monday 6th of March at Noon
Hello All thanks for checking up on what is new. The LATEST tests are availible and you should get them.
You are to implement an AVL tree. See my sample program. To get any points you must turn in a project that compiles and runs.
Name your executable 'avl'.
Your output will have the following format for the tree describe below:
////////////////////////////////////////// // You don't ouput this fancy ascii tree // 2 // / \ // 1 3 ////////////////////////////////////////// 1 [null, null]--> 0 2 [1, 3]--> 0 ROOT 3 [null, null]--> 0 fields: 1 2 3 4 1 2 3 4 data [left pointer, right pointer]--> balance factor NOTE: the node that is the root of the tree should "ROOT" appended to its line of output. F%CK Fred and his damn changes!! Hold it just a minute. These are not that horrible. Making node 2 print out "ROOT" makes it easier to interpret the output. See that it's children are left:1, right:3. Notice that the children have null left and right pointers. So you know they are leaf nodes.
In addition to the ouput above have your rotate_left() and rotate_right() functions output the following messages respectively:
completed a rotateLeft() around 2 completed a rotateRight() around 5Where the numbers are the current node that had the imbalance to be corrected.
Your main.cpp will read in the commands from standard input.
============================================================================== NOTE:numbers you do not need to worry about negative numbers NOTE:assume all input will be formatted correctly '//....' comments. Yes put comments in your test inputs 'A' number 'D' number 'S' number 'P' 'I' 'R' **no 'B' ==============================================================================
You main.cpp will output to stdout. This way you can redirect your output to a file of your choosing.
The reason for this is that you can type commands to your program at the command prompt while it is running and see the output too. This should serve to speed debugging.
==============================================================
A INTERGER_KEY 'A' is for add.
==============================================================
You do not have to worry about checking the input. All input will be correctly formatted.
Add commands will always be:
'A'<space>number"\n"
You need to echo that a number was added to the tree:
"added data: 2"
"added data: "number
You need to output this message if the number being added is already in the tree:
"duplicate rejected: "2
That is:
"duplicate rejected: "number
==============================================================
D INTEGER_KEY 'D' is for delete.
Delete commands will always be:
'D'<space>number"\n"
When the number of a delete command is not in the tree output this message:
"delete failed: "<number>" is not in tree"
NOTE: Dr Stapleton's method for finding the in-order predecessor vs the in-order successor is required.
See test case tests/t39 and tests/t39.out
==============================================================
S INTEGER_KEY 'S' is for search.
Again no need to worry about input. Search commands will be:
'S'<space><number>
What you output when the value is found in the tree is this:
search: 11
"search: "number
What you output when the value is not found is this:
"search: "number" is not in tree"
==============================================================
P
'P' is for pre-order traversal
I
'I' is for in-order traversal
R
'R' is for post-order traversal
The printing family of commands share a common output format:
Example:
////////////////////////
// 3 //
// / \ //
// 2 5 //
// / / \ //
// 1 4 6 //
////////////////////////
In Order:
1 [null, null]--> 0
2 [1, null]--> -1
3 [2, 5]--> 0 ROOT
4 [null, null]--> 0
5 [4, 6]--> 0
6 [null, null]--> 0
Post Order:
1 [null, null]--> 0
2 [1, null]--> -1
4 [null, null]--> 0
6 [null, null]--> 0
5 [4, 6]--> 0
3 [2, 5]--> 0 ROOT
Pre Order:
3 [2, 5]--> 0 ROOT
2 [1, null]--> -1
1 [null, null]--> 0
5 [4, 6]--> 0
4 [null, null]--> 0
6 [null, null]--> 0
==============================================================
B
NOTE: 'B' has been dropped from the assignment. I want you to instead print the balance factor of each node when it is printed by a print command.
If you have already implemented the B command that is fine. I will not be testing for it. If you have done it already, I might be willing to give you extra credit toward the other assignements.
==============================================================
** NEW!!
Lines that begin with '/' are comments until the end of the line
I added this so I could annotate each test case so you can easily read what the test is testing for.
Once you have read in the first character from a line and found it to be a '/' comment cin.ignore('\n') will skip the rest of the input for that line.
==============================================================
NOTE: the EASIEST way to set up your working directory is to copy: a tar file I have made for you.
***make sure you delete the old tests before you get a fresh copy of my tests
$rm tests/t[0-9][0-9]*
$cp /user/s4/admiral/p1_tests.tar .
$tar xvf p1_tests.tar
$scp username@jaguar.ecst.csuchico.edu:/user/s4/admiral/p1_tests.tar .
$tar xvf p1_tests.tar
$java Main
$java Main debug
$./avl < tests/t01 > tests/t01.myout $diff tests/t01.myout test/t01.out $The diff command will output nothing if your output matches mine. However if there are differences diff will tell you which lines are your file but not mine and vice versa.
Diff will be the basis of how I will test your program's outputs against my absolutely 100% correct output.
You will find a perl script in the test directory. You can move it into your p1 directory and execute it with:
$ perl run_p1_test.plI advise running the script after every change you make to your program. You can edit the script with your text editor to change the directory where it looks for files and the program it uses to generate your outputs.
NEW!!
You will find a turn-in directory under:
/user/projects/csci311/p1/your-user-name
All your .cpp and .h files and your Makefile should be turned in.
Six files in all is what I would prefer. If you folded the AVLnode class into your AVLtree.h and AVLtree.cpp that is fine. Then you would have four files to turn in.
I will compile your programs when I grade them so DO NOT turn in an executable or any .o files.
I recommend that you add the following to your Makefile:
clean:
rm *.o avl
turn_in:
cp *.cpp *.h Makefile /user/projects/csci311/p1/user_name
$make clean
$make turn_in
This is a difficult program to debug. Here are my recommended steps toward a working solution.
Start the project by making the following files:
AVLtree.h AVLtree.cpp AVLnode.h AVLnode.cpp main.cpp MakefileAdd to these files empty functions. So what you should have is a project that compiles with the make command. From now on you must keep your project in a state that compiles.
Get main finished. It is real simple. Make a loop that reads in the character into a switch statement..... c << cin switch(c) case 'A': data << cin ......
Go ahead and implement the AVLtree/AVLnode classes as just a standard binary search tree with no delete function yet.
I want you to do this because at this point you can write final versions of:
pre_order() post_order() in_order() search()I'll make the test cases for these NOT dependent on having a valid functioning AVL tree. A working binary tree you should be easy.
Get your insert function to correctly propagate the balance factors up the tree. If you can't get this DO NOT do anything else. You must get this to work. Use a boolean or enum that is passed by reference in your insert() that signals callers that the tree has increased in height.
Now add the 3 cases of what to do when insert returns a "height changed".
No use your balance factors to detect the need for a single left or right rotation. Get the single rotation functions left_rotate() and right_rotate() working because double rotations can use these two functions.
Sadly it may be too late in the project for me to have you all do it MY WAY. It would be a good idea to do the insert Kruse's way.
Now add the code to detect double rotations. The real challenge is getting the balance factors correct afterward. Use the cases that Kruse's code does.
Now to tackle deletions. If you have rotate_left and rotate_right correct these are not that bad. Use a similar approach to insert(). You need to pass around a reference bool or enum that lets callers know if the tree height changed.
What I did was recycle balance_left(),balance_right(),rotate_left(),rotate_right() that I call from insert(). If you do your insert() like Kruse you can do this too.
I used kruse's insert(), left_balance(), and rotate() as the basis for my program. You should too.
It is a good idea to make your functions Class functions and not member functions.
In fact that is what the textbook does and every other C++ implementation does.
Why? You have the problem of deleting this as well as updating the tree class's root pointer.
It may be handy to have parent pointers however they complicate the pointer assignments greatly during a rotation.
Templates are overkill for this assignment. Don't use them unless you love that template syntax.
Don't be a bone head and copy Brian Appleton's C++ implementation. I've read it backward and foward. I'll spot it comming a mile away. Cheating is not an issue I'm really interested but honor demands that you commit seppuku if I notice it! Don't take chances, just do the programming.
It is not very hard for me to collect rudimentary statistics on the source that gets turned in. Finding cheaters is usually just a matter of looking for students whose line counts for each of the project files are suspiciously similar to other students.
If you must cheat do it alone.
I recommend making a To_string(AVL_node) function that dumps your node's instance variables to a string so you can print it. In fact make this look like my output_format.
Since your program will likely have loads of segfaults remember to: compile with -g start gdb, run avl < tests/t0_, when it segfaults do a 'where' to find out what file/function the segfault occurs.
I will not be accepting late assignments.
What I want from you is to turn in what you have.
If you follow the steps I recommend you should have a project that will be worth a fair amount of points.
Please add a README to your turn in directory explaining what isn't working.
If you don't not include a README I will not give you partial credit.
"Turn off" any portions of your code that are broken so that what I get from you will compile.
Start working on the next assignment. After an assignment is due, we will want to move on to talking about the new assignment in lab.