高性能数据结构在竞技编程中的应用

22/26高性能数据结构在竞技编程中的应用第一部分高性能数据结构的应用场景 2第二部分线性表：队列和栈的应用 3第三部分树状数组：处理区间查询和更新 6第四部分线段树：区间查询、更新和求极值 9第五部分排序树：高效维护有序集合 13第六部分并查集：解决连通性问题 17第七部分哈希表：快速查找和映射 19第八部分伸展树：动态维护有序集合 22

第一部分高性能数据结构的应用场景关键词关键要点平衡树（平衡二叉搜索树）

1.保持树高平衡，通常为O(logn)，显著提升搜索、插入和删除操作的效率。

2.在竞技编程中常用于快速查询、动态插入和删除大量数据，如维护排名、统计区间内元素数量等。

3.常见变种包括红黑树、AVL树和伸展树，各有优缺点，根据具体场景选择。

动态规划

高性能数据结构在竞技编程中的应用场景

竞技编程是一项智力竞赛，要求参与者在有限的时间内解决复杂的问题。高性能数据结构对于在竞技编程中取得成功至关重要，因为它可以帮助参与者有效地组织和处理数据，并快速找到问题的解决方案。

具体应用场景：

1.动态规划

动态规划是一种解决复杂问题的技术，它将问题分解成较小的子问题，并记录子问题的最优解。在竞技编程中，动态规划通常用于解决需要维护多个状态的优化问题。高性能数据结构，如哈希表和字典，可用于快速查找和存储子问题的状态，从而提高动态规划算法的效率。

2.图论问题

图论问题涉及连接节点的边和顶点的集合。在竞技编程中，图论问题经常出现在路径查找、最小生成树和最大流问题中。高性能数据结构，如邻接表和邻接矩阵，可用于高效地存储和查询图结构，从而加快图论算法的执行速度。

3.字符串处理问题

字符串处理问题涉及对字符串进行操作，如匹配、搜索和替换。在竞技编程中，字符串处理问题经常出现在文本处理和字符串算法中。高性能数据结构，如后缀树和后缀阵列，可用于快速执行字符串匹配和搜索操作。

4.算法设计

算法设计涉及选择和实现用于解决特定问题的最佳算法。在竞技编程中，算法设计至关重要，因为参与者需要在有限的时间内找到最有效和最优的算法。高性能数据结构可以帮助参与者选择最适合问题的算法，并优化算法的性能。

常用的高性能数据结构包括：

*哈希表/字典：用于快速查找和存储键值对。

*堆：用于维护最大或最小元素。

*优先队列：用于根据优先级存储和检索元素。

*并查集：用于在并查集中高效地查找和合并集合。

*线段树：用于维护区间树，并高效地更新和查询区间。

*后缀树/后缀阵列：用于快速执行字符串匹配和搜索操作。

*邻接表/邻接矩阵：用于高效地存储和查询图结构。

通过熟练掌握这些高性能数据结构，竞技编程参与者可以优化算法的性能，提高解决问题的能力，并在比赛中取得更好的成绩。第二部分线性表：队列和栈的应用关键词关键要点主题名称：队列的应用

1.问题建模：队列可以模拟真实世界中的排队场景，例如队列中的任务等待执行，或数据等待处理。在竞技编程中，队列用于解决各种问题，例如广度优先搜索(BFS)、拓扑排序和任务调度。

2.队列的使用：队列提供先进先出的(FIFO)特性，这意味着最早进入队列的元素将首先被移除。这使得队列适用于需要按顺序处理元素的情况。在竞技编程中，队列用于存储要执行的任务列表或跟踪搜索过程中的已访问状态。

3.相关问题：与队列应用相关的典型竞技编程问题包括：在线法官中的任务调度、使用BFS查找最短路径，以及解决拓扑依赖问题（例如，确定编译依赖项的顺序）。

主题名称：栈的应用

线性表：队列和栈的应用

线性表是一种数据结构，元素按顺序排列，通过索引或遍历进行访问。栈和队列是线性表中的两种基本数据结构，在竞技编程中有着广泛的应用。

栈

栈是一种后进先出（LIFO）的数据结构，类似于一叠盘子。只有栈顶的元素可以被访问和修改。

竞技编程中的应用：

*函数调用：栈用于存储函数调用时的局部变量和返回地址，以便函数返回时恢复状态。

*回溯：栈用于存储搜索或遍历过程中访问过的状态，以便回溯到之前的选择。

*表达式求值：栈用于存储运算符和操作数，以便按照运算优先级进行计算。

*括号匹配：栈用于检查括号是否成对出现，以确保代码的语法正确性。

队列

队列是一种先进先出（FIFO）的数据结构，类似于一条队列。元素从队尾插入，从队头删除。

竞技编程中的应用：

*任务调度：队列用于存储等待处理的任务，确保先入队的任务先被执行。

*缓冲区：队列用于在生产者和消费者之间缓冲数据，避免数据丢失或出现竞争条件。

*广度优先搜索：队列用于存储广度优先搜索算法中访问过的节点，以便按照层级进行遍历。

*消息传递：队列用于在不同的线程或进程之间传递消息，实现异步通信。

特定竞技编程问题示例

栈：

*括号匹配：给定一个包含括号的字符串，判断括号是否成对出现。可以使用栈存储左括号，当遇到右括号时匹配弹出。

*回溯：求解八皇后问题，使用栈存储当前摆放皇后的位置，当遇到冲突时回溯到之前的选择。

*表达式求值：给定一个中缀表达式，计算结果。可以使用栈存储运算符和操作数，按照运算优先级进行求值。

队列：

*任务调度：给定一组任务及其依赖关系，安排任务的执行顺序，确保依赖关系得到满足。可以使用队列存储等待执行的任务，并根据依赖关系进行调度。

*广度优先搜索：给定一个图，求解最短路径或联通性问题。可以使用队列存储访问过的节点，并按照广度进行搜索。

*消息传递：在多线程环境中，使用队列在不同的线程之间传递消息，确保消息顺序得到保证。

优缺点比较

|数据结构|优点|缺点|

||||

|栈|访问和修改栈顶元素方便|只能从栈顶访问元素|

|队列|先进先出，FIFO特性|插入和删除元素需要遍历|

结论

栈和队列是竞技编程中不可或缺的数据结构，它们的独特特性使它们适用于广泛的问题类型。通过理解这些数据结构的原理和应用，程序员可以有效地解决复杂的问题，提高竞技编程的效率和准确性。第三部分树状数组：处理区间查询和更新关键词关键要点【树状数组：处理区间查询和更新】

1.树状数组是一种空间复杂度为O(n)的数据结构，可以高效地处理区间查询和更新。

2.树状数组利用前缀和数组的思想，通过二进制表示元素的位置，快速地查询和更新指定区间的元素。

3.树状数组在竞技编程中广泛用于处理范围求和、单点修改和范围查询等问题。

【相关算法优化】：

树状数组：处理区间查询和更新

简介

树状数组（BinaryIndexedTree，简称BIT）是一种高效的数据结构，用于处理一维数组上的区间查询和更新操作。它可以快速计算特定区间的元素和，并支持以常数时间更新单个元素。

原理

树状数组基于二进制表示的原理构建。其核心思想是在每个节点存储该节点及其所有后代节点所表示的元素的和。每个节点的编号由其存储的元素集合的二进制表示的前缀和决定。

构建

给定一个一维数组A，我们可以使用以下算法构建树状数组：

1.初始化树状数组大小为n，其中n是输入数组的长度。

2.对于数组中的每个元素A[i]（从i=1到n）：

-将指针p设置为i。

-while(p<=n)：

-将树状数组BIT[p]加上A[i]。

-将指针p更新为p+(p&-p)，移动到BIT[p]的父节点。

查询

查询区间[i,j]的元素和可以使用以下算法：

1.将sum初始化为0。

2.将指针p设置为j+1。

3.while(p>0)：

-将sum加上BIT[p]。

-将指针p更新为p-(p&-p)。

4.将指针q设置为i。

5.while(q>0)：

-将sum减去BIT[q]。

-将指针q更新为q-(q&-q)。

6.返回sum。

更新

更新单个元素A[i]的值为x可以使用以下算法：

1.将差值delta设置为x-A[i]。

2.将指针p设置为i。

3.while(p<=n)：

-将BIT[p]加上delta。

-将指针p更新为p+(p&-p)。

优势

树状数组相对于其他用于处理区间查询和更新的数据结构（如线段树）具有以下优势：

-内存消耗低：树状数组只需O(n)的空间，其中n是数组的长度。

-查询和更新时间复杂度低：区间查询和元素更新的时间复杂度均为O(logn)。

-实现简单：树状数组的实现相对简单，易于理解和实施。

应用

树状数组在竞技编程中具有广泛的应用，包括但不限于：

-计算子数组和

-查找最大值或最小值

-区间求逆

-离线查询第四部分线段树：区间查询、更新和求极值关键词关键要点线段树：区间查询、更新和求极值

1.区间查询：线段树利用二分法将区间划分成较小的子区间，通过递归遍历子树，快速查询指定区间的元素信息。

2.区间更新：线段树支持对指定区间进行值更新，通过递归更新子树信息，高效地维护整个树的数据一致性。

3.区间求极值：线段树可以快速计算指定区间内元素的极值（最大值或最小值），利用子树信息进行递归求解，高效获取区间内最优值。

线段树的结构和实现

1.节点结构：线段树的节点包含区间信息、区间元素信息以及左右子节点指针，递归构建成树形结构。

2.区间表示：每个节点的区间表示为[l,r]，其中l表示左端点，r表示右端点。

3.区间覆盖：子节点的区间[l1,r1]与[l2,r2]覆盖父节点区间[l,r]，满足[l1,r1]∪[l2,r2]=[l,r]。

线段树的时间复杂度

1.查询复杂度：区间查询的时间复杂度为O(logn)，其中n为树中元素个数。

2.更新复杂度：区间更新的时间复杂度同样为O(logn)。

3.求极值复杂度：区间求极值的时间复杂度为O(logn)，与区间查询相同。

线段树的扩展应用

1.范围查询：针对指定范围条件的元素进行查询，例如查询区间内所有偶数元素。

2.动态范围查询：在区间不断变化的情况下，高效维护区间查询结果。

3.离线查询：先收集全部查询请求，再使用线段树まとめて处理，优化查询效率。

线段树的前沿发展

1.持久化线段树：针对查询频繁的场景，维护历史状态的线段树版本，支持查询任意历史状态。

2.可持久化线段树：基于持久化线段树，进一步实现区间更新的可持久化，降低内存消耗。

3.并行线段树：利用多线程并行处理技术，提升区间查询和求极值的性能。线段树：区间查询、更新和求极值

简介

线段树是一种树形数据结构，用于高效地处理与区间相关的查询和更新。它将一个给定的数组划分为一系列连续的区间，并使用一个二叉树来表示这些区间。每个树节点存储与相应区间的统计信息，例如和、最小值或最大值。

结构

线段树是一个高度平衡的、二叉完全树。每个节点有三个主要部分：

*区间范围：节点表示的区间范围。

*统计信息：与区间相关的统计信息，例如和、最小值或最大值。

*左右子节点：分别表示节点区间范围的左半部分和右半部分的子树节点。

建立线段树

给定一个数组，线段树可以递归地构建如下：

1.将数组视为根节点的区间范围，并将根节点的统计信息设置为数组中相应元素的和。

2.将区间范围分为左右两半。

3.为每个子区间创建子节点，并重复步骤1和2，直到达到数组的底层元素。

区间查询

区间查询用于查询特定区间内的统计信息。给定要查询的区间范围，我们可以使用以下步骤进行查询：

1.从根节点开始。

2.如果当前节点的区间范围与要查询的区间范围完全重叠，则返回节点的统计信息。

3.否则，如果要查询的区间范围与当前节点的左子节点的区间范围重叠，则递归查询左子节点。

4.否则，递归查询右子节点。

5.将左子节点和右子节点的查询结果合并为最终结果。

区间更新

区间更新用于更新特定区间内的元素值。给定要更新的区间范围和新的元素值，我们可以使用以下步骤进行更新：

1.从根节点开始。

2.如果当前节点的区间范围完全包含要更新的区间范围，则更新节点的统计信息。

3.否则，如果要更新的区间范围与当前节点的左子节点的区间范围重叠，则递归更新左子节点。

4.否则，递归更新右子节点。

5.更新当前节点的统计信息，以反映子节点的更改。

求极值

线段树还可以用于在给定区间内求极值。这可以通过以下步骤实现：

1.从根节点开始。

2.如果当前节点的区间范围与要查找极值的区间范围完全重叠，则返回节点的统计信息。

3.否则，如果要查找极值的区间范围与当前节点的左子节点的区间范围重叠，则递归查找左子节点。

4.否则，递归查找右子节点。

5.在左子节点和右子节点查找的极值之间进行比较，返回较大的极值。

时间复杂度

*建立线段树：O(nlogn)，其中n是数组中的元素数量。

*区间查询：O(logn)

*区间更新：O(logn)

*求极值：O(logn)

应用

线段树在竞技编程中广泛用于解决与区间相关的各种问题，包括：

*求和查询

*极值查询

*范围更新

*逆序对计算

*区间覆盖

*动态范围查询

优点

*高效的区间查询、更新和求极值操作。

*适用于解决广泛的区间相关问题。

*相对于暴力算法具有显着的性能优势。

局限性

*建立线段树的开销可能很高，尤其对于大型数组。

*线段树的修改操作需要在所有受影响的节点上进行传播，这可能会降低更新操作的效率。第五部分排序树：高效维护有序集合关键词关键要点排序树：高效维护有序集合

1.基本原理：排序树是一种二叉搜索树，其中每个节点都包含一个键和一个值。它维护着按键有序的集合，并支持高效的插入、删除和查找操作。

2.效率优势：排序树相对于其他数据结构（如链表或数组）具有明显的效率优势。例如，查找操作的时间复杂度为O(logn)，比链表的O(n)更加高效。

3.应用广泛：排序树在竞技编程中有着广泛的应用，尤其是在需要维护有序集合的场景中。例如，可以用来快速查询排行榜、处理区间查询或计算众数。

平衡树：保持树的高度平衡

1.平衡机制：平衡树是一种排序树，它通过平衡子树的高度来优化树的结构。这确保了查找、插入和删除操作的时间复杂度始终为O(logn)，即使树高度很高。

2.常见类型：常见的平衡树类型包括红黑树、AVL树和splay树。每种类型都使用不同的算法来保持树的平衡，并针对特定的性能要求进行优化。

3.性能提升：在竞技编程中，平衡树对于需要频繁更新或查询大数据集的场景尤为有用。它可以显著提升性能，使程序能够在严格的时间限制下高效运行。

优先队列：基于优先级的排序

1.基本概念：优先队列是一种数据结构，它按元素的优先级对元素进行排序。当需要访问具有最高优先级的元素时，优先队列可以快速提供。

2.实现方法：优先队列可以使用堆、二叉搜索树或斐波那契堆等底层数据结构来实现。不同的实现方法在时间复杂度和空间效率方面各有优势。

3.竞技编程应用：优先队列在竞技编程中用于解决各种问题，例如迪杰斯特拉算法、图的最短路径计算和贪心算法。它使程序员能够优先处理最重要的任务，从而优化算法的效率。

并查集：高效处理集合合并

1.基本原理：并查集是一种数据结构，它用于维护一组不重叠的集合。它支持高效的集合合并和查询操作，可以确定两个元素是否属于同一个集合。

2.实现方法：并查集通常使用数组来表示集合，其中每个元素指向集合的代表元素。这使得集合合并和查询操作的时间复杂度为O(α(n))，其中α(n)是反阿克曼函数，增长极其缓慢。

3.竞技编程应用：并查集在竞技编程中广泛用于解决图论问题（例如连通分量）、集合合并问题和数据压缩。它可以显著提升程序的效率，尤其是在需要处理大量集合合并操作的场景中。

哈希表：基于键的快速查找

1.基本原理：哈希表是一种数据结构，它使用哈希函数将键映射到值。哈希函数将输入键转换为固定大小数组中的索引，从而实现快速查找和插入操作。

2.冲突处理：由于哈希函数可能产生碰撞（不同的键映射到同一个索引），哈希表使用各种技术（例如链表、开散列或二次探测）来处理碰撞。

3.竞技编程应用：哈希表在竞技编程中用于快速查找和计数元素。它特别适用于需要频繁查找或插入特定键的情况，例如查找字符串中的重复字符或计算字符频率。排序树：高效维护有序集合

排序树是一种自平衡二叉查找树，旨在高效地维护有序集合。它基于红黑树，并针对有序集合的特定操作进行了优化。

结构

排序树与红黑树具有相似的结构。它由节点组成，每个节点包含以下内容：

-键值（元素）

-指向左子树和右子树的指针

-颜色（红色或黑色）

颜色属性用于保持自平衡性，并确保树的高度保持对数级（O(logn)）。

插入

将元素插入排序树的过程类似于红黑树。新元素以红节点的形式插入树中。然后，进行一系列旋转和颜色调整操作，以保持树的自平衡性。

删除

删除元素的过程也类似于红黑树。要删除的元素及其子树被替换为一个虚拟节点，然后进行旋转和颜色调整操作，以保持树的自平衡性。

有序集合操作

помимоосновныхоперацийвставкииудаления,сортировочныедеревьяподдерживаютспециальныеоперациидляработысупорядоченнымимножествами:

-`find_kth(k)`：查找具有给定索引k的元素。

-`range_query(a,b)`：查找具有索引范围[a,b]的所有元素。

-`split(k)`：将树拆分为两个子树，其中一个子树包含索引小于k的元素，而另一个子树包含索引大于或等于k的元素。

-`join(a,b)`：合并两个子树，形成一个包含两个子树元素的有序集合。

优势

排序树在竞技编程中有以下优势：

-高效：有序集合操作的时间复杂度为O(logn)，这对于处理大型数据集至关重要。

-自平衡：排序树保持自平衡，即使在大量插入和删除之后。

-支持范围查询：排序树支持高效的范围查询，这在解决涉及查找特定范围内的元素的问题时非常有用。

-可分离和合并：排序树可以通过`split()`和`join()`操作高效地分离和合并，这使得它们非常适合需要分治法或区间树等技术的问题。

应用

排序树在竞技编程中广泛用于解决各种问题，例如：

-查找中位数：使用`find_kth()`操作高效地查找有序集合的中位数。

-查找逆序对：使用`range_query()`操作查找逆序对的数目，解决逆序对问题。

-处理区间：使用`split()`和`join()`操作创建区间树，高效地处理区间查询和更新。

-解决凸包：使用排序树维护点集的凸包，快速检查点是否在凸包内或计算凸包的面积。第六部分并查集：解决连通性问题关键词关键要点【并查集：解决连通性问题】

1.定义和概念：并查集是一种数据结构，用来高效地管理一组元素的连通性，即找出哪些元素属于同一组。它由一个数组组成，数组中每个元素存储着一个指向该元素所在组的父元素的指针。

2.基本操作：并查集支持两种基本操作：

-`find(x)`：返回元素`x`所在组的代表元素（根节点）。

-`union(x,y)`：将元素`x`和`y`所在的组合并为一个组。

【趋势和前沿】

并查集在竞技编程中具有广泛的应用，尤其是解决连通性问题。随着竞技编程的不断发展，对于高效数据结构的需求不断增长，并查集作为一种经典的数据结构，在复杂度分析和实际应用方面都得到了广泛的认可和探索。

此外，并查集在分布式系统、网络应用程序和社交网络分析等领域也得到了广泛的应用。研究人员不断探索并查集的变种和优化算法，以提高其性能和适用范围。并查集：解决连通性问题

简介

并查集是一种数据结构，用于高效地管理和查询一组元素的连通性信息。在竞技编程中，并查集经常被用来解决涉及连通性问题的任务。

基本原理

并查集由一个数组组成，数组中的每个元素表示一个元素所属的集合。该数组有两个操作：

*查找（find）：给定一个元素，找到它所属的集合的代表元素（通常是集合中的第一个元素）。

*合并（union）：合并两个集合，使其成为一个集合。

优化

为了提高并查集的性能，可以使用以下优化技术：

*按秩合并：合并时，将秩较小的集合合并到秩较大的集合中，这样可以减少查找操作的深度。

*路径压缩：查找时，将路径上的所有元素直接连接到集合的代表元素，这样可以降低查找操作的复杂度。

应用

并查集在竞技编程中的应用包括：

*连通性查询：检查两个元素是否属于同一个连通分量。

*最小生成树：在加权无向图中找到最小生成树。

*连通分量计数：计算图中连通分量的数量。

*网络流最大匹配：在二分图中找到最大匹配。

*动态连通性：在动态变化的图中维护连通性信息。

具体示例

考虑以下问题：

给定一个无向图，其中有n个节点和m条边。每个节点都有一个权重。找到图中权重总和最大的连通分量。

算法：

1.使用并查集初始化n个单元素集合，每个集合包含一个节点。

2.对于每条边，将其端点所在的集合合并。

3.循环遍历集合并计算每个集合中节点权重的总和。

4.返回权重总和最大的集合。

复杂度分析：

*时间复杂度：O(nlogn)，其中n是节点的数量。

*空间复杂度：O(n)，用于存储并查集数组。

结论

并查集是一种强大的数据结构，可以有效地解决涉及连通性问题的任务。了解并查集的基本原理和优化技术对于竞技编程中解决这类问题至关重要。第七部分哈希表：快速查找和映射哈希表：快速查找和映射

哈希表是一种数据结构，允许以恒定时间复杂度进行查找和插入操作。它基于哈希函数的工作原理，该函数将键映射到哈希表中的索引。

工作原理：

*哈希表由一个数组组成，其中每个元素存储一个键-值对。

*哈希函数将键映射到数组中特定的索引。

*插入时，键和值对存储在哈希函数计算出的索引处。

*查找时，使用哈希函数计算键的索引，然后在相应的位置搜索键-值对。

哈希冲突：

当两个不同的键散列到相同的索引时，就会发生哈希冲突。解决冲突的方法有很多，包括：

*线性探测：从冲突位置开始，线性搜索数组中的下一个可用位置。

*开放寻址：使用其他哈希函数或散列方法在冲突发生时查找不同的索引。

*链地址法：在冲突位置创建一个链表来存储键-值对。

选择哈希函数：

选择合适的哈希函数对于优化哈希表性能至关重要。常用的哈希函数包括：

*除法法：将键除以哈希表的大小。

*余数法：将键模以哈希表的大小。

*乘法法：将键乘以一个常数，然后取结果的模。

在竞技编程中的应用：

哈希表在竞技编程中广泛用于：

*快速查找：查找字符串中的模式、查找图形中的节点或查找数组中的特定元素。

*集合操作：查找并集、交集和差集。

*频率计数：计算数组中元素出现的次数或字符串中字符出现的次数。

*路径压缩：并查集中的优化技术。

优势：

*恒定时间复杂度的查找和插入操作。

*适用于需要快速访问数据的情况。

*易于实现。

缺点：

*哈希冲突可能会影响性能。

*需要选择合适的哈希函数。

*无法存储相同键的多个值（除非使用链表）。

其他用途：

哈希表也用于各种其他应用中，包括：

*数据库索引

*缓存

*网络路由

*存储密码哈希值

示例实现：

```python

classHashTable:

def__init__(self,size):

self.size=size

self.table=[[]for_inrange(size)]

defhash(self,key):

returnkey%self.size

definsert(self,key,value):

index=self.hash(key)

self.table[index].append((key,value))

defget(self,key):

index=self.hash(key)

fork,vinself.table[index]:

ifk==key:

returnv

returnNone

```

总结：

哈希表是一种高效的数据结构，它允许以恒定时间复杂度进行查找和插入操作。通过利用哈希函数，哈希表可以快速定位所需数据，使其成为竞技编程和其他需要快速数据访问的应用中的宝贵工具。第八部分伸展树：动态维护有序集合关键词关键要点伸展树：动态维护有序集合

1.伸展树的定义和性质：

-一种自平衡二叉搜索树，其高度近似于对数

-支持插入、删除和排序等操作的高效算法

2.伸展操作：

-当树的高度超过一定阈值时，将树旋转为近似平衡的状态

-确保树的高度在对数级别内，保证操作效率

3.应用场景：

-动态维护有序集合，例如处理大量数据流中的插入和删除操作

-数据分析和算法中，需要高效的有序数据结构时

伸展操作的步骤

1.寻找重节点：

-找到深度大于阈值节点，称为重节点

-重节点的子树高度不平衡

2.进行旋转：

-将重节点旋转到根节点

-根据重节点的深度和左右子树的高度，选择单旋转或双旋转

3.更新高度：

-旋转后，更新受影响节点的高度

-确保树的高度在对数级别内伸展树：动态维护有序集合

伸展树是一种动态数据结构，用于维护有序集合（比方说，整数集合），使其支持以下操作：

-插入元素

-删除元素

-查找元素

-求第k小元素

-求排名为k的元素

-合并两个伸展树

伸展树将有序集合表示为一棵平衡二叉搜索树（BST），该BST满足以下性质：

-左子树元