一、你的splay都能做什么

1、伸展

Splay树的核心操作是伸展（Splay），在每次访问某个节点之后，将该节点从当前位置旋转并移动到根节点位置。通过不断地旋转和移动，可以实现对节点的自适应调整，使得频繁访问的节点处于更接近根节点的位置，进而优化了查找、插入、删除等操作的效率。

2、插入和删除

在Splay树中，节点的插入和删除操作和普通的二叉搜索树是类似的。对于插入操作，我们首先将要插入的节点插入到原来的二叉搜索树中，然后进行伸展操作，将新增节点旋转并移动到根节点的位置。对于删除操作，则需要先进行查找操作找到要删除的节点，然后将该节点删除，并对其父亲节点进行伸展操作，将其旋转并移动到根节点的位置。

3、区间查询

Splay树支持区间查询的功能，可以快速查找指定区间内的最大值、最小值、总和等信息。实现区间查询的方法是，先将区间的端点到达根节点的位置，然后将它们的LCA（最近公共祖先）旋转到根节点，此时LCA的左子树和右子树就分别代表了两个区间，通过在Splay树上求出这两个区间的信息，即可得到所需结果。

4、区间修改

除了区间查询，Splay树还支持区间修改的操作，可以对指定区间内的节点值进行修改。实现区间修改的方法是，将区间的端点到达根节点的位置，然后将它们的LCA旋转到根节点，在LCA下的子树内对所有节点递归进行修改。

二、splay概述

1、splay简介

首先，伸展树(splay tree)是一颗二叉搜索树，它的定义是建立在二叉搜索树之上，并且它是基于类似程序局部性原理的假设：一个节点在一次被访问后，这个节点很可能不久再次被访问。那么伸展树的做法就是在每次一个节点被访问后，我们就把它推到树根的位置。正像程序局部性原理的实际效率被广泛证明一样，伸展树在实际的搜索效率上也是非常高效的。尽管存在最坏情况下单次操作会花费O(N)的时间，但是这种情况并不是经常发生，而实际证明伸展树能够保证M次连续操作非常多花费O(MlogN)的时间。相比于平衡二叉树，伸展树有差不多的平均性能，其他的优势在于：不需要存储平衡信息。另外如果采用自顶向下的调整方式，还能简略额外的栈开销。

2、伸展的概念

伸展是一种特殊的旋转方式，它采用了类似于平衡二叉树的策略，如果查询节点可以通过两步旋转更快的到达根节点，则采用两步旋转法。所谓的单旋转，一字型，之字形，是根据父节点是否是根节点来划分的，并且是自底向上的思路。 如果查询节点的父节点是根节点，那么直接旋转该节点到根节点的位置。 如果查询节点的父节点不是根节点，那么该节点一定有祖父节点，那么就分为两种情况：

3、伸展树的代码实现

我们在实现的时候仅需要在一字型的时候进行像平衡二叉树的单旋操作，而单旋转和之字形只需要简单的链改变。我们的实现思路如下：

描述：在查询一个节点后进行伸展旋转，将其推到根节点位置输入：查找的节点的值x，伸展树树根root输出：新的树根初始化leftHeader=headerNode，rightHeader=headerNode初始化leftMax=leftHeader,rightMin=rightHeader循环    if xroot节点的值，说明在右子树        如果root.right等于null,说明右子树为空，查找失败            调整结束，跳出循环        如果x大于root.right的值，右一字型情况            root=rotateWithRightChilde(root)        leftMax.right=root        leftMax=root        root=root.right    else 等于的情况        中树根已经为x，直接跳出循环开始合并leftMax.right=root.leftrightMin.left=root.rightroot.left=leftHeader.rightroot.right=rightHeader.leftreturn root

在这里有个小细节，就是我们在rightMin=root，root=root.left的时候，rightMin保持的root的left依然存在 ，我这里之所以没有把它置null是因为在最后合并的时候会同一经rightMin.left置成root.right，而且没一轮如果符合条件，都会发生置换。我们的Java实现如下：

public BinaryNode splay(T x, BinaryNode root){        BinaryNode< T> headerNode=new BinaryNode<>(null);//头节点，随便定义其值        BinaryNoderightHeader=headerNode;        BinaryNodeleftHeader=headerNode;        BinaryNodeleftMax=leftHeader;        BinaryNoderightMin=rightHeader;        if(root==null)            return root;        while(true) {            if(x.compareTo(root.element)<0) {                if(root.left==null)                    break;                if(x.compareTo(root.left.element)<0)                    root=rotateWithLeftChild(root);                rightMin.left=root;                rightMin=root;                root=root.left;            }else if(x.compareTo(root.element)>0) {                if(root.right==null)                    break;                if(x.compareTo(root.right.element)>0)                    root=rotateWithRightChild(root);                leftMax.right=root;                leftMax=root;                root=root.right;            }else //等于的情况，结束循环                break;        }        //开始合并        leftMax.right=root.left;        rightMin.left=root.right;        root.left=leftHeader.right;        root.right=rightHeader.left;        return root;    }}

三、平衡二叉树简介

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

比如下图就是一个示例的Treap：

简单理解是话，平衡树就是在二叉搜索树上增加了一个weight值。因此Treap的大部分操作都和二叉搜索树是一样的，少数区别在于每次插入一个节点后，需要对树的结构进行调整。因为每一个节点的weight值不一样，当我们按照key值插入一个节点后，这个节点有可能不满足weight值的要求。

对于如何调整，首先我们来看一个最简单的例子：

如图所示的一个Treap有三个节点，其中根的右儿子节点是新插入的。假设我们一开始想要让Treap满足小根堆的性质，即weight值越小越在堆顶。那么我们需要在不改变key值顺序的情况下，对节点进行变形，使得weight值满足性质。这一步骤被称为旋转，对于例子，其旋转之后的形态为：

根据旋转的方向不同，旋转分为两种：左旋和右旋。在例子中是将右儿子节点旋转至根，所以称为左旋。反之将左儿子节点旋转至根，称为右旋。那么这个旋转具体的过程，我们可以对应旋转前后的图来分析。首先是左旋操作：

它的过程有如下几步：

延伸阅读1：splay的优点

上一篇

emtp文件用什么软件打开?

下一篇

为什么Python运行速度慢?