Description
This assignment asks you to extend the implementation of a binary search tree in two different ways.
Overview
For this assignment you need implement two different data structures, both extending the operations of a BST.
1. First, we want to implement a binary search tree (BST), that can be used as a self-organizing data structure. The BST should implement the usual operations as described in class (insert, search, delete, plus helper methods) as well as the following functionality: (1) Insert at the root, using the algorithm described in class/lecture slides, and (2) find the k-th smallest element, using the algorithm described in class/lecture slides.
2. The second data structure is a binary search tree that allows duplicate keys to be stored and retrieved efficiently
In more detail you must implement:
1. For the move-to-front BST:
1. Insert at the root: There are many algorithms to implement root insert operations. For this assignment you must implement this operation as described in the lecture slides (the “left hook, right hook” algorithm). Your implementation should be efficient in terms of steps needed and extra memory allocation.
2. Find the k-th smallest element in the BST. This operation should use the following algorithm, as described in class/lecture slides: Recall that in order to implement this operation efficiently, we need to extend the node class to include an extra field, that gives us the height of the tree rooted at the node. This implied that the delete, insert and insert as root operations must also be extended, in order to update these fields (size of subtrees) when the tree is modified.
2. For the BST with duplicate keys:
1. Extend the BST operations so that it is possible to allow duplicate keys (different entries that happen to have the same key). This can be achieved by adding the following convention: When searching for key with value k in the tree, then start the search at the root as before and if k is less than or equal to the key in the root search (recursively) the left subtree for k, otherwise search the right subtree for k. This way, if we allow duplicate entries in the tree (nodes that have the same key values), we know that the following property holds: at every node v in the tree, all nodes below v with keys equal to v can only be on its the left subtree.
2. Implement a method deleteAll(k) that finds and deletes all nodes with key equal to k, when the tree allows duplicate keys.
3. deleteAll() should be an additional operation in your implementation. The delete() operation should still be there in the BST implementation that allows duplicate keys, and it should delete only the first entry found with the given key.
Make your implementation as efficient as possible. Your code should include the running time of each operation (of the interfaces given below) in the comments. The implementation should use a reasonable amount of extra space to do the operations.
Details
Use a linked structure for the representation of the binary tree. The space used should be proportional to the number of nodes in the tree. You must implement two separate classes for the two types of trees required. Implement the following interfaces:
For the move-to-front BST:
package bst;
public interface FrontBSTTree
/**
* Inserts a new node in the tree, using insertion at the root
* @param newnode the node to be inserted and become the root for the current tree
*/
public void insertAsRoot(BSTNode
/**
* Find and remove the k-th smallest element in the tree
* @param k the k-th value for the key
* @return node with the k-th smallest key in the tree
*/
public BSTNode
}
For the second part, the BST with duplicates, implement the following interface:
package bst;
public interface DupBSTTree
/**
* Delete all nodes in tree whose key is equal to k
* @param key of the nodes to delete
*/
public void deleteAll(K key);
}
Our implementation will be based on BST nodes, as defined by the following interface:
package bst;
public interface BSTNode
/**
* Recovers the value stored in the node
* @return the value stored in the node
*/
public V getValue();
/**
* Sets the value stored in the node
* @param value the value to store in the node
*/
public void setValue(V value);
/**
* Recovers the key stored in the node
* @return the key stored in the node
*/
public K getKey();
/**
* Sets the key stored in the node
* @param key the key to store in the node
*/
public void setKey(K key);
/**
* Recover the parent stored of the current node
* @return the parent of the current node
*/
public BSTNode
/**
* Set the parent of the current node
* @param parent to set for the current node
*/
public void setParent(BSTNode
/**
* Recovers the left child of the node
* @return the left child of the node
*/
public BSTNode
/**
* Recovers the right child of the node
* @return the right child of the node
*/
public BSTNode
/**
* Sets a new node to be the left child of this node
* @param newLeftChild the new left child of this node
*/
public void setLeftChild(BSTNode
/**
* Sets a new node to be the right child of this node
* @param newRightChild the new right child of this node
*/
public void setRightChild(BSTNode
/**
* Check if the node is a leaf node. A leaf node is a node which has no children
* @return true if a leaf node else false
*/
public boolean isLeafNode();
/**
* Check if the node is a root node. A root node is a node which does not have a parent
* @return true if a root node else false
*/
public boolean isRootNode();
/**
* recover the height of the tree rooted at the current node
* Recall that this must be implemented as an O(1) operation.
* @return the height of the tree rooted at the current node
*/
public int getHeight();
}
The BSTTree
package bst;
public interface BSTTree
/**
* Calculates the size of the tree.
* @return the number of internal and leaf nodes in the tree
*/
public int size();
/**
* Checks if the tree is empty
* @return true if the tree contains no nodes else false
*/
public boolean isEmpty();
/**
* Computes the maximum height of the tree
* @return the maximum height of the tree
*/
public int getHeight();
/**
* Adds a node as the root of the tree
* @param root add a node as the root of the tree
*/
public void setRoot(BSTNode
/**
* Recovers the root of the tree
* @return the root node of the tree
*/
public BSTNode
/**
* Recovers the distance between the root node and the query node.
* The distance is in terms of the number of edges between the query node
* and the root.
* @param node is the initial location of the query
* @return the distance from node to the root
*/
public int distanceToRoot(BSTNode
/**
* Checks if the Binary Search Tree is balanced
* @return true if the binary search tree is balanced otherwise false
*/
public boolean isBalanced();
/**
* insert a new key-value pair in the BST
* @param key of the new node
* @param value of the new node
*/
public void insert(K key, V value);
/**
* find the node of the tree with the given key
* @param key of the node to recover
* @return the node that matches the search key, null of no node to with this key
*/
public BSTNode
/**
* delete the node of the tree with the given key
* @param key of the node to delete
* @return the node that is deleted, null of no node to delete
*/
public BSTNode
}
Use the following recursive definition for a balanced binary tree, when implementing the isBalanced() method:
A binary tree with root node v is called balanced if all the following properties hold:
· The left subtree of v (v.left) is balanced
· The right subtree of v (v.right) is balanced
· The heights of the left and right subtree of v differ by at most 1: |height(v.left)−height(v.right)|≤1|height(v.left)−height(v.right)|≤1
Your final code submitted should include at least three concrete classes called DuplicateKeyBSTTree, MoveToFrontBSTTree and BinarySearchTreeNode which should implement DupBSTTree, FrontBSTTree and BSTNode respectively. Each of these classes must contain a default constructor or your submission will have compilation errors.
You may use your own code that you implemented in the tutorial however you should not use any code from other sources for the tree link structure.