Project 4: Self Organizing Binary Search Tree

Educational Objectives: Understanding and developing a self organizing binary search tree data structure, practicing tree traversal algorithms, practicing recursive algorithms, and analyzing of algorithm complexity.

Statement of Work: Implement a class template for a generic self organizing binary search tree, which supports element insertion, deletion, search (and self-restructuring), and in-order and level-order traversals. Analyze the time complexity of one of the member functions.

Project Requirements:

In this project, you will develop a class template for a generic self organizing binary search tree. The self organizing binary search tree can restructure itself based on the search frequency of the data in the tree. In particular, a threshold value is maintained by the tree and a search count is maintained in each node of the tree. The search count in a node is increased by 1 each time the data in the node is searched. When the search count reaches the threshold, the corresponding node will move up in the tree by one level, which is achieved by a single rotation: rotate the position of the current node with its parent node. Let t denote the node whose search count reaches the threshold, and let p denote the parent node. Let us also assume that t is the left child of p. Then the rotation occurs as follows: 1) node t will occupy the position of p (that is, the parent of p will point to t instead of p); 2) the right child of node t becomes the left child of p; and 3) node p becomes the right child of node t. Note that this is the single rotation in AVL tree that we discussed in class. The following figure shows the single rotation (the node with data 40 reaches the search count). The case that t is the right child of the parent node p is analogous to the one we just discussed: 1) node t will occupy the position of p (that is, the parent of p will point to t instead of p); 2) the left child of node t becomes the right child of p; and 3) node p becomes the left child of node t.

After the single rotation, the search count of node t is re-set to 0. When a node is already at the root (top) of the tree, no rotation should be performed even if the search count reaches the threshold. For this case, you also need to re-set the search count to 0.

Name your self organizing binary search tree class template as "BST". Your BST must have a nested structure named "BSTNode" to contain the node related information (including, e.g., element, the search count, and pointers to children nodes). In addition, BST must at least support the following interfaces (in the following T is the abstract type of the elements stored in a node in BST).

Public interfaces

• BST(int th=default_threshold_value): constructor. Parameter th specifies the value for the single-rotation threshold. The default value default_threshold_value should be 1.
• BST(const string input, int th=default_threshold_value): constructor. The first parameter is a string containing the values (separated by spaces) to be inserted into the BST. An example could be string "1 23 34 30" for an integer-valued BST, which indicates to insert integers 1, 23, 34, and 30 into the tree in that order. The second parameter specifies the value for the single-rotation threshold. The default value default_threshold_value should be 1. 
• BST(const BST&): copy constructor. You need to copy both the element and the corresponding search count in each node.
• BST(BST&&): move constructor.
• ~BST(): destructor.
• void buildFromInputString(const string input): parameter "input" is string containing the values to be inserted to the tree (separated by spaces), as we have discussed above. The tree should be built based on the input string. If the tree contains nodes before the function is called, you need to first delete all the existing nodes. 
• const BST & operator= (const BST &): copy assignment operator. You need to copy both the element and the corresponding search count in each node.
• const BST & operator=(BST &&): move assignment operator.
• bool empty(): return true if the tree is empty. Return false otherwise.

The following public functions will call the corresponding private versions of the functions to perform certain tasks:

• void printInOrder() const: print out the elements in the tree in the in-order traversal.
• void printLevelOrder() const: print out the elements in the tree in the level-order traversal.
• int numOfNodes() const: return the number of nodes in the tree.
• int height() const: return the height of the tree.
• void makeEmpty(): delete all nodes from the tree (make the tree empty)
• void insert(const T& v): insert v into the tree.
• void insert(T &&v): insert v into the tree (move instead of copy)
• void remove(const T& v): delete value v from the tree.
• bool contains(const T& v): search to determine if v is the tree.

Private interfaces. 1) All the required private member functions must be implemented recursively except the function printLevelOrder(BSTNode *t). 2) No static variables or global variables can be used in implementing these recursive functions (zero point for the corresponding function if it uses static or global variables). 3) For some of the private member functions, we intentionally leave out the parameters. You need to decide if you need to have additional parameters for each such private member functions.

• void printInOrder(BSTNode *t) const: print the elements in the subtree rooted at t in the in-order traversal. 
• void printLevelOrder(BSTNode *t) const: print the elements in the subtree rooted at t in the level-order traversal. 
• void makeEmpty(BSTNode* &t): delete all nodes in the subtree rooted at t. Called by functions such as the destructor.
• void insert(const T& v, BSTNode *&t): insert v into the subtree rooted at t. No duplicated elements are allowed. If value v is already in the subtree, this function does nothing. Initialize the search count to 0 for the newly added node.
• void insert(T&& v, BSTNode *&t): insert v into the subtree rooted at t (move instead of copy). No duplicated elements are allowed. If value v is already in the subtree, this function does nothing. Initialize the search count to 0 for the newly added node.
• void remove(const T& v, BSTNode *&t): remove value v from the subtree rooted at t (if it is in the subtree). If the node x containing v has two child nodes, replace the value of node x with the smallest value in the right subtree of the node x.
• bool contains(const T& v, BSTNode *&t, ...other parameters if necessary...): return true if v is in the subtree rooted at t; otherwise, return false. Note that the search count of the corresponding node containing v should be increased by 1. If search count reaches the threshold, perform the single rotation discussed above. Reset search count to 0. If the node containing the value v is already the root of the tree, do not rotate (but you do need to reset the search count to 0). Note that you can add other parameters if necessary. You may or may need to add additional parameters depending on your design and implementation of BST.
• int numOfNodes(BSTNode *t) const: return the number of nodes in the subtree rooted at t.
• int height(BSTNode *t) const: return the height of the subtree rooted at t. Recall that the height of a tree is the number of the links along the longest path from the root to any of the leaf nodes. The height is an empty tree is -1.
• BSTNode * clone(BSTNode *t) const: clone all nodes in the subtree rooted at t. Called by functions such as the assignment operator=. Note that you also need to copy the search count in the original node to the corresponding cloned node.

Other Requirements:

• Analyze the worst-case time complexity of the private member function height(BSTNode *t) of the binary search tree. Give the complexity in the form of Big-O. Your analysis must be clearly understandable by others. Name the file containing the complexity analysis as "analysis.txt".
• You can use any C++/STL containers and algorithms
• If you need to use any containers, you must use the ones provided in C++/STL. You cannot use the ones you developed in the previous projects.

Provided Code

The tar file contains the following files:

1. proj4_driver.cpp: the driver program to test your implementation of the self organizing binary search tree.
2. proj4.x: executable code (compiled on linprog.cs.fsu.edu)
3. proj4.input: sample input file. You can redirect the standard input of proj4.x to this file ('./proj4.x < proj4.input'), or you can just type line by line when the program asks for input.

Deliverable Requirements

Turn in the tar file containing all c++ header files, source files, makefile, and analysis.txt on Canvas.

Grading

• Typing 'make' in the subdirectory containing your submitted files should produce the executable proj4.x on linprog. If the program or makefile has any kind of (compiling) errors, no more than 10 points will be awarded.
• proj4.x is successfully produced (15 points).
• Pass all cases in the provided files (35 points)
• Pass all cases in another testing program and input file (not provided) (15 points)
• Implementation of 18 public functions, which may call private functions (30 points)
  • 2 points each for buildFromInputString, printInOrder, printLevelOrder, numOfNodes, height, insert, remove, and default constructor(16 points)
  • contains (5 points)
  • 1 point each for all other public functions (9 points)
• Complexity analysis. 2 points for the big O form. 3 points for explanation (5 points)

Notes:

• You should thoroughly test your program in addition to the simple sample input file proj4.input. We will test your program using other test files in addition to proj4.input file.