CS 3100 Project #4
CS 3100 – Data Structures and Algorithms
Project #4 – Indexing with AVL Trees
Learning Objectives
Demonstrate effective use of memory management techniques in C++
Implement a data structure to meet given specifications
Design, implement, and use an AVL tree data structure
Analyze operations for time complexity
Overview
Your task for this assignment is to implement an AVL tree that serves as a map data type (sometimes
also called a dictionary. A map allows you to store and retrieve key/value pairs. For this project, the key
will be an integer and the value will be a string.
The AVLTree Class
The map will be implemented as an AVL tree. For this project, you must write your own AVL tree - not
using code from outside sources. Your AVL tree should remain balanced by implementing single and
double rotations when inserting new data. Your tree must support the following operations:
ool AVLTree::insert(int key, string value) – Insert a new key/value pair into the tree. For this
assignment the duplicate keys are not allowed. This function should return true if the key/value
pair is successfully inserted into the map, and false if the pair could not be inserted (for example,
due to a duplicate key already found in the map).
int AVLTree::getHeight() – return the height of the AVL tree.
int AVLTree::getSize() – return the total number of nodes (key/value pairs) in the AVL tree.
friend ostream& operato
(ostream& os, const AVLTree& me) - print the tree using the
operator. You should overload the
operator to print the AVL tree “sideways” using indentation
to show the structure of the tree. For example, consider the following AVL tree (each node
contains a key, value pair):
3/9/22, 7:05 PM
Page 1 of 3
This tree would be printed as follows:
XXXXXXXXXX, Fifty
XXXXXXXXXX, Forty-five
40, Forty
XXXXXXXXXX, Thirty
XXXXXXXXXX, Twenty
XXXXXXXXXX, Ten
(Note: If you turn your head sideways, you can see how this represents the tree.)
(Also note: This style of printout can be directly implemented as a right-child-first inorder traversal
of the tree.)
ool AVLTree::find(int key, string& value) – if the given key is found in the AVL tree, this
function should return true and place the co
esponding value in value. Otherwise this function
should return false (and the value in value can be anything).
vecto
string> AVLTree::findRange(int lowkey, int highkey) – this function should return a C++
vector of strings containing all of the values in the tree with keys ≥ lowkey and ≤ highkey. Fo
each key found in the given range, there will be one value in the vector. If no matching key/value
pairs are found, the function should return an empty vector.
Example: Suppose the call resultVector = myTree.findRange(30, 47) were called on the tree
pictured above. The findRange function would then return a vector containing the strings:
{"Thirty", "Fourty", "Forty five"}.
Turn in and Grading
3/9/22, 7:05 PM
Page 2 of 3
The AVLTree class should use a seperate AVLTree.h and AVLTree.cpp file.
Please zip your entire project directory into a single file called project4.zip and upload to the
dropbox in Pilot.
This project is worth 50 points, distributed as follows:
Task Points
AVLTree::insert stores key/value pairs in the co
ect locations in the AVLTree, and co
ectly
ejects duplicate keys
3
AVLTree::getHeight() co
ectly returns the height of the tree 3
AVLTree::getSize() co
ectly returns the number of key/value pairs in the tree 3
The tree maintains co
ect balance, regardless of the order in which keys are inserted 10
operato
prints the tree in a neat and readable manner, using indentation or some othe
appropriate mechanism to clearly show the structure of the tree
4
AVLTree::find co
ectly finds and returns key/value pairs in the tree in Θ(log n) time, and
eturns false when no matching key is found
4
AVLTree::findRange co
ectly returns a C++ vector of strings matching keys in the specified
ange
6
AVLTree::operator= co
ectly creates an independent copy of an AVL tree 4
Copy constructor co
ectly creates an independent copy of an AVL tree 4
Code has no memory leaks 4
Code is well organized, well documented, and properly formatted. Variable names are clear,
and readable. Your AVLTree class is declared and implemented in separate (.cpp and .h) files.
5
3/9/22, 7:05 PM
Page 3 of 3
#include "AVLTree.h"
#include
#include
using namespace std;
int main() {
AVLTree tree;
cout
tree.insert(50, "Fifty");
This should print 0, because it returns false (no duplicates allowed):
cout
tree.insert(50, "Another fifty");
cout
tree.insert(100, "One hundred");
cout
tree.insert(200, "Two hundred");
single rotate left
cout
"\n\n";
cout
tree
endl;
cout
tree.insert(40, "Fourty");
cout
tree.insert(30, "Thirty");
single rotate right
cout
tree.insert(150, "One hundred fifty");
cout
tree.insert(175, "One hundred seventy-five");
double rotate right
cout
tree.insert(35, "Thirty-five");
cout
tree.insert(34,"Thirty-four");
double rotate left
cout
tree.insert(50, "Fifty yet again");
should be 0
cout
tree.insert(34, "Thirty-four again");
should be 0;
cout
tree.insert(200, "Two hundred");
should be 0;
Expect: XXXXXXXXXX
cout
"\n\n";
cout
tree
endl;
cout
tree.getSize()
endl;
9
cout
tree.getHeight()
endl;
3
string result;
cout
tree.find(50, result)
endl;
1
cout
result
endl;
Fifty
cout
tree.find(40, result)
endl;
1
cout
result
endl;
Fourty
cout
tree.find(175, result)
endl;
1
cout
result
endl;
One hundred seventy-five
cout
tree.find(600, result)
endl;
0
vecto
string> vec = tree.findRange(30, 200);
all of it
for (vecto
string>::iterator it = vec.begin(); it != vec.end(); ++it) {
cout
*it
endl;
}
cout
"\n\n"
endl;
vec = tree.findRange(100, 200);
ight subtree
for (vecto
string>::iterator it = vec.begin(); it != vec.end(); ++it) {
cout
*it
endl;
}
cout
"\n\n"
endl;
vec = tree.findRange(30, 100);
left subtree
for (vecto
string>::iterator it = vec.begin(); it != vec.end(); ++it) {
cout
*it
endl;
3/9/22, 7:05 PM
Page 1 of 2
}
cout
"\n\n"
endl;
return 0;
}
3/9/22, 7:05 PM
Page 2 of 2