4
\$\begingroup\$

I implemented an implicit treap and tested it a little. It works fine but I'd like to know if there are ways to improve/simplify things and/or if some parts are incorrect. Later, I'll augment code to allow for more operations (interval reversal, shifts, etc..).

Treap node.

struct Node
{   int v, p, c; /* value, priority, subtree size */
    Node *l, *r; /* left and right subtrees */

    Node(int val, int priority = rand())
    {   v = val;
        p = priority;
        l = r = 0;
    }
};

Size of subtree rooted at node x.

int count(Node *x)
{   return x ? x->c : 0;
}

Merge.

void join(Node **x, Node *left, Node *right)
{   if(left == 0 || right == 0)
        *x = left ? left : right;
    else
    {   if(left->p > right->p)
        {   join(&left->r, left->r, right);
            *x = left;
        }
        else
        {   join(&right->l, left, right->l);
            *x = right;
        }
        (*x)->c = count((*x)->l) + count((*x)->r) + 1;
    }
}

Split.

void split(Node *x, int k, Node ** left, Node **right)
{   Node *tmp;
    if(x == 0) *left = *right = 0;
    else
    {   int c = count(x) - count(x->r);
        if(k < c)
        {   split(x->l, k, left, &tmp);
            *right = x, (*right)->l = tmp;
        }
        else
        {   split(x->r, k - c, &tmp, right);
            *left = x, (*left)->r = tmp;
        }
        x->c = count(x->l) + count(x->r) + 1;
    }
}

Insert element.

void insert(Node **t, int k, int v)
{   Node *n = new Node(v);
    Node *left, *right;
    split(*t, k, &left, &right);
    join(t, left, n);
    join(t, *t, right);
}

Remove element.

void remove(Node **t, int k)
{   Node *left, *mid, *tmp, *right;
    split(*t, k, &left, &mid);
    split(mid, k + 1, &tmp, &right);
    join(t, left, right);
}
\$\endgroup\$
2
  • 3
    \$\begingroup\$ Looks more like a C review is needed. There is no real C++ in this code. Adding the C tag so it gets more exposure. \$\endgroup\$ Nov 21 '14 at 19:30
  • \$\begingroup\$ Yes, thanks. Code is for competitive programming and I use c++ for that..that's why the includes are c++. \$\endgroup\$
    – mrk
    Nov 22 '14 at 10:59
3
\$\begingroup\$

You should be giving your variables proper names. This would really improve the readability of your code. After all, code is read more times than it is written. As an outsider not all too well versed in advanced data structures, it's really hard to tell what k or v is supposed to be. Your code will effectively be self documenting if you change c and all other one character identifiers to something more reasonable like subtree_size or at least subsize. You won't need comments like /* left and right subtrees */.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.