简单的平衡树-treaps

在普通的二叉树中,由于没有进行处理,导致整个树出现不平衡,然而,可将堆的思想放入二叉树中,这样在一定程度上会出现二叉搜索树的平衡,这样就得到了一个新的数据结构treap.在treap中不仅有插入的键值,还附带一个堆的值段:priority,键值按照二叉树来进行处理,而priority则通过大顶堆或小顶堆的性质进行处理,如大顶堆则有一下特征:

1.如果v是u的左孩子,则key[u] > key[v];

2.如果v是u的右孩子,则key[u] < key[v];

3.如果v是u的孩子,则priority[u] > priority[v].

可以证明treap的高位lgn,搜索时间为lgn,不过为了达到这样的性质,一般priority采用随机获取.

下面是插入算法:

与普通的二叉树方法类似,先查找到合适的节点,插入之后,进行堆的属性调整.

int treap_insert(struct treap_root *root,struct treap_node *node)
{
    int res = 0;
    struct treap_node *p;

    p = _treap_find(root,node->value);


    if(!p)
    {
        root->root = node;
    }
    else
    {
        if(p->value > node->value)
        {
            p->left = node;
            node->parent = p;
        }
        else
        {
            p->right = node;
            node->parent = p;
        }

        //max heap or min heap
        if((root->flag && node->priority>p->priority) || \
            (!root->flag && node->priority < p->priority) )
        _treap_adjust(root,node);
    }
    root->length ++;
    return res;
}

调整与普通的堆不同,这里需要采用旋转来保证堆中的二叉树性质.

void _treap_adjust(struct treap_root *root,struct treap_node *node)
{
    long lvalue,lpriority;
    struct treap_node *p,*q;
    long rvalue,rpriority;

    p = node;
    q = p->parent;

    while(p&&q)
    {
        if(root->flag && q->priority >= p->priority) break;

        if(!root->flag && q->priority <= p->priority) break;

        //max heap
        if(root->flag && q->priority < p->priority)
        {
            if(q->left == p) right_rotate(root,q);
            else         left_rotate(root,q);
        }
        //min heap
        if(!root->flag && q->priority > p->priority)
        {
            if(q->left == p)
                    right_rotate(root,q);
            else        left_rotate(root,q);
        }
        q = p->parent;
    }

}

二叉树的删除:

先查找到后继,进行替换之后,进行堆的性质调整.

int treap_delete(struct treap_root *root,struct treap_node *node)
{
    struct treap_node *p,*q;

    q = NULL;

    if(!root->length) return 0;

    p = treap_successor(node);

    //no right child
    if(!p) {
        q = node->left;
        if(root->root == node) root->root = q;
        else
        if(node->parent->left == node) {
            node->parent->left = q;
        } else {
            node->parent->right = q;
        }

        if(q) q->parent = node->parent;
        root->length --;
        return 0;
    }

    if(root->root == node) root->root = p;
    else
    if(node->parent->left == node) node->parent->left = p;
    else                   node->parent->right = p;

    q = p->right;

    if(p->parent!=node)
    {
    if(p->parent->left == p) p->parent->left = q;
    else            p->parent->right = q;
    }

    if(q&&p->parent != node)
    q->parent = p->parent;

    p->left = node->left;

    if(node->left)
    node->left->parent = p;

    if(node->right != p)
    {
    p->right = node->right;

    if(node->right)
    node->right->parent = p;

    }

    p->parent = node->parent;

    __adjust_child(root,p);
    root->length --;
    return 0;
}

这里进行堆的调整,也需要进行旋转控制,来代替普通的交换数值

void __adjust_child(struct treap_root *root,struct treap_node *node)
{
    struct treap_node *left = node->left;
    struct treap_node *right = node->right;
    struct treap_node *temp = node;

    //max heap
    if(root->flag) {
    if(left && left->priority > temp->priority)     temp = left;
    if(right && right->priority > temp->priority)   temp = right;
    //min heap
    } else {
    if(left && left->priority < temp->priority) temp = left;
    if(right && right->priority < temp->priority) temp = right;
    }

    if(temp != node)
    {
        if(node->left == temp) right_rotate(root,node);
        else            left_rotate(root,node);
        __adjust_child(root,node);
    }
}

 treaps.rar   

参考资料:

1.算法导论

2.堆的数据结构

3.treap的作者主页: