Treap 数据结构

2025年3月17日 | 阅读18分钟

Treap 数据结构是二叉搜索树和堆的混合体。Treap 和随机二叉搜索树是两种二叉搜索树数据结构，它们维护有序键的动态集合，并允许在键之间进行二分查找。

树的结构是一个随机变量，与任何一系列键的插入和删除后的随机二叉树具有相同的概率分布；特别是，高概率下，其高度与键的数量成对数比例，因此每次搜索、插入或删除操作都需要对数时间来执行。

为了更好地理解 Treap 数据结构，我们应该理解 Treap 的底层数据结构，即二叉搜索树和堆数据结构。

二叉搜索树

节点删除和添加会导致树变得不平衡（变得一边重；因此，我们重视 BST 的属性，即通过均等分割来分布数据的能力，就会失效）。因此，我们必须重新平衡该树（对于有 n 个组件的树，这需要 O(n) 时间）。长期以来，计算机科学家一直使用平衡搜索树，其中包括旋转算法来在添加和删除节点后保持其平衡，例如红黑树、伸展树、AVL 树等。

B 树比仅仅一个元素在每个节点中包含更多信息。这些通过一些改进进行了补充。例如，伸展树将最常访问的组件移到顶部并重新平衡。这增加了算法的复杂性，同时提供了标准 BST 的好处。

堆

堆只是带有“堆”特性的二叉树。（当树的所有父节点的键大于或等于其子节点的键时，则为最大堆。）这个特性是它成为实现优先队列的良好数据结构的原因（如果我们删除一个元素，我们必须在两个子节点之间进行选择，以确定谁将占据缺失元素的位置）。堆可以逻辑地存储在数组中，这是其优点（随机访问时间）。

Treap 数据结构是堆和二叉搜索树的混合体。当我们创建一个堆时，我们实际上是创建了一个有序二叉树，它也满足“堆”的特性。假设只使用一个元素。在这种情况下，它将显示为一条直线（因为在 BST 中，左子节点必须小于其父节点，右子节点必须大于或等于其父节点，但对于堆，每个父节点都应该要么比所有子节点都大，要么比所有子节点都小）。

Treap Data Structure

数字表示数据结构的堆排列（最大堆顺序），而字母表示树的部分（左子节点-父节点=右子节点）。所以我们现在有了树和堆。这是 Treap 数据结构的魔术属性。无论树的元素选择顺序如何，该树只有一个配置。

使用随机堆权重使第二个键对我们更有价值。因此，树的结构（形状）现在将由我们为堆值分配的随机权重决定。通过确保这些是随机分配的（一种方法是通过哈希键本身）来获得随机堆优先级。要插入一个新键，请计算优先级并执行传统的 BST 插入，然后将其旋转到树的顶部（以维护堆）。要删除一个键，将其权重增加到无穷大，然后将其旋转到树的底部（同样，按堆顺序），直到它成为叶子节点，然后删除它。

所以它在键方面是一棵树，在优先级方面是一个堆。理论上，重新堆化树几乎肯定会使其保持平衡（高度将是 c.log(n)），因为随机二叉搜索树具有对数高度。

Treap 数据结构的重要性

以下是说明 Treap 数据结构重要性的原因。

  • 如前所述，它是一种自组织数据结构。它们自行维护，无需监督。与其他自平衡树不同，它们不需要复杂的算法（简单的树旋转就足够了，尽管涉及数组的简单算法也可以完成任务）。
  • 它也是一种随机数据结构。
  • 由于随机权重，树很有可能在无论我们添加、删除等顺序如何的情况下都保持平衡（随机二叉搜索树具有对数高度）。
  • 它只是一个二叉搜索树，因此要打印键的排序顺序，可以像处理传统 BST 一样遍历它。搜索 Treap 与搜索树类似。
  • Treap 是一种结合了概率、随机化、两种主要的二叉搜索结构以及其他因素来创建有用数据结构的结构。

C++ 代码

让我们编写 C++ 代码来实现 Treap 数据结构。

输出

上面的 C++ 代码产生以下输出。

Select one of the operations for the Treap Data Structure::
1. To insert a new node in the Treap Data Structure.
2. To display the nodes of the Treap Data Structure.
3. To Delete a node from the Treap Data Structure.
4. To search a node from the Treap Data Structure.
1
Enter the value of the node to be inserted
98

Do you want to continue (Type y or n) 
y

Select one of the operations for the Treap Data Structure::
1. To insert a new node in the Treap Data Structure.
2. To display the nodes of the Treap Data Structure.
3. To Delete a node from the Treap Data Structure.
4. To search a node from the Treap Data Structure.
1
Enter the value of the node to be inserted
32

Do you want to continue (Type y or n) 
y

Select one of the operations for the Treap Data Structure::
1. To insert a new node in the Treap Data Structure.
2. To display the nodes of the Treap Data Structure.
3. To Delete a node from the Treap Data Structure.
4. To search a node from the Treap Data Structure.
1
Enter the value of the node to be inserted
22

Do you want to continue (Type y or n) 
y

Select one of the operations for the Treap Data Structure::
1. To insert a new node in the Treap Data Structure.
2. To display the nodes of the Treap Data Structure.
3. To Delete a node from the Treap Data Structure.
4. To search a node from the Treap Data Structure.
1
Enter the value of the node to be inserted
10

Do you want to continue (Type y or n) 
y

Select one of the operations for the Treap Data Structure::
1. To insert a new node in the Treap Data Structure.
2. To display the nodes of the Treap Data Structure.
3. To Delete a node from the Treap Data Structure.
4. To search a node from the Treap Data Structure.
1
Enter the value of the node to be inserted
67

Do you want to continue (Type y or n) 
y

Select one of the operations for the Treap Data Structure::
1. To insert a new node in the Treap Data Structure.
2. To display the nodes of the Treap Data Structure.
3. To Delete a node from the Treap Data Structure.
4. To search a node from the Treap Data Structure.
1
Enter the value of the node to be inserted
30 

Do you want to continue (Type y or n) 
y

Select one of the operations for the Treap Data Structure::
1. To insert a new node in the Treap Data Structure.
2. To display the nodes of the Treap Data Structure.
3. To Delete a node from the Treap Data Structure.
4. To search a node from the Treap Data Structure.
2
Contents of the Treap Data Structure are::

10(54) > 22(12) > 30(23) > 32(81) > 67(86) > 98(19)

Do you want to continue (Type y or n) 
y

Select one of the operations for the Treap Data Structure::
1. To insert a new node in the Treap Data Structure.
2. To display the nodes of the Treap Data Structure.
3. To Delete a node from the Treap Data Structure.
4. To search a node from the Treap Data Structure.
3
Enter the value of the node that you want to delete::
30
o you want to continue (Type y or n) 
y

Select one of the operations for the Treap Data Structure::
1. To insert a new node in the Treap Data Structure.
2. To display the nodes of the Treap Data Structure.
3. To Delete a node from the Treap Data Structure.
4. To search a node from the Treap Data Structure.
4
Enter the word to search
98
98 found in Treap.

Do you want to continue (Type y or n) 
y

Select one of the operations for the Treap Data Structure::
1. To insert a new node in the Treap Data Structure.
2. To display the nodes of the Treap Data Structure.
3. To Delete a node from the Treap Data Structure.
4. To search a node from the Treap Data Structure.
4
Enter the word to search
69
69 not found in Treap.

Do you want to continue (Type y or n) 
y

Select one of the operations for the Treap Data Structure::
1. To insert a new node in the Treap Data Structure.
2. To display the nodes of the Treap Data Structure.
3. To Delete a node from the Treap Data Structure.
4. To search a node from the Treap Data Structure.
4
Enter the word to search
67
67 found in Treap.

Do you want to continue (Type y or n) 
n

在上面的 C++ 代码中，我们为 Treap 数据结构的不同功能编写了不同的方法函数，例如向 Treap 添加新节点、搜索已存在的节点、计算当前 Treap 中的节点数、检查 Treap 数据结构是否为空以及清空 Treap 数据结构。

一旦这些函数编写完成，一个菜单驱动的程序会调用所有这些函数，然后依次将数据添加到 Treap 数据结构中，接着对创建的 Treap 数据结构执行搜索操作和打印操作。

Java 代码

现在让我们看看如何用 Java 代码实现 Treap 数据结构。

输出

上面的 Java 代码产生以下输出。

Treap Test

Select one of the operations for the Treap Data Structure

1. To insert a new node in the Treap Data Structure.
2. To search a node from the Treap Data Structure.
3. To count nodes in the Treap Data Structure.
4. To check if the TreapData Structure is empty?.
5. To make Treap Data Structure empty.
1
Enter integer element to insert
10

Post-Order : 10 
Pre-Order: 10 
In order: 10 
Do you want to continue (Type y or n) 

y

Select one of the operations for the Treap Data Structure

1. To insert a new node in the Treap Data Structure.
2. To search a node from the Treap Data Structure.
3. To count nodes in the Treap Data Structure.
4. To check if the TreapData Structure is empty?.
5. To make Treap Data Structure empty.
1
Enter integer element to insert
22

Post-Order: 10 22 
Pre-Order: 22 10 
In order: 10 22 
Do you want to continue (Type y or n) 

y

Select one of the operations for the Treap Data Structure

1. To insert a new node in the Treap Data Structure.
2. To search a node from the Treap Data Structure.
3. To count nodes in the Treap Data Structure.
4. To check if the TreapData Structure is empty?.
5. To make Treap Data Structure empty.
1
Enter integer element to insert
36

Post-Order: 10 22 36 
Pre-Order: 36 22 10 
In order: 10 22 36 
Do you want to continue (Type y or n) 

y

Select one of the operations for the Treap Data Structure

1. To insert a new node in the Treap Data Structure.
2. To search a node from the Treap Data Structure.
3. To count nodes in the Treap Data Structure.
4. To check if the TreapData Structure is empty?.
5. To make Treap Data Structure empty.
1
Enter integer element to insert
75

Post-Order : 10 22 75 36 
Pre-Order : 36 22 10 75 
In order : 10 22 36 75 
Do you want to continue (Type y or n) 

y

Select one of the operations for the Treap Data Structure

1. To insert a new node in the Treap Data Structure.
2. To search a node from the Treap Data Structure.
3. To count nodes in the Treap Data Structure.
4. To check if the TreapData Structure is empty?.
5. To make Treap Data Structure empty.
1
Enter integer element to insert
62

Post-Order : 10 22 62 75 36 
Pre-Order : 36 22 10 75 62 
In order : 10 22 36 62 75 
Do you want to continue (Type y or n) 

y

Select one of the operations for the Treap Data Structure

1. To insert a new node in the Treap Data Structure.
2. To search a node from the Treap Data Structure.
3. To count nodes in the Treap Data Structure.
4. To check if the TreapData Structure is empty?.
5. To make Treap Data Structure empty.
1
Enter integer element to insert
89

Post-Order : 10 22 62 75 89 36 
Pre-Order : 36 22 10 89 75 62 
In order : 10 22 36 62 75 89 
Do you want to continue (Type y or n) 

y

Select one of the operations for the Treap Data Structure

1. To insert a new node in the Treap Data Structure.
2. To search a node from the Treap Data Structure.
3. To count nodes in the Treap Data Structure.
4. To check if the TreapData Structure is empty?.
5. To make Treap Data Structure empty.
1
Enter integer element to insert
44

Post-Order : 10 22 44 62 75 89 36 
Pre-Order : 36 22 10 89 75 62 44 
In order : 10 22 36 44 62 75 89 
Do you want to continue (Type y or n) 

y

Select one of the operations for the Treap Data Structure

1. To insert a new node in the Treap Data Structure.
2. To search a node from the Treap Data Structure.
3. To count nodes in the Treap Data Structure.
4. To check if the TreapData Structure is empty?.
5. To make Treap Data Structure empty.
2
Enter integer element to search
27
Search result: false

Post-Order : 10 22 44 62 75 89 36 
Pre-Order : 36 22 10 89 75 62 44 
In order : 10 22 36 44 62 75 89 
Do you want to continue (Type y or n) 

y

Select one of the operations for the Treap Data Structure

1. To insert a new node in the Treap Data Structure.
2. To search a node from the Treap Data Structure.
3. To count nodes in the Treap Data Structure.
4. To check if the TreapData Structure is empty?.
5. To make Treap Data Structure empty.
3
Nodes = 7

Post-Order : 10 22 44 62 75 89 36 
Pre-Order : 36 22 10 89 75 62 44 
In order : 10 22 36 44 62 75 89 
Do you want to continue (Type y or n) 

y

Select one of the operations for the Treap Data Structure

1. To insert a new node in the Treap Data Structure.
2. To search a node from the Treap Data Structure.
3. To count nodes in the Treap Data Structure.
4. To check if the TreapData Structure is empty?.
5. To make Treap Data Structure empty.
4
Empty status = false

Post-Order : 10 22 44 62 75 89 36 
Pre-Order : 36 22 10 89 75 62 44 
In order : 10 22 36 44 62 75 89 
Do you want to continue (Type y or n) 

y

Select one of the operations for the Treap Data Structure

1. To insert a new node in the Treap Data Structure.
2. To search a node from the Treap Data Structure.
3. To count nodes in the Treap Data Structure.
4. To check if the TreapData Structure is empty?.
5. To make Treap Data Structure empty.
5

Treap Cleared

Post-Order : 
Pre-Order : 
In order : 
Do you want to continue (Type y or n) 

y

Select one of the operations for the Treap Data Structure

1. To insert a new node in the Treap Data Structure.
2. To search a node from the Treap Data Structure.
3. To count nodes in the Treap Data Structure.
4. To check if the Treap Data Structure is empty?.
5. To make Treap Data Structure empty.
4
Empty status = true

Postorder : 
Pre-order : 
In order : 
Do you want to continue (Type y or n) 

N

在上面的 Java 代码中，我们为 Treap 数据结构的不同功能编写了不同的方法函数，例如向 Treap 添加新节点、搜索已存在的节点、计算当前 Treap 中的节点数、检查 Treap 数据结构是否为空以及清空 Treap 数据结构。

一旦这些函数编写完成，一个菜单驱动的程序会调用所有这些函数，然后依次将数据添加到 Treap 数据结构中，接着对创建的 Treap 数据结构执行搜索操作和打印操作。

下一话题双向链表上的快速排序





相关帖子




Logo

我们提供所有技术（如 Java 教程、Android、Java 框架）的教程和面试问题

联系信息

G-13, 2nd Floor, Sec-3, Noida, UP, 201301, India

hr@tpointtech.com

+91-9599086977

关注我们
Tpoint Tech Facebook PageTpoint Tech X PageTpoint Tech Linkedin PageTpoint Tech Telegram ChannelTpoint Tech Youtube ChannelTpoint Tech instagram Page
教程
Java 数据结构 C 语言 C++ 教程 C# 教程 PHP 教程HTML 教程 JavaScript 教程jQuery 教程Spring 教程
面试题
Microsoft Amazon Adobe Intuit Accenture Cognizant Capgemini Wipro Tcs Infosys
在线编译器
C R C++ Php Java Html Swift Python JavaScript TypeScript
最新帖子 | 教程列表 | 隐私政策 | 关于我们 | 联系我们
© 版权所有 2011 - 2025 TpointTech.com。保留所有权利。