/**
* 如果一个二叉搜索树节点插入的顺序是随机的,这样我们得到的二叉搜索树大多
* 数情况下是平衡的,即使存在一些极端情况,但是这种情况发生的概率很小,
* 所以我们可以这样建立一棵二叉搜索树,而不必要像AVL那样旋转,可以证明随
* 机顺序建立的二叉搜索树在期望高度是O(log n),但是某些时候我们并不能得
* 知所有的待插入节点,打乱以后再插入。所以我们需要一种规则来实现这种想法,
* 并且不必要所有节点。也就是说节点是顺序输入的,我们实现这一点可以用Treap。
* Treap=Tree+Heap。Treap本身是一棵二叉搜索树,它的左子树和右子树
* 也分别是一个Treap,和一般的二叉搜索树不同的是,Treap记录一个额外的
* 数据,就是优先级,Treap在以关键码构成二叉搜索树的同时,还按优先级来
* 满足堆的性质,Treap维护堆性质的方法用到了旋转,堆的优先级是随机的,我们
* 通过维护堆的性质来保证二叉树的平衡,Treap数据结构下的插入与删除操作期
* 望的时间复杂度均为O(log(n)),Treap维护堆的唯一旋转方式:
* * *
* / \ / \
* * * <================> * *
* / \ / \
* * * * *
*/
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
struct node
{
int element;
int priority;
struct node * left_node;
struct node * right_node;
};
struct node * alloc_node(int element)
{
struct node * new_node;
new_node = calloc(1, sizeof (struct node));
assert(new_node);
new_node->element = element;
// 为新节点的优先级分配一个随机数
new_node->priority = rand() % 1000;
return new_node;
}
struct node * left_rotate(struct node * root_node)
{
struct node * tmp_node;
tmp_node = root_node->right_node;
root_node->right_node = tmp_node->left_node;
tmp_node->left_node = root_node;
return tmp_node;
}
struct node * right_rotate(struct node * root_node)
{
struct node * tmp_node;
tmp_node = root_node->left_node;
root_node->left_node = tmp_node->right_node;
tmp_node->right_node = root_node;
return tmp_node;
}
struct node * insert(struct node * root_node, int element)
{
if(root_node == NULL)
{
// 分配一个新的节点
root_node = alloc_node(element);
}
else
{
if(root_node->element > element)
{
root_node->left_node = insert(root_node->left_node, element);
if(root_node->priority > root_node->left_node->priority)
root_node = right_rotate(root_node);
}
else if(root_node->element < element)
{
root_node->right_node = insert(root_node->right_node, element);
if(root_node->priority > root_node->right_node->priority)
root_node = left_rotate(root_node);
}
}
return root_node;
}
struct node * del(struct node * root_node, int element)
{
if(root_node != NULL)
{
if(root_node->element == element)
{
struct node * tmp_node;
if(!root_node->left_node || !root_node->right_node)
{
tmp_node = root_node;
if(!root_node->left_node)
root_node = root_node->right_node;
else
root_node = root_node->left_node;
// 释放被删除节点
free(tmp_node);
}
else
{
tmp_node = root_node;
if(root_node->left_node->element < root_node->right_node->element)
{
root_node = right_rotate(root_node);
root_node->right_node = del(tmp_node, element);
}
else
{
root_node = left_rotate(root_node);
root_node->left_node = del(tmp_node, element);
}
}
}
else
{
if(root_node->element < element)
root_node->right_node = del(root_node->right_node, element);
else if(root_node->element > element)
root_node->left_node = del(root_node->left_node, element);
}
}
return root_node;
}
分享到:
相关推荐
**Treap树堆实现** Treap,又称为“随机优先搜索树”,是一种结合了二叉查找树(BST)和堆特性的数据结构。它在保持查找树特性的同时,通过引入随机化来保证平衡,从而避免了传统平衡二叉树如AVL或红黑树等在插入和...
Treap树,也被称为二叉搜索树堆,是一种二叉搜索树,它将堆(Heap)的性质与二叉搜索树(Binary Search Tree)的性质结合起来。Treap树中的每个节点都同时拥有一个搜索键(search key)和一个优先级(priority)。它...
Treap树是一种自平衡二叉搜索树,由Russo在1989年提出,它的全称是“随机优先堆树”(Tree-Heap)。它结合了二叉搜索树和堆的特点,通过引入随机性来保持平衡,从而在平均情况下达到较高的查找、插入和删除操作的...
Treap,全称是“Tree + Heap”,是由Russo在1989年提出的,是一种结合了二叉搜索树(BST)和堆(Heap)特性的数据结构。它在保持搜索树平衡的同时,通过随机化策略解决了平衡问题,使得插入、删除和查找操作的时间...
fruit --treep平衡树 Treap=Tree+Heap。Treap本身是一棵二叉搜索树,它的左...Treap在以关键码构成二叉搜索树的同时,还满足堆的性质。Treap维护堆性质的方法用到了旋转,只需要两种旋转,编程复杂度比Splay要小一些。
红黑树和AVL树是两种自平衡二叉查找树,它们在计算机科学中的数据结构领域扮演着重要的角色,主要用于高效地存储和检索数据。这两种数据结构的主要目标是在插入和删除操作后保持树的平衡,从而确保搜索、插入和删除...
在了解和实现Treap树的过程中,理解它的存储结构、定义规则、建树方法、平衡保持机制以及应用场景是基础,但同时也需要注意对文件内容进行适当的解读和修正,以确保对概念和实现方法有准确的理解。
- **Treap**:一种自平衡的二叉搜索树,结合了堆的性质和二叉搜索树的性质。 - **Splay Tree (伸展树)**:一种自调整的二叉搜索树,通过一系列旋转操作使最近访问的节点移动到树根的位置。 ##### 2. 二叉搜索树的...
在这个"平衡树大全"中,我们将深入探讨三种重要的平衡树类型:Splay树、Treap树和静态平衡树(Static Balance Tree,简称SBT)。 1. **Splay树**: Splay树是一种自调整的平衡树,通过每次操作后将访问的节点移动...
Treap,全称是“随机优先堆树”(Tree with Random Priority),是一种自平衡的二叉搜索树。它结合了二叉搜索树的特性(左子节点小于父节点,右子节点大于父节点)与堆的特性(每个节点的优先级大于或等于其子节点)...
Treap(树堆)是一种结合了随机化和二叉搜索树特性的数据结构,由Russo和Sedgewick在1989年提出。它的核心思想是将二叉搜索树与堆属性相结合,通过随机化的方式确保良好的平衡性,从而在平均情况下提供近似于最优的...
3. Treap:Treap是一种随机化的动态树,结合了堆(heap)和二叉搜索树的特性。每个节点都有一个优先级,插入和删除操作通过维护堆的性质来保证树的平衡。由于优先级是随机生成的,Treap在平均情况下的性能接近于最优...
Treap是一种结合了二叉搜索树(BST)和堆(Heap)特性的数据结构,其名称由“tree”和“heap”组合而成。Treap的特点在于每个节点不仅包含键值,还包含一个优先级,这个优先级通常是随机生成的,使得整个树同时满足...
数据结构与算法分析:C语言描述_原书第2版_高清版全书特点如下:1.专用一章来讨论算法设计技巧,包括贪婪算法、分治算法、动态...treap树、k-d树、配对堆以及其他相关内容;5.合并了堆排序平均情况分析的一些新结果。
**Treap(树堆)** 是一种结合了二叉搜索树(BST)和堆属性的数据结构。它由Carlos R. Păcu于1989年提出,名字由"tree"(树)和"heap"(堆)组合而成。Treap的特点在于每个节点不仅包含键值(如在BST中),还包含一...
在《数据结构与算法分析:C语言描述》中,作者精炼并强化了他对算法和数据结构...增加了高级数据 结构及其实现的内容,包括红黑树、自顶向下伸展树、treap树、k-d树、配对堆等。整合了堆排序平均情况分析的一些新结果。