首页 > 其他分享 >Treap

Treap

时间:2023-12-16 20:44:22浏览次数:30  
标签:Node return val int Treap child root

前置:BST

\(Treap=BST+heap\),通过额外维护堆的性质来避免退化成链的问题。

与\(BST\)中结构释义相同的部分不做解释。

\(priority\)表示优先级,即该节点在小根堆中的值,\(child[0]\)表示左孩子,\(child[1]\)表示右孩子。

\(public\)中,\(empty\):时间复杂度\(O(1)\)。

其余操作时间复杂度均为\(O(logn)\)。

class Treap
{
private:
    int INF = 0x3f3f3f3f;
    struct Node
    {
        int key, size = 1, count = 1, priority = rand();
        Node *child[2] = {nullptr, nullptr};
        Node *&left = child[0], *&right = child[1];
        Node(int key) : key(key) {}
        void UpdSize()
        {
            size = count + (left ? left->size : 0) + (right ? right->size : 0);
        }
    };

    Node *root = nullptr;

    enum rot_type{LF = 1, RT = 0}; // 左旋和右旋
    void rotate(Node *&root, rot_type dir) // 旋转以维护小根堆的性质
    {
        Node *tmp = root->child[dir];
        root->child[dir] = tmp->child[!dir];
        tmp->child[!dir] = root;
        root->UpdSize(), tmp->UpdSize();
        root = tmp;
    }

    Node *FindMinNode(Node *root) // 在以root为根的子树中查找最小节点
    {
        if (!root) return root;
        while (root->left) root = root->left;
        return root;
    }

    Node *FindMaxNode(Node *root) // 在以root为根的子树中查找最大节点
    {
        if (!root) return root;
        while (root->right) root = root->right;
        return root;
    }

    int FindMin(Node *root) // 在以root为根的子树中查找最小键值
    {
        root = FindMinNode(root);
        return (root ? root->key : INF);
    }

    int FindMax(Node *root) // 在以root为根的子树中查找最大键值
    {
        root = FindMaxNode(root);
        return (root ? root->key : INF);
    }

    int count(Node *root, int val) // 在以root为根的子树中查找键值为val的数量
    {
        if (!root) return 0;
        if (root->key == val) return root->count;
        else if (val < root->key) return count(root->left, val);
        else return count(root->right, val);
    }

    void insert(Node *&root, int &val) // 在以root为根的子树中插入键值为val的节点
    {
        if (!root) root = new Node(val);
        else if (val < root->key) 
        {
            insert(root->left, val);
            if (root->left->priority < root->priority) rotate(root, RT);
        }
        else if (val > root->key)
        {
            insert(root->right, val);
            if (root->right->priority < root->priority) rotate(root, LF);
        }
        else root->count++;
        if (root) root->UpdSize();
    }

    void erase(Node *&root, int val, int cnt) // 在以root为根的子树中删除cnt个键值为val的节点
    {
        if (val < root->key) erase(root->left, val, cnt);
        else if (val > root->key) erase(root->right, val, cnt);
        else 
        {
            if (root->count > cnt) root->count -= cnt;
            else 
            {
                Node *tmp = root;
                if (!root->left)
                {
                    root = tmp->right;
                    delete tmp;
                } 
                else if (!root->right) 
                {
                    root = tmp->left;
                    delete tmp;
                } 
                else 
                {
                    rot_type dir = (root->left->priority < root->right->priority ? RT : LF);
                    rotate(root, dir);
                    erase(root->child[!dir], val, cnt);
                }
            }
        }
        if (root) root->UpdSize();
    }

    int rank(Node *root, int val) // 计算键值为val的排名(排名定义为比当前键值小的键值的个数加一)
    {
        if (!root) return 1;
        if (val == root->key) return (root->child[0] ? root->child[0]->size : 0) + 1;
        if (val < root->key) return rank(root->child[0], val);
        return rank(root->child[1], val) + root->count + (root->child[0] ? root->child[0]->size : 0);
    }

    int kth(Node *root, int k) // 计算排名为k的键值
    {
        if (!root) return INF;
        int leftSize = (root->child[0] ? root->child[0]->size : 0);
        if (leftSize >= k) return kth(root->child[0], k);
        if (leftSize + root->count >= k) return root->key;
        return kth(root->child[1], k - leftSize - root->count);
    }
public:
    bool empty(){return !root;}
    int Max(){return (root ? FindMax(root) : INF);}
    int Min(){return (root ? FindMin(root) : INF);}
    void insert(int val){insert(root, val);}
    int count(int val){return count(root, val);}
    void erase(int val, int cnt = 1){cnt = min(cnt, count(val)); if (cnt) erase(root, val, cnt);}
    int rank(int val){return rank(root, val);}
    int kth(int k){return kth(root, k);}
    int prev(int val){return kth(rank(val) - 1);}
    int next(int val){return kth(rank(val + 1));}
} Tp;

标签:Node,return,val,int,Treap,child,root
From: https://www.cnblogs.com/xiojoy/p/17908349.html

相关文章

  • 平衡树(无旋Treap,范浩强树)学习笔记
    平衡树:YYDS以下是常见的平衡树/要用平衡树实现的算法:Treap(有旋/无旋)Splay树WBLT(WeightBalancedLeafyTree,重量平衡线段树)SBT(SizeBalancedTree,陈启峰树)AVL树B树、B+树笛卡尔树红黑树、左偏红黑树、AA树替罪羊树\(\to\)K-DTree(k-DimensionTree)LT(LeafyTree,平......
  • Treap 学习笔记
    二叉查找树二叉查找树是一棵有点权的二叉树,具有以下几个特征:左孩子的权值小于父亲的权值右孩子的权值大于父亲的权值中序遍历及从小到大排序二叉查找树支持以下几个操作:插入一个数删除一个数找一个数的前驱找一个数的后继询问一个数的排名询问排第几名的数二叉查......
  • Treap
    概述FHQTreap基于Treap发明的“无旋Treap”,代码短,易理解且速度快(在OI算是很优秀的算法了)。FHQTreap核心函数只有两个,分别是分裂和合并。字面意思,就是将某一棵二叉查找树按某种要求分裂成两个或将两个合并成一个。实现变量维护变量名功能root记录所维护......
  • 算法笔记(2)FHQtreap
    原发布于我的个人博客前言FHQtreap绝对是平衡树里最好写,最实用的,他几乎能做所有splay或其它平衡树能做的事,还能可持久化!这篇文章将会介绍FHQtreap的基本操作和维护区间的操作,并附上例题。基本操作FHQtreap的基本操作只有两个,分裂和合并。有些读者可能会问,分裂和合并和平衡树......
  • 【学习笔记】FHQ-Treap
    前置知识:二叉搜索树与二叉堆。1.简介Treap,即Tree+Heap,它的每个结点上存储着一个索引\(key\)和一个值\(val\),其中索引满足二叉堆的性质,值满足二叉搜索树的性质,且索引是随机的。Treap就是通过上述的性质,使树达到平衡。至于为什么索引是随机的,其实很简单:我们插入的每个数的......
  • Atcoder Beginner Contest 324 G Generate Arrays 题解-Treap
    为了更好的阅读体验,请点击这里题目链接套上平衡树板子就能做的很快的题,然后因为是指针存树,因此交换只需要把序列大小较小的挨个拿出来插到相应的地方即可。复杂度\(O(N\log^2N)\)。但是一定要记住不可以直接使用std::swap交换包含带有指针的类的实例(如代码中的Treap类)!......
  • Treap引入
    前置知识treap是由BST和heap组合而成的数据结构,这一点也体现在它的名字上:treap=tree+heapBST中,每个节点的左儿子都比它小,右儿子都比它大,可以实现有序的遍历,但是可能因为数据特殊的排列方式,而退化为线性heap中,每个父节点都是当前子树内权值最大(或最小)的点。在BST的基础上加一个......
  • BST-Treap名次树指针实现板子 Ver2.0
    为了更好的阅读体验,请点击这里这里只有板子没有原理QWQ可实现1.插入x数2.删除x数(若有多个相同的数,只删除一个)3.查询x数的排名(排名定义为比当前数小的数的个数+1)4.查询排名为x的数5.求x的前驱(前驱定义为小于x,且最大的数)6.求x的后继(后继定义为大于x,且......
  • 弱势无图解FHQ-Treap 及各种乱七八糟的错误方法
    众所周知,FHQ-Treap是一个码量少,可区间翻转,能持久化的treap(只是常熟略大)像我这种蒟蒻,想调处有旋Treap或者Splay肯定要个114514年以下可能以FHQ代表FHQ-Treap(逃前置芝士treap的节点拥有两个权值,一个是值,一个是优先级。优先级满足堆的性质,值满足二叉搜索树的性质。当两个权值相......
  • Treap
    BST\(v_i\)表示点权,\(x\)表示当前点,\(L\)表示左子树,\(R\)表示右子树在普通二叉树的基础上多一个条件对于\(p\inL\),满足\(v_p\leqv_x\)对于\(q\inR\),满足\(v_x<v_q\)Treap但是这样如果BST是一条链的话就退化\(O(n)\),而且很容易卡,考虑TreapTreap就是在普通B......