• Implementing a balanced binary search tree (BST) data structure.
• Practice writing rebalancing routines for an AVL tree.
• Practice writing re-structuring routines for a Splay tree.
• Practice use of recursion in programs.
• Practice writing unit tests.
• Practice measuring the performance of an algorithm.

Wireless power transmission is a technology which allows for the transmission of electrical energy without physical connections. The devices can transfer the energy over short distances or long distances. The technologies are categorized into near field and far-field technologies. The near field sources can provide power in the range of feet such as charging a mobile phone, and the far-field sources can provide power in the range of miles. The near field technologies transfer the power through electromagnetic fields. The far-field technologies transfer the power using microwave or laser.

A startup company decided to research a wireless power transfer system for generating the power from solar cells in the space and beaming the power to the remote places on earth where the regular sources of power are not available. The solar satellite could be illuminated over 99% of the time whereas earth surface solar panels can collect power for an average of 29% of the day. The plan is to launch a network of solar satellites and provide power to customers on earth.

The company is building a simulator to perform feasibility studies. You are assigned a task to develop the data structure that stores the information about the customers. The data structure runs in all satellites in a network of satellites, and it is updated automatically. The decision is made to use self-balancing Binary Search Tree. The data structure module provides the possibility of organizing data in a regular BST or an AVL tree or a Splay tree. It is also possible to convert the data structure in the run time.

A binary tree is a tree structure in which each node has either 0, 1, or 2 children. A BST is a derivative of a binary tree where each node contains a key and value pair. The key determines the nodes' placement in the tree, and the value is the data to be stored. Given a set of rules about how to order the keys, we can create a structure where we can query data from it with a specified key. For a BST, we define these rules as follows:

1. If the target key is less than the key at the current node, traverse to the left child.
2. If the target key is greater than the key at the current node, traverse to the right child.
3. If the keys are equal, the action is determined by our application of the tree. More on this later.

A BST on its own can be efficient, but as the dataset increases in size, we can start running into problems. In the worst case, our BST can become a linked list where each of the new keys is greater than or less than the previous one inserted. On the contrary, the best case is inserting elements into the tree in a way to make it a complete tree. Either case is rare to occur with a large dataset, but imbalances are common. An imbalance can be defined when one subtree on a node becomes significantly larger in size or height compared to the other subtree. As the tree becomes increasingly imbalanced, our average query times begin to increase. Luckily, we have methods to prevent large imbalances.

The AVL Tree

An AVL tree employs rotations during insertions or deletions to balance a BST. As the name implies, nodes are literally rotated up the tree to keep its structure complete. A complete tree, or ideally a perfect tree, is the most efficient kind of binary tree. Insertions, deletions, and queries all take O(log(n)) time in such a case. AVL trees have two types of rotations, left and right, which are shown in the diagram below:

The variables "x" and "y" refer to 2 specific nodes whereas the subtrees "a", "b", and "c" refer to subtrees (which is just a pointer to a node which may or may not have more children). Note that the pointers to "a", "b", and/or "c" can be null, but "x" nor "y" will never be null.

The key to keeping an AVL tree efficient is when we perform these rotations. A rotation is performed on a node that is imbalanced, and an imbalance occurs when the node's children's heights differ by more than 1. For example, in the above diagram, consider node "y" to be imbalanced in the right rotation and node "x" to be imbalanced in the left rotation. Using a left and right rotation, we can perform four rotation combinations. The imbalance in the following examples occurs on the node with the height of 2 (in red).

1. Single left rotation: This is a simple case where we can apply a left rotation to the top node to balance the tree.

2. Single right rotation: Similar to the above case, we can apply a single right rotation to the top node to balance the tree.

3. Double left-right rotation: The following two cases become more complicated and require two rotations. In this example, the imbalance still occurs at the node with height 2. If we perform a single right rotation, we still end up with an unbalanced tree, just mirrored (draw a diagram). So, we must perform two rotations. The first left rotation should transform the tree into a form we can balance with a second right rotation. Which node should the first rotation be performed on (hint: it's not necessarily the node with height 2)?

4. Double right-left rotation: Likewise, this case uses a right rotation followed by a left rotation.

The Splay Tree

Splay trees are binary search trees in which we store the recently accessed node at the root of tree. Such a tree would be a goodchoice for data structure, if in the application some data points are accessed more frequently than others. Although some work is required in this data structure to bring up the recently accessed data point to the root, but as soon as a node is at the root, the next time its access time is O(1). The amortized analysis of Splay trees reveals that the search operation is O(log n).

Your assignment is to implement a binary search tree with balancing methods.

For this project, you are provided with the skeleton .h and .cpp files and a sample driver:

• wpower.h – Interface for the Customer and WirelessPower classes.
• wpower.cpp – A skeleton for the implementation of the class WirelessPower.
• driver.cpp – A sample driver program. (Note: this file is provided to show a typical usage. Since the project is not implemented, trying to compile and run this driver program will not generate the sample output in driver.txt. Once you develop your project, you should be able to generate the similar output as driver.txt by running this driver program. Please note, the randomly generated values are different on different platforms.)
• driver.txt – A sample output produced by driver.cpp.

Please note, you may not change any of the private variables or public function declarations or file names. They will be used for grading. Also, any provided function implementations may not be modified. You may, however, add your own private functions as helpers. The current private function declarations are provided as a backbone to help you.

Additionally, you are responsible for thoroughly testing your program. Your test program, mytest.cpp, must be submitted along with other files. For grading purposes, your implementation will be tested on input data of varying sizes, including very large data. Your submission will also be checked for memory leaks and memory errors.

This project has three classes: Random, Customer, and WirelessPower. The Random class is provided as a supplementary class to facilitate the testing. The Customer class defines the nodes in the binary tree. The WirelessPower class is the one that implements the balanced binary search tree. This class allows for creating three different types of BST. The three types are a regular BST with no balancing, an AVL tree, and a Splay tree.

Class WirelessPower

The WirelessPower class implements a binary search tree. The WirelessPower::m_root member variable points to a node of type Customer. Every node in WirelessPower is a Customer object. The nodes are organized as a binary search tree. The WirelessPower class supports the insertion and deletion operations. After insertion or deletion operations the class checks for any required property such as an imbalance and it performs the re-structuring operations.

For the WirelessPower class, you must implement the following methods in wpower.cpp:

• The class declarations WirelessPower, Customer, Random and provided function implementations in wpower.cpp may not be modified in any way. No additional libraries may be used. However, private helper functions are permitted in the WirelessPower class.
• No STL containers or additional libraries may be used in the implementation of the WirelessPower class. However, you can use STL containers in the Tester class for the testing purposes.
• The required functionality is provided in the Customer class. There is no need for any modifications to the implementation of this class.
• Your code should not have any memory leaks or memory errors.
• The lowest level of nodes which store the keys have zero height.
• Follow all coding standards as described on the C++ Coding Standards. In particular, indentations and meaningful comments are important.
• The function WirelessPower::dumpTree(...) prints out the nodes information in an in-order traversal. For every node, it prints the id followed by the height of the node in the WirelessPower tree. The following example presents a sample output of the dumpTree() function for an AVL tree. The tree viewer tool shows a graphical representation of the output of the dump function. You can copy & paste the dump() output in the viewer. This tool facilitates debugging. Note: The implementation for this requirement is provided to you.
  

  ((((19224:0)19289:1(19372:0))20201:2((26241:0)27904:1))53002:3(60496:1(93209:0)))

  

You need to test your project and you need to submit your tests along with your project. Tests must be submitted in a file called mytest.cpp.

• The test file name must be mytest.cpp; the file name must be in lower case, a file name like myTest.cpp is not acceptable.
• The test file must contain the declaration and implementation of your Tester class and the main() function as well as all your test cases, i.e. calls to your test functions.
• You are responsible for thoroughly testing your work before submission. The following section presents a non-exhaustive list of tests to perform on your implementation.
• You must write a separate function for every test case.
• Every test function must return true/false depending on passing or failing the test. Visual outputs are not accepted as test results.
• Tests cannot be interactive. The test file mytest.cpp must compile and run to completion.
• An example of declaring, implementing, and calling a test function, and outputting the test results was provided in the driver.cpp file of project 0.
• The testing guidelines page provides information that helps you to write more effective test cases.

Note: Testing incrementally makes finding bugs easier. Once you finish a function and it is testable, make sure it is working correctly.

Testing WirelessPower Class

• Test whether the AVL tree is balanced after a decent number of insertions, e.g. 300 insertions. (Note: this requires visiting all nodes and checking the height values are correct.)
• Test whether the BST property is preserved after all insertions. (Note: this requires visiting all nodes and comparing key values.)
• Test whether the Splay tree performs the splay operations. For example, we can insert multiple nodes in the splay tree and after every insertion we check whether the inserted node is at root and the tree preserves the BST property.
• Test whether the height values are correct after multiple insetions in a Splay tree.
• Test the remove function for a normal case in the BST tree. Trying to remove a node from a tree results in a tree without the node.
• Test the remove function for an edge case in the BST tree. In this case the tree has only one node and we remove the node.
• Test whether the AVL tree is balanced after multiple removals. For example, insert 300 nodes, then remove 150, and check the AVL property.
• Test whether the BST property is preserved after multiple removals from a BST tree and an AVL tree.
• Test whether the height values are correct in a BST tree after multiple removals.
• Test the assignment operator for a normal case.
• test the assignment operator for an error case, e.g. assigning an empty object to an empty object.

Random Numbers for Testing

For testing purposes, we need data. Data can be written as fixed values or can be generated randomly. Writing fixed data values might be a tedious work since we need a large amount of data points. The approach for creating data will be your decision.

In the file driver.cpp there is the class Random which generates pseudorandom numbers. The class is using a default seed value. On the same machine it always generates the same sequence of numbers. That is why the numbers are called pseudorandom numbers, they are not real random numbers. Please note, the numbers are machine dependent, therefore, the numbers you see in the sample file driver.txt might be different from the numbers your machine generates.

Memory leaks and errors

• Run your test program in valgrind; check that there are no memory leaks or errors.
  Note: If valgrind finds memory errors, compile your code with the -g option to enable debugging support and then re-run valgrind with the -s and --track-origins=yes options. valgrind will show you the lines numbers where the errors are detected and can usually tell you which line is causing the error.
• Never ignore warnings. They are a major source of errors in a program.

You must submit the following files to the proj2 directory.

• wpower.h
• wpower.cpp
• mytest.cpp - (Note: This file contains the declaration and implementation of your Tester class as well as all your test cases and a main function.)

If you followed the instructions in the Project Submission page to set up your directories, you can submit your code using the following command:

   cp wpower.h wpower.cpp mytest.cpp ~/cs341proj/proj2/