Treap(数堆)

作者: _SilverBullet | 来源:发表于2016-07-03 16:12 被阅读259次

定义

数堆名字取了Tree和Heap各一半,即Treap,是二叉搜索树和堆合并构成的数据结构。而堆和二叉搜索树的性质是有冲突的,二叉搜索树满足左子树<根节点<右子树,而堆是满足根节点小于等于(或大于等于)左右子树。因此在Treap的数据结构中,并不是以单一的键值作为节点的数据域。Treap每个节点的数据域包含2个值,key和weight。key值,和原来的二叉搜索树一样,满足左子树<根节点<右子树weight值在Treap中满足堆的性质,根节点的weight值小于等于(或大于等于)左右儿子节点。

示例Treap:


Treap

代码实现为:

struct Node
{
    int key;
    int weight;
    Node * lchild;
    Node * rchild;
    Node * father;
}Node;

旋转操作

Treap大部分操作和二叉搜索树是一样的,区别是插入操作时weight值可能会不满足堆的性质,这时需要进行旋转操作
示例:

旋转之前

右儿子节点是新插入的,并不满足堆的性质,所以要对其进行调整,假设这个Treap满足小根堆的性质,则调整结果为

旋转之后

这样最小的weight值就位于根节点处。这个操作叫做旋转。

  • 将右儿子调整至根部的旋转叫做左旋
  • 将左儿子调整至根部的旋转叫做右旋

左旋操作

左旋操作

操作过程:

  1. 获取根节点A的右儿子节点B
  1. 将节点B的父亲节点信息更新为f,并更新节点f的子节点信息为B
  2. 将节点A的右儿子信息更新为节点B的左儿子D,同时将节点D的父亲节点信息更新为A
  3. 将节点B的左儿子信息更改为节点A,同时将节点A的父亲节点信息更改为B

代码实现为

void LeftRotate( Node &*A )
{
    // step1
    Node *B=A->rchild;
    // step2
    B->father=A->father;
    if( A->father->lchild == A )
        B->father->lchild=B;
    else
        B->father->rchild=B;
    // step3
    if( B->lchild!=NULL )
    {
        A->rchild=B->lchild;
        B->lchild->father=A;
    }
    // step4
    A->father=B;
    B->lchild=A;
}

右旋操作

右旋操作

其操作是左旋的镜像

  1. 获取根节点A的左儿子节点B
  1. 将节点B的父亲节点信息更新为f,并更新节点f的子节点信息为B
  2. 将节点A的左儿子信息更新为节点B的右儿子D,同时将节点D的父亲节点信息更新为A
  3. 将节点B的右儿子信息更改为节点A,同时将节点A的父亲节点信息更改为B

代码实现为

void RightRotate( Node &*A )
{
    // step1
    Node *B=A->lchild;
    // step2
    B->father=A->father;
    if( A->father->lchild == A )
        B->father->lchild=B;
    else
        B->father->rchild=B;
    // step3
    if( B->rchild!=NULL )
    {
        A->lchild=B->rchild;
        B->rchild->father=A;
    }
    // step4
    A->father=B;
    B->lchild=A;
}

总结

数堆的优势为:对于一般的二叉搜索树,在某些特殊情况下根据输入数据来建树有可能退化为一条链,比如一个依次增大的数列。而如果一棵二叉排序树的节点是按照随机顺序插入,得到的二叉排序树大多数情况下是平衡的,其期望高度是O(logn)。因此Treap利用weight值作为随机因子来调整二叉树的形状,使得在大部分情况下比直接通过数据建立的二叉树要平衡。
每一次查找的期望复杂度也会降低,总体的速度也就得到了提高。

相关文章

  • Treap(数堆)

    定义 数堆名字取了Tree和Heap各一半,即Treap,是二叉搜索树和堆合并构成的数据结构。而堆和二叉搜索树的性...

  • 平衡树

    Binary Index Tree AVL Splay Treap Scapegoat Tree Treap(wi...

  • 堆, 堆树(最小堆/最大堆) - heap, treap

    概念 堆是一种逻辑结构,树是一种存储结构,两者是不同层面的东西,就像“中国人"和“成年人”一样不矛盾。 heap和...

  • Treap

  • 平衡树Treap

    在学习平衡树Treap之前,我们先来了解什么是二叉查找树。 二叉查找树(BST:Binary Search Tre...

  • 非旋式Treap

    SuperMemo

  • 数据流的中位数

    使用双pq,一个大顶堆装小于middle的数,一个小顶堆装大于middle的数。大顶堆与小顶堆之间元素个数差不能大...

  • top K问题 处理解决办法

    先拿10000个数建堆,然后依次添加剩余元素,如果大于堆顶的数(10000中最小的),将这个数替换堆顶,并调整结构...

  • 2019-02-27 筛法求素数

    筛法: 一堆数 1.2.3.4.5.6.7.8.9.10.11.12.13.14.15.16.17.18.19.2...

  • (305)查找-折半查找

    概述 二分查找法主要是解决在“一堆数中找出指定的数”这类问题。而想要应用二分查找法,这“一堆数”必须有一下特征: ...

网友评论

    本文标题:Treap(数堆)

    本文链接:https://www.haomeiwen.com/subject/pnzqjttx.html