数据结构是数据的组织形式和访问方法，前文介绍了基础数据结构，在基础上发展出了很多高级数据结构，它们原理复杂，编程困难。
为什么需要这么多高级数据结构？这是在特定应用背景下高效处理数据的需要。基础数据结构不够强大，像数组、栈、队列这样的线性结构，计算复杂度为O(n)，在面对大量数据时力不从心；二叉树、堆、哈希很高效，但是它们过于简单，在处理很多特定问题时操作不便。高级数据结构与某些应用背景紧密结合，能高效地解决问题。例如，集合问题用并查集；区间问题用树状数组、线段树、分块、莫队算法；混合问题用块状链表；动态查询用平衡树，等等。
本篇介绍Treap树。
Treap树也是一种原理比较简单的BST。Treap是一个合成词，把Tree和Heap各取一半组合而成，Treap是树和堆的结合，通常翻译成树堆。
Treap树的操作基于“键值+优先级”。BST的每个节点上存有一个元素，把元素的值称为“键值”，这是所有BST都有的。除此之外，Treap树为每个节点人为添加了一个称为优先级的权值。对于键值，这棵树是一棵BST；对于优先级，这棵树是一个堆。堆的特征是在这棵树的任意子树上，根节点的优先级最大。对于树上的任意一组节点：父亲fa、左孩子ls、右孩子rs，满足以下两个条件。
提示/
Treap树的核心思想是用优先级维护二叉树的平衡性。
01
Treap树的性质
Treap树的重要性质：若每个节点的键值、优先级已经事先确定而且不同，那么建立的BST的形态是唯一的，与节点的插入顺序没有关系。可以把每个点的(键值，优先级)看作它在平面上的坐标(x，y)，坐标确定了它的位置。可简单地概括为节点的键值x限定了它在二叉树上的横向位置，优先级y限定了它的纵向位置。若优先级是随机产生的，那么在概率上就实现了二叉树的平衡。
下面用7个节点举例说明建树过程和Treap树的形态唯一性，如图4.58所示。节点的键值分别为{a，b，c，d，e，f，g}，优先级分别为{6，5，2，7，3，4，1}。图4.58(a)的纵向是优先级，横向是键值；图4.58(b)按BST的规则建了一棵树，从堆的角度看，它是一个最大堆(也可以用小根堆)；图4.58(c)是形成的Treap树。显然，由于每个节点被键值和优先级确定了位置，Treap树的形态是唯一的。
■ 图4.58Treap树的形态唯一性
需要注意，所谓“Treap树的形态唯一性”，是指已经提前确定所有节点的键值、优先级之后，建的树的形态是唯一的。但是在一般情况下，建Treap树是逐个点加入树上的，每个点的优先级是动态分配的，所以Treap树的最后形态并不能提前预知。不过，当处理完毕之后，这棵Treap树的新形态是确定唯一的。
给节点加上优先级是Treap树解决二叉树平衡的核心思想，合适的优先级能产生一个平衡的BST。如何产生优先级？最简单的方法是对每个节点的优先级进行随机赋值，那么生成的Treap树的形态也是随机的。虽然不能保证生成的Treap树是完美的平衡，但是从概率期望上看，它的插入、删除、查找的时间复杂度都为O(log2n)。
如果预先知道所有节点的键值，那么建树很简单：先按键值排序，然后从键值最小的开始，从左到右逐个向树上加入节点，加入时按优先级(或者已知，或者随机生成)在纵向上调整形态。这就是笛卡儿树，它的建树复杂度为O(n)。
更常见的情况是需要动态加入新的节点，并不能预先知道键值和优先级。做法是每读入一个新键值，为它分配一个随机的优先级，插入树中，插入时动态调整树的结构，使它仍然是一棵Treap树。此时建一棵n个节点的树，复杂度为O(nlog2n)。
如何调整和维护Treap树？有两种方法：①旋转法；②FHQ。两种方法的计算复杂度都为O(log2n)。旋转法是经典方法，FHQ是近几年开始流行的新技术，FHQ不仅比旋转法编码简单，而且能用于区间翻转、移动、持久化等场合。
02
基于旋转法的Treap树操作
下面用旋转法实现几个基本操作：插入节点、删除节点、排名、第k大、前驱和后继。
1. 插入节点
把新节点k插入Treap树的过程有两步。
(1) 用朴素的插入方法，把k按键值大小插入一个空的叶子节点。
(2) 为k随机分配一个优先级，如果k的优先级违反了堆的性质，即它的优先级比父节点o高，那么让k向上走代替父节点o，得到一棵新的Treap树。
步骤(2)中的调整过程用到了一种技巧——旋转，包括左旋和右旋。观察图4.59，新节点k刚插入时，它有父节点o和子节点x、b。当k旋转到o的上面时，其他节点a、x、b保存原来的相对位置不变，以a、x、b为根的子树也随之同步移动。注意，不管是左旋还是右旋，树的中序遍历保持不变，这是BST的特征。
■ 图4.59Treap树的旋转(把k旋转到根)
旋转法插入节点的代码如下，代码中定义的节点名称o、k与图4.59的节点名称对应。
下面用一个例子说明插入的过程。设初始BST是{a，b，c}，插入新节点d。图4.60(a)是初始BST；图4.60(b)按键值找到空叶子，插入d；图4.60(c)中d的优先级比父节点c高，把c左旋，上升；图4.60(d)中d的优先级比新的父节点b高，继续左旋上升；4.60(e)再次左旋上升，完成了新的Treap树。注意在旋转的过程中，原来的节点a、b、c的相对位置保持不变。
■ 图4.60Treap树的插入和调整
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大的数，计算过程与排名的过程类似。