Threaded AVL Tree

Description:

Threaded AVL Search Tree (single thread; right): similar to the threaded BST however rotations of an AVL tree are implemented. Adding threading allows to traverse the nodes in order by using the threads for every node; thus, traversing without recursion or the use of a stack. Therefore, limiting the amount of space required to keep track of nodes. Uses Catch Framework for creation of test cases.

Commands within bstt.h class:

• copy constructor / destructor present. [O(N)]
• operator=: clears "this" tree and then makes a copy of the "other" tree. [O(N)]
• clear: clears the tree's nodes and all its contents that were from the struct (tree is now empty). [O(N)]
• size: returns the number of nodes in the tree. [O(1)]
• height: returns the height of the tree. [O(1)]
• search: searches for the key in the tree and returns boolean value accordingly. [O(lgN)]
• range_search: searches the tree for all keys that are within the specified range (lower <= upper) and are returned in a vector. [O(lgN + M); M is the # of keys in range]
• insert: inserts user's node as (key, value) pair. [O(lgN)]
• operator[]: returns the value that the user requests and if not found then return default value. [O(lgN)]
• operator(): finds the key and returns the key to the right. If threaded then follow thread to next key inorder. Not found will result in default value.
• operator%: returns the height stored in the node that contains a key; no key results in -1.
• begin: obtains the first key to initiate inorder traversal [O(lgN)]
• next: follows the thread and returns key that is next inorder by pass by reference.
• dump: output tree's contents.

Data Structure: AVL Tree
Leveraged Knowledge:

• Tree Rotations Cases: Right, Left then Right, Right then Left, Left
• Helper functions under private
• Threading saves space during inorder traversal but uses time to apply threads during insertion/deletion.

Download Code Here