treap

#include <stdio.h>
#include <limits.h>
#include <stdlib.h>
/****dagendui****/
struct treap {
        int key;
        int perior;
        struct treap *lchild;
        struct treap *rchild;
};


void init_node(struct treap *node, int key)
{
        node->lchild = node->rchild = NULL;
        node->key = key;
        do {
                node->perior = rand()%100;
        } while (node->perior == INT_MIN || node->perior == INT_MAX);
}
inline struct treap *r_rotate(struct treap *node)
{
        struct treap *tmp = node;
        if (node->lchild && node->lchild->perior > node->perior) {
                tmp = node->lchild;
                node->lchild = tmp->rchild;
                tmp->rchild = node;
        }
        return tmp;
}
inline struct treap *l_rotate(struct treap *node)
{
        struct treap *tmp = node;
        if (node->rchild && node->rchild->perior > node->perior) {
                tmp = node->rchild;
                node->rchild = tmp->lchild;
                tmp->lchild = node;
        }
        return tmp;
}
struct treap *do_insert(struct treap *root, struct treap *node)
{
        if (!root) {
                return node;
        } else {
                if (node->key < root->key) {
                        root->lchild = do_insert(root->lchild, node);
                        return r_rotate(root);
                } else if (node->key > root->key) {
                        root->rchild = do_insert(root->rchild, node);
                        return l_rotate(root);
                } else {
                        fprintf(stderr, "this key has been bound\n");
                        free (node);
                        return root;
                }
        }

}

struct treap * insert(struct treap *root, int key)
{
        struct treap *node;
        node = malloc(sizeof(*node));
        init_node(node, key);
        return do_insert(root, node);
}
struct treap *do_del(struct treap *node)
{
        struct treap *tmp, *ret;

        node->perior = INT_MIN;
        ret = NULL;
        if (!node->lchild && !node->rchild) {
                free(node);
                return NULL;
        } else if (!node->lchild) {
                ret = l_rotate(node);
                ret->lchild = do_del(node);
        } else if (!node->rchild) {
                ret = r_rotate(node);
                ret->rchild = do_del(node);
        } else if (node->lchild->key < node->rchild->key) {
                ret = l_rotate(node);
                ret->lchild = do_del(node);
        } else {
                ret = r_rotate(node);
                ret->rchild = do_del(node);
        }
        return ret;
}
struct treap *del(struct treap *root, int key)
{
        struct treap *parent, *tmp;
        struct treap *ret;

        ret = root;
        parent = NULL;
        while (root) {
                if (key < root->key) {
                        parent = root;
                        root = root->lchild;
                } else if (key > root->key) {
                        parent = root;
                        root = root->rchild;
                } else
                        break;
        }

        if (!root) {
                fprintf(stderr, "del :this key is not bound\n");
                return ret;
        }

        tmp = do_del(root);
        if (parent) {
                if (parent->lchild == root)
                        parent->lchild = tmp;
                else
                        parent->rchild = tmp;
        } else
                ret = tmp;

        return ret;
}