Intruction Implement a Hash Table using a Tree. This data structure is similar to the linked list hash dictionary described in the book. However, instead of storing the values in each “bucket” as a...

1 answer below »
Filling Binary Tree and Hash class


Intruction Implement a Hash Table using a Tree. This data structure is similar to the linked list hash dictionary described in the book. However, instead of storing the values in each “bucket” as a linked list, you will store the values in a binary tree. Part 1: DictTree The dictionary tree class stores key/value pairs using a binary tree where the order is based on the value of the key. The implementation is essentially the same as a standard binary tree except the tree order is based on the key. The following is a representation of the data structure followed by the header file. key item left right * * key item left right * * key item left right * * key item left right * * key item left right * * template class DictTree { private: TreeNode* root; // any other functions you find useful int numNodes; public: DictTree(); ~DictTree(); void add(KeyType newKey, ItemType newItem); bool remove(KeyType newKeys); bool contains(KeyType key); ItemType lookupItem(KeyType key); int size(); void traverse(void visit(ItemType&)) const; }; Your job is to implement each of the methods in the header class. You also need to define the Node as a class or struct. The implementation should be very similar to a standard binary tree. The following is the output if your dictionary tree is implemented correctly: Part 2: HashTable Once the tree dictionary is implemented, completing the HashTable implementation requires little additional code. The HashTable is implemented using an array of buckets where each of these buckets is a DictTree pointer: buckets 0 * 1 * 2 * … * n * When adding an item to the hash table using a key for the lookup, use of a hash function is required. This hash function takes the key value as input and returns the bucket the item should be associated with. The hash function is called as follows: int b = getHashIndex(key); b now stores the bucket index that the item associated with key is located. Refer to the notes given in the started code. The following is the output if the hash table is implemented correctly: DictTree DictTree Introduction Part 1: DictTree Part 2: HashTable Test Driver Part 3: Questions Deliverables
instruction-nvspeyhz.pdf dicttree-d3lyhe1p.h hashtable-2d1tcwu4.h hashtablebasictest-dfxjenx5.cpp
Answered Same DayOct 09, 2021

Answer To: Intruction Implement a Hash Table using a Tree. This data structure is similar to the linked list...

Aditi answered on Oct 10 2021
151 Votes
DictTree.h
#pragma once
#include
#include
using namespace std;
template
struct TreeNode
{
    // Your implementation...
    KeyType key;
    ItemType item;
    TreeNode* left;
    TreeNode* right;
};
template
class DictTree
{
private:
    TreeNode* root;
    TreeNode* removeFromSubtree(TreeNodeyType, ItemType>* subTree, KeyType key, bool& success);
    TreeNode* removeNode(TreeNode* node);
    TreeNode* removeLeftmostNode(TreeNode* node, TreeNode* successor);
    TreeNode* containedInSubtree(TreeNode* subTree, KeyType key);
    void preorder(void visit(ItemType&), TreeNode* treePtr) const;
    int numNodes;
public:
    DictTree();
    void add(KeyType newKey, ItemType newItem);
    bool remove(KeyType newKeys);
    bool contains(KeyType key);
    ItemType getItem(KeyType key);
    int size();
    void traverse(void visit(ItemType&)) const;
};
template
DictTree::DictTree()
{
    // Set up the root and the initial number of nodes to 0
    root = NULL;
    numNodes = 0;
}
template
void DictTree::add(KeyType newKey, ItemType newItem)
{
    // Use containedInSubtree to determine if a node with newKey exists
    // If it does, use setValue to set the value to newKey and newItem and return.
    // If the root hasn't been set up, make a new node with newKey, newItem
    // and set equal to this new node and return.
    
    TreeNode* newNode = new TreeNode();
    newNode->key = newKey;
    newNode->item = newItem;
    newNode->left = newNode->right = NULL;
        
    if(numNodes == 0){
        root = newNode;
        numNodes++;
    }
    
    TreeNode* temp = containedInSubtree(root, newKey);
    
    if(temp != NULL){
        temp->item = newItem;
    }
    
    else{        
        TreeNode* currNode = root;
        TreeNode* parent = root;
        while(currNode){
            parent = currNode;
            if(newKey > currNode->key){
                currNode = currNode->right;
            }
            else{
                currNode = currNode->left;
            }
        }
        if(newKey < parent->key){
            parent->left = newNode;
        }
        else{
            parent->right = newNode;
        }
    }
}
template
bool DictTree::remove(KeyType key)
{
    // This method is done.
    bool isSuccessful = false;
    root = removeFromSubtree(root, key, isSuccessful);
    if (isSuccessful)
        numNodes--;
    return isSuccessful;
}
template
TreeNode* DictTree::removeFromSubtree(TreeNode* subTree, KeyType key, bool & success)
{
    // Refer to previous implementation nodes
    if(subTree == NULL){
        success = false;
        return NULL;
    }
    else if(subTree->key < key){
        subTree->right = removeFromSubtree(subTree->right, key, success);
        return subTree;
    }
    else if(subTree->key > key){
        subTree->left = removeFromSubtree(subTree->left, key, success);
        return subTree;
    }
    else if(subTree->key == key){
        subTree = removeNode(subTree);
        success = true;
        return subTree;
    }
}
/*
* Case 1) Node is a leaf - it is deleted
* Case 2) Node has one child (left/right) - parent adopts child
* Case 3) Node has two children - find successor node.
*/
template
TreeNode* DictTree::removeNode(TreeNode* node)
{
    if(node->left == NULL && node->right == NULL){
        delete node;
        return NULL;
    }
    else if(node->left == NULL){
        TreeNode* temp = node->right;
        delete node;
        return temp;
    }
    else if(node->right == NULL){
        TreeNode* temp = node->left;
        delete node;
        return temp;
    }
    else{
        node = removeLeftmostNode(node, node->right);
        node->right = NULL;
        return node;
    }
    // Refer to previous implementation nodes
    return NULL;
}
template
SOLUTION.PDF
SOLUTION.PDF

Answer To This Question Is Available To Download

Related Questions & Answers

More Questions »

Submit New Assignment

Copy and Paste Your Assignment Here
Have files?