秒懂算法 | Treap 树

作者：TiAmo

2023-03-31
江苏
本文字数：4325 字
阅读完需：约 14 分钟

数据结构是数据的组织形式和访问方法，前文介绍了基础数据结构，在基础上发展出了很多高级数据结构，它们原理复杂，编程困难。
为什么需要这么多高级数据结构？这是在特定应用背景下高效处理数据的需要。基础数据结构不够强大，像数组、栈、队列这样的线性结构，计算复杂度为 O(n)，在面对大量数据时力不从心；二叉树、堆、哈希很高效，但是它们过于简单，在处理很多特定问题时操作不便。高级数据结构与某些应用背景紧密结合，能高效地解决问题。例如，集合问题用并查集；区间问题用树状数组、线段树、分块、莫队算法；混合问题用块状链表；动态查询用平衡树，等等。
本篇介绍 Treap 树。

Treap 树也是一种原理比较简单的 BST。Treap 是一个合成词，把 Tree 和 Heap 各取一半组合而成，Treap 是树和堆的结合，通常翻译成树堆。

Treap 树的操作基于“键值+优先级”。BST 的每个节点上存有一个元素，把元素的值称为“键值”，这是所有 BST 都有的。除此之外，Treap 树为每个节点人为添加了一个称为优先级的权值。对于键值，这棵树是一棵 BST；对于优先级，这棵树是一个堆。堆的特征是在这棵树的任意子树上，根节点的优先级最大。对于树上的任意一组节点：父亲 fa、左孩子 ls、右孩子 rs，满足以下两个条件。

(1) 键值(key)满足 BST 的要求：ls.key≤fa.key≤rs.key。

(2) 优先级(pri)满足堆的要求：fa.pri≥max{ls.pri，rs.pri}。

提示/

Treap 树的核心思想是用优先级维护二叉树的平衡性。

01、Treap 树的性质

Treap 树的重要性质：若每个节点的键值、优先级已经事先确定而且不同，那么建立的 BST 的形态是唯一的，与节点的插入顺序没有关系。可以把每个点的(键值，优先级)看作它在平面上的坐标(x，y)，坐标确定了它的位置。可简单地概括为节点的键值 x 限定了它在二叉树上的横向位置，优先级 y 限定了它的纵向位置。若优先级是随机产生的，那么在概率上就实现了二叉树的平衡。

下面用 7 个节点举例说明建树过程和 Treap 树的形态唯一性，如图 1 所示。节点的键值分别为{a，b，c，d，e，f，g}，优先级分别为{6，5，2，7，3，4，1}。图 4.58(a)的纵向是优先级，横向是键值；图 1(b)按 BST 的规则建了一棵树，从堆的角度看，它是一个最大堆(也可以用小根堆)；图 1(c)是形成的 Treap 树。显然，由于每个节点被键值和优先级确定了位置，Treap 树的形态是唯一的。

■ 图 1 Treap 树的形态唯一性

需要注意，所谓“Treap 树的形态唯一性”，是指已经提前确定所有节点的键值、优先级之后，建的树的形态是唯一的。但是在一般情况下，建 Treap 树是逐个点加入树上的，每个点的优先级是动态分配的，所以 Treap 树的最后形态并不能提前预知。不过，当处理完毕之后，这棵 Treap 树的新形态是确定唯一的。

给节点加上优先级是 Treap 树解决二叉树平衡的核心思想，合适的优先级能产生一个平衡的 BST。如何产生优先级？最简单的方法是对每个节点的优先级进行随机赋值，那么生成的 Treap 树的形态也是随机的。虽然不能保证生成的 Treap 树是完美的平衡，但是从概率期望上看，它的插入、删除、查找的时间复杂度都为 O(log₂n)。

如果预先知道所有节点的键值，那么建树很简单：先按键值排序，然后从键值最小的开始，从左到右逐个向树上加入节点，加入时按优先级(或者已知，或者随机生成)在纵向上调整形态。这就是笛卡儿树，它的建树复杂度为 O(n)。

更常见的情况是需要动态加入新的节点，并不能预先知道键值和优先级。做法是每读入一个新键值，为它分配一个随机的优先级，插入树中，插入时动态调整树的结构，使它仍然是一棵 Treap 树。此时建一棵 n 个节点的树，复杂度为 O(nlog₂n)。

如何调整和维护 Treap 树？有两种方法：①旋转法；②FHQ。两种方法的计算复杂度都为 O(log₂n)。旋转法是经典方法，FHQ 是近几年开始流行的新技术，FHQ 不仅比旋转法编码简单，而且能用于区间翻转、移动、持久化等场合。

02、基于旋转法的 Treap 树操作

下面用旋转法实现几个基本操作：插入节点、删除节点、排名、第 k 大、前驱和后继。

1. 插入节点

把新节点 k 插入 Treap 树的过程有两步。

(1) 用朴素的插入方法，把 k 按键值大小插入一个空的叶子节点。

(2) 为 k 随机分配一个优先级，如果 k 的优先级违反了堆的性质，即它的优先级比父节点 o 高，那么让 k 向上走代替父节点 o，得到一棵新的 Treap 树。

步骤(2)中的调整过程用到了一种技巧——旋转，包括左旋和右旋。观察图 2，新节点 k 刚插入时，它有父节点 o 和子节点 x、b。当 k 旋转到 o 的上面时，其他节点 a、x、b 保存原来的相对位置不变，以 a、x、b 为根的子树也随之同步移动。注意，不管是左旋还是右旋，树的中序遍历保持不变，这是 BST 的特征。

■ 图 2 Treap 树的旋转(把 k 旋转到根)

旋转法插入节点的代码如下，代码中定义的节点名称 o、k 与图 2 的节点名称对应。


void rotate(int &o,int d){    //参考图示理解。d=0右旋，d=1左旋    int k;    if(d == 1) {              //左旋，把o的右儿子k旋到根部        k = t[o].rs;          //rs: rson，右儿子        t[o].rs = t[k].ls;    //图中的x        t[k].ls = o;    }    else {                    //右旋，把o的左儿子k旋到根部        k = t[o].ls;        t[o].ls = t[k].rs;    //图中的x        t[k].rs = o;    }  t[k].size = t[o].size;  Update(o);  o = k;                    //新的根是k}

复制代码

下面用一个例子说明插入的过程。设初始 BST 是{a，b，c}，插入新节点 d。图 3(a)是初始 BST；图 3(b)按键值找到空叶子，插入 d；图 3(c)中 d 的优先级比父节点 c 高，把 c 左旋，上升；图 3(d)中 d 的优先级比新的父节点 b 高，继续左旋上升；3(e)再次左旋上升，完成了新的 Treap 树。注意在旋转的过程中，原来的节点 a、b、c 的相对位置保持不变。

■ 图 3 Treap 树的插入和调整

2. 删除节点

如果待删除的节点 x 是叶子节点，直接删除。如果待删除的节点 x 有两个子节点，那么找到优先级最大的子节点，把 x 向相反的方向旋转，也就是把 x 向树的下层调整，直到 x 被旋转到叶子节点，然后直接删除。

用旋转法处理 Treap 树的插入和删除，会不会导致出现一棵不平衡的 Treap 树？答案是不会，因为 Treap 的形态完全由留在树上的节点的键值和优先级决定，在概率上它仍然是平衡的。

3. 排名

“排名”和“求第 k 大数”一般被称为“名次树问题”，是 BST 的典型应用，在任何一种 BST 上都容易用递归遍历得到，Treap 树也常用来求名次。它们都用到了节点的 size 值，即以这个节点为根的子树上的节点总数。

求数字 x 的排名。从根节点开始递归查找，递归到节点 u 时：若 u 的键值大于或等于 x，x 在 u 的左子树上，继续递归 u 的左子树；若 u 的键值小于 x，x 在 u 的右子树上，递归 u 的右子树，并加上 u 的左子树的 size 值。

4. 求第 k 大数

根据节点的 size 值不断递归整棵树，求得第 k 大数。

5. 前驱和后继

前驱是求比 x 小的数，后继是求比 x 大的数，计算过程与排名的过程类似。

用例 1 给出 Treap 树代码，实现上述操作。

//用旋转法实现Treap树#include<bits/stdc++.h>using namespace std;const int M=1e6+10;int cnt = 0;             //t[cnt]: 最新结点的存储位置struct Node{int ls,rs;           //左右儿子int key,pri;         // key：键值；pri：随机的优先级int size;            //当前结点为根的子树的结点数量，用于求第k大和rank}t[M];                   //tree[]，存树void newNode(int x){     //初始化一个新结点cnt++;        //从t[1]开始存储结点，t[0]被放弃。若子结点是0，表示没有子结点t[cnt].size = 1;t[cnt].ls = t[cnt].rs = 0;  //0表示没有子结点t[cnt].key = x;             //key: 键值t[cnt].pri = rand();        //pri：随机产生，优先级}void Update(int u){             //更新以u为根的子树的sizet[u].size = t[t[u].ls].size + t[t[u].rs].size+1;}void rotate(int &o,int d){      //旋转，参考图示理解。d=0右旋，d=1左旋int k;    if(d==1) {                  //左旋，把o的右儿子k旋到根部       k=t[o].rs;       t[o].rs=t[k].ls;//图中的x       t[k].ls=o;    }    else {                      //右旋，把o的左儿子k旋到根部       k=t[o].ls;       t[o].ls=t[k].rs; //图中的x       t[k].rs=o;    }t[k].size=t[o].size;Update(o);o=k;                       //新的根是k}void Insert(int &u,int x){if(u==0){newNode(x);u=cnt;return;}    //递归到了一个空叶子，新建结点t[u].size++;if(x>=t[u].key)    Insert(t[u].rs,x); //递归右子树找空叶子，直到插入else               Insert(t[u].ls,x); //递归左子树找空叶子，直到插入if(t[u].ls!=0 && t[u].pri>t[t[u].ls].pri) rotate(u,0);if(t[u].rs!=0 && t[u].pri>t[t[u].rs].pri) rotate(u,1);Update(u);}void Del(int &u,int x){t[u].size--;if(t[u].key==x){if(t[u].ls==0&&t[u].rs==0){u=0; return;}if(t[u].ls==0||t[u].rs==0){u=t[u].ls+t[u].rs; return;}if(t[t[u].ls].pri < t[t[u].rs].pri){     rotate(u,0); Del(t[u].rs, x); return;}     else{ rotate(u,1); Del(t[u].ls, x); return;}  }  if(t[u].key>=x) Del(t[u].ls,x);  else            Del(t[u].rs,x);  Update(u);}int Rank(int u,int x){   //排名，x是第几名  if(u==0)  return 0;  if(x>t[u].key) return t[t[u].ls].size+1+Rank(t[u].rs, x);  return Rank(t[u].ls,x);}int kth(int u,int k){    //第k大数是几?  if(k==t[t[u].ls].size+1) return t[u].key;   //这个数为根  if(k> t[t[u].ls].size+1) return kth(t[u].rs,k-t[t[u].ls].size-1);//右子树  if(k<=t[t[u].ls].size)   kth(t[u].ls,k);    //左子树}int Precursor(int u,int x){  if(u==0)   return 0;  if(t[u].key>=x)  return Precursor(t[u].ls,x);  int tmp = Precursor(t[u].rs,x);  if(tmp==0)  return t[u].key;  return tmp;}int Successor(int u,int x){  if(u==0)   return 0;  if(t[u].key<=x)  return Successor(t[u].rs,x);  int tmp = Successor(t[u].ls,x);  if(tmp==0)   return t[u].key;  return tmp;}int main(){  srand(time(NULL));  int root = 0;           //root是整棵树的树根，0表示初始为空  int n;  cin>>n;  while(n--){        int opt,x; cin >> opt >> x;        switch (opt){            case 1: Insert(root,x);    break;            case 2: Del(root,x);       break;            case 3: printf("%d\n",Rank(root,x)+1);    break;            case 4: printf("%d\n",kth(root,x));       break;            case 5: printf("%d\n",Precursor(root,x)); break;            case 6: printf("%d\n",Successor(root,x)); break;        }  }  return 0;}

复制代码

发布于: 刚刚阅读数: 3

原文链接:【http://xie.infoq.cn/article/6dd579f1548019bd87dd75c3f】。文章转载请联系作者。

TiAmo

关注

有能力爱自己，有余力爱别人！ 2022-06-16 加入

CSDN全栈领域优质创作者，万粉博主；阿里云专家博主、星级博主、技术博主、阿里云问答官，阿里云MVP；华为云享专家；华为Iot专家；亚马逊人工智能自动驾驶（大众组）吉尼斯世界纪录获得者

发布

暂无评论

创作场景