bottomupmergesort

unsigned int hash_function(char *key, int table_size)
{
    unsigned int h = 0;
    for (; *key; *key++)
    {
        h = (h << 5) | (h >> 27);
        h += (int)*key;
    }
    return h % table_size;
}

bottomupmergesort

#include <iostream>
#include <limits>
#include <queue>
using namespace std;

template <class K, class V> // RedBlack Tree for storing Key/Value pairs
class RedBlackTree {
    protected:
    static const bool red = true;       //node color flags
    static const bool black = false;

bottomupmergesort

    void bfs()
    {
        std::queue<nodeptr> fq;
        fq.push(head->right);
        while (!fq.empty())
        {
            int nc = fq.size();
            while (nc > 0)
            {
                auto curr = fq.front();

bottomupmergesort

void preorder(nodeptr h)
{
     if (h != nullptr)
     {
            cout<<h->key<<" ";
            preorder(h->left);
            preorder(h->right);
     }
}

bottomupmergesort

    nodeptr rotate(K key, nodeptr y)
    {
        nodeptr c, gc; //child and grandchild.
        c = (key < y->key) ? y->left:y->right; //set the value of child.
        if (key < c->key) //determine grandchild
        {
            //right rotate
            gc = c->left; c->left = gc->right; gc->right = c;
        } else {
            //left rotate

bottomupmergesort

    void splitNode(K key)
    {
        x->color = red; x->left->color = black; x->right->color = black;
        if (isRed(p))
        {
            g->color = red;
            if (key < p->key != key < g->key) 
                p = rotate(key, g);
            x = rotate(key, gg);
            x->color = black;

bottomupmergesort

    void insert(K key, V val)
    {
        x = head;
        p = x; g = x;
        while (!isNil(x))
        {
            gg = g; g = p; p = x;
            x = (key < x->key) ? x->left:x->right;
            if (isRed(x->left) && isRed(x->right))
                splitNode(key);

bottomupmergesort

    bool isNil(nodeptr h)
    {
        if (h == nullptr)
            return true;
        
        return (h == z);
    }
    bool isRed(nodeptr h)
    {
        return isNil(h) ? false:(h->color == red);

bottomupmergesort

#include <iostream>
#include <limits>
using namespace std;

template <class K, class V> // RedBlack Tree for storing Key/Value pairs
class RedBlackTree {
    protected:
    static const bool red = true;       //node color flags
    static const bool black = false;
    struct node {

bottomupmergesort

unsigned int DiceRoll()
{
      unsinged int result = (rand() % 6) + 1;
      return result; 
}