`
yyang900427
  • 浏览: 11599 次
  • 性别: Icon_minigender_1
  • 来自: 北京
最近访客 更多访客>>
社区版块
存档分类
最新评论

Treap(树堆)

阅读更多
/**
 * 如果一个二叉搜索树节点插入的顺序是随机的,这样我们得到的二叉搜索树大多
 * 数情况下是平衡的,即使存在一些极端情况,但是这种情况发生的概率很小,
 * 所以我们可以这样建立一棵二叉搜索树,而不必要像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树堆实现** Treap,又称为“随机优先搜索树”,是一种结合了二叉查找树(BST)和堆特性的数据结构。它在保持查找树特性的同时,通过引入随机化来保证平衡,从而避免了传统平衡二叉树如AVL或红黑树等在插入和...

    Treap 树堆 和 Skip Lists

    Treap树,也被称为二叉搜索树堆,是一种二叉搜索树,它将堆(Heap)的性质与二叉搜索树(Binary Search Tree)的性质结合起来。Treap树中的每个节点都同时拥有一个搜索键(search key)和一个优先级(priority)。它...

    treap树VB实现

    Treap树是一种自平衡二叉搜索树,由Russo在1989年提出,它的全称是“随机优先堆树”(Tree-Heap)。它结合了二叉搜索树和堆的特点,通过引入随机性来保持平衡,从而在平均情况下达到较高的查找、插入和删除操作的...

    手把手教你用Treap

    Treap,全称是“Tree + Heap”,是由Russo在1989年提出的,是一种结合了二叉搜索树(BST)和堆(Heap)特性的数据结构。它在保持搜索树平衡的同时,通过随机化策略解决了平衡问题,使得插入、删除和查找操作的时间...

    fruit --treep平衡树

    fruit --treep平衡树 Treap=Tree+Heap。Treap本身是一棵二叉搜索树,它的左...Treap在以关键码构成二叉搜索树的同时,还满足堆的性质。Treap维护堆性质的方法用到了旋转,只需要两种旋转,编程复杂度比Splay要小一些。

    红黑树和AVL树的实现

    红黑树和AVL树是两种自平衡二叉查找树,它们在计算机科学中的数据结构领域扮演着重要的角色,主要用于高效地存储和检索数据。这两种数据结构的主要目标是在插入和删除操作后保持树的平衡,从而确保搜索、插入和删除...

    Treap原理和实现方法.pdf

    在了解和实现Treap树的过程中,理解它的存储结构、定义规则、建树方法、平衡保持机制以及应用场景是基础,但同时也需要注意对文件内容进行适当的解读和修正,以确保对概念和实现方法有准确的理解。

    史上最简单的平衡树——无旋Treap.pdf

    - **Treap**:一种自平衡的二叉搜索树,结合了堆的性质和二叉搜索树的性质。 - **Splay Tree (伸展树)**:一种自调整的二叉搜索树,通过一系列旋转操作使最近访问的节点移动到树根的位置。 ##### 2. 二叉搜索树的...

    平衡树大全

    在这个"平衡树大全"中,我们将深入探讨三种重要的平衡树类型:Splay树、Treap树和静态平衡树(Static Balance Tree,简称SBT)。 1. **Splay树**: Splay树是一种自调整的平衡树,通过每次操作后将访问的节点移动...

    Python库 | treap-1.31.tar.gz

    Treap,全称是“随机优先堆树”(Tree with Random Priority),是一种自平衡的二叉搜索树。它结合了二叉搜索树的特性(左子节点小于父节点,右子节点大于父节点)与堆的特性(每个节点的优先级大于或等于其子节点)...

    treap:有效实现隐式treap数据结构

    Treap(树堆)是一种结合了随机化和二叉搜索树特性的数据结构,由Russo和Sedgewick在1989年提出。它的核心思想是将二叉搜索树与堆属性相结合,通过随机化的方式确保良好的平衡性,从而在平均情况下提供近似于最优的...

    改造静态树为动态树

    3. Treap:Treap是一种随机化的动态树,结合了堆(heap)和二叉搜索树的特性。每个节点都有一个优先级,插入和删除操作通过维护堆的性质来保证树的平衡。由于优先级是随机生成的,Treap在平均情况下的性能接近于最优...

    数据结构之Treap详解

    Treap是一种结合了二叉搜索树(BST)和堆(Heap)特性的数据结构,其名称由“tree”和“heap”组合而成。Treap的特点在于每个节点不仅包含键值,还包含一个优先级,这个优先级通常是随机生成的,使得整个树同时满足...

    数据结构与算法分析:C语言描述_原书第2版

    数据结构与算法分析:C语言描述_原书第2版_高清版全书特点如下:1.专用一章来讨论算法设计技巧,包括贪婪算法、分治算法、动态...treap树、k-d树、配对堆以及其他相关内容;5.合并了堆排序平均情况分析的一些新结果。

    刷题算法提高阶段-数据结构6

    **Treap(树堆)** 是一种结合了二叉搜索树(BST)和堆属性的数据结构。它由Carlos R. Păcu于1989年提出,名字由"tree"(树)和"heap"(堆)组合而成。Treap的特点在于每个节点不仅包含键值(如在BST中),还包含一...

    数据结构与算法分析:C语言描述_原书第2版_高清版.zip

    在《数据结构与算法分析:C语言描述》中,作者精炼并强化了他对算法和数据结构...增加了高级数据 结构及其实现的内容,包括红黑树、自顶向下伸展树、treap树、k-d树、配对堆等。整合了堆排序平均情况分析的一些新结果。

Global site tag (gtag.js) - Google Analytics