I am trying to build a few backends for a key-value store in C++ by implementing

Question

I am trying to build a few backends for a key-value store in C++ by implementing the following map backends which support insertion and searching operations. I have already built Unsorted (This stores the key-value pairs in an unsorted std::vector), Sorted (This stores the key-value pairs in a sorted std::vector or std::deque. This includes a custom binary search function (const Entry   binary_search(const IT &start, const IT &end, const std::string &target)), as well as Binary Search Tree: (This stores the key-value pairs in a plain binary search tree with a recursive method).

I am looking for help building....

Treap: This stores the key-value pairs in a treap. I need to write functions to insert a key-value pair into a treap given a node, key, and value. I also need functions for rotating the tree to the right and left for a given value.

Also, I need help constructing two applications:

map_bench: This is a benchmarking utility that measure the time it takes for a particular map implementation to insert and search a specific number of items.

frequencies: This is a word counting application that uses the map library to count the number of times every word from standard input appears and outputs the resulting tally to standard output.

Any insight?

Explanation / Answer

C PROGRAM :

#include<stdio.h>

#include<stdlib.h>

struct node

{

    int key;

    struct node left, right;

};

struct node *newNode(int item)

{

    struct node temp = (struct node )malloc(sizeof(struct node));

    temp->key = item;

    temp->left = temp->right = NULL;

    return temp;

}

void inorder(struct node *root)

{

    if (root != NULL)

    {

        inorder(root->left);

        printf("%d ", root->key);

        inorder(root->right);

    }

}

struct node insert(struct node node, int key)

{

    if (node == NULL) return newNode(key);

    if (key < node->key)

        node->left = insert(node->left, key);

    else if (key > node->key)

        node->right = insert(node->right, key);  

    return node;

}

int main()

{

    struct node *root = NULL;

    root = insert(root, 50);

    insert(root, 30);

    insert(root, 20);

    insert(root, 40);

    insert(root, 70);

    insert(root, 60);

    insert(root, 80);

    inorder(root);

    return 0;

}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.