树堆(Treap)图文详解与实现

1.Treap的定义

树堆(Treap)是二叉排序树(Binary Sort Tree)与堆(Heap)结合产生的一种拥有堆性质的二叉排序树。

但是这里要注意两点,第一点是Treap和二叉堆有一点不同,就是二叉堆必须是完全二叉树,而Treap并不一定是;第二点是Treap并不严格满足平衡二叉排序树(AVL树)的要求,即树堆中每个节点的左右子树高度之差的绝对值可能会超过1,只是近似满足平衡二叉排序树的性质。

Treap每个节点记录两个数据,一个是键值,一个是随机附加的优先级,Treap在以关键码构成二叉排序树的同时,又以结点优先级形成最大堆和最小堆。所以Treap必须满足这两个性质,一是二叉排序树的性质,二是堆的性质。如下图,即为一个树堆。

2.Treap的特点

Treap因在BST中加入了堆的性质,在以随机顺序将节点插入二叉排序 树时,根据随机附加的优先级以旋转的方式维持堆的性质,其特点是能基本实现随机平衡的结构。相对于其他的平衡二叉搜索树,优点是实现简单,因为Treap维护堆性质的方法只用到了旋转,只需要两种旋转,易于维护,可用于高效快速查找。

3.Treap的操作

3.1Treap的插入

给节点随机分配一个优先级,先和二叉排序树(又叫二叉搜索树)的插入一样,先把要插入的点插入到一个叶子上,然后再维护堆的性质。

以最小堆为例,如果当前节点的优先级比其根节点小就旋转。如果当前节点是根的左子节点就右旋。如果当前节点是根的右子节点就左旋。 即左旋能使根节点转移到左边,右旋能使根节点转移到右边。

下图中,当X节点优先级小于Y节点时右旋和Y节点优先级小于X节点的左旋,其左右旋转如下图:

插入写成递归形式的话,只需要在递归调用完成后判断是否满足堆性质,如果不满足就旋转,实现相对简单。其插入过程示例图如下:

时间复杂度: 由于旋转是O(1)的,最多进行h次(h是树的高度),插入的复杂度是O(h)的,在期望情况下h=O(log n),所以它的期望复杂度是O(log n)。

3.2Treap的删除

(1)找到相应的结点; (2)若该结点为叶子结点,则直接删除; (3)若该结点为只包含一个叶子结点的结点,则将其叶子结点赋值给它; (4)若该结点为其他情况下的节点,则进行相应的旋转,具体的方法就是每次找到优先级最小的儿子,向与其相反的方向旋转,直到该结点为上述情况之一,然后进行删除。

时间复杂度: 最多进行O(h)次旋转,期望复杂度是O(log n)。

3.3Treap的查找

根据Treap具有二叉搜索树的性质,可以快速查找所需节点。 时间复杂度: 期望复杂度是O(log n)。

4 数据结构的设计

结点采用结构体存储,定义如下:

struct node
{ 
   int key;//关键字 
   int priority;//随机优先级
   node* left;//左节点
   node* right;//右节点
};

5.具体实现

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef struct node Node;
typedef struct treap_t Treap;
typedef Node* nodePoint;

struct node
{ 

   int key;//关键字 
   int priority;//随机优先级
   Node* left;//左节点
   Node* right;//右节点

};

Node* root;//Treap的根结点

//左旋转
 void rotate_left(Node* &node)
 {
   Node* x = node->right;
   node->right = x->left;
   x->left =node;
   node = x;
 }

 //右旋转
 void rotate_right(Node* &node)
 {
   Node* x = node->left;
   node->left = x->right;
   x->right = node;
   node = x;
 }

 //插入操作
 void treap_insert(Node* &root, int key, int priority)
 {
   //根为NULL,则直接创建此结点为根结点
   if (root == NULL)
   {
     root = (Node*)new Node;
     root->left = NULL;
     root->right = NULL;
     root->priority = priority;
     root->key = key;
   }
   //向左插入结点
   else if (key <root->key)
   {
     treap_insert(root->left, key, priority);
     if (root->left->priority < root->priority)
       rotate_right(root);
   }

   //向左插入结点
   else
   {
     treap_insert(root->right, key, priority);
     if (root->right->priority < root->priority)
       rotate_left(root);
   }
 }

 //删除结点操作
 void treap_delete(Node* &root, int key)
 {
   if (root != NULL)
   {
     if (key < root->key)
       treap_delete(root->left, key);
     else if (key > root->key)
       treap_delete(root->right, key);
     else
     {
       //左孩子为空
       if (root->left == NULL)
         root = root->right;

       //右孩子为空
       else if (root->right == NULL)
         root = root->left;

       //左右孩子均不为空
       else
       {
         //先旋转,然后再删除
         if (root->left->priority < root->right->priority)
         {
           rotate_right(root);
           treap_delete(root->right, key);
         }
         else
         {
           rotate_left(root);
           treap_delete(root->left,key);
         }
       }
     }
   }
 }

//中序遍历
void in_order_traverse(Node* root)
{
  if (root!= NULL)
  {
    in_order_traverse(root->left);
    printf("%d\t", root->key);
    in_order_traverse(root->right);
  }
}

//计算树的高度
int depth(Node* node)
{
    if(node == NULL)
        return -1;
    int l = depth(node->left);
    int r = depth(node->right);
    return (l < r)?(r+1):(l+1);
}

int main()
{
  srand(time(0));

  //产生最大伪随机数0至RAND_MAX(32767)
  //printf("%d\n",RAND_MAX);

  //随机插入10个节点
  printf("----------------------创建Treap树堆-----------------------\n");
  printf("顺序插入0至9十个数,键值与优先级如下\n");
  for (int i = 0; i < 10; i++)
  {
    int pri=rand();
    printf("key:%d priority:%d\n",i,pri);
    treap_insert(root,i,pri);
  }

  //中序遍历Treap
  printf("\n插入完毕,中序遍历Treap所得结果为:\n");
  in_order_traverse(root);

  printf("\nTreap高度:%d\n", depth(root));

  printf("----------------------删除结点-----------------------\n");
  printf("请输入要删除的结点键值\n");
  int rmKey;
  scanf("%d",&rmKey);
  treap_delete(root, rmKey);

  printf("\n删除完毕,中序遍历Treap所得结果为:\n");
  in_order_traverse(root);

 printf("\nTreap高度:%d\n", depth(root));
  getchar();
  getchar();
  return 0;
}

运行结果截图:


参考文献

[1]http://blog.csdn.net/yang_yulei/article/details/46005845 [2]http://www.cnblogs.com/shuaiwhu/archive/2012/05/06/2485894.html

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小灰灰

JDK容器学习之TreeMap (一) : 底层数据结构

TreeMap 在日常的工作中,相比较与HashMap而言,TreeMap的使用会少很多,即使在某些场景,需要使用到排序的Map时,也更多的是选择 Linke...

26290
来自专栏Android研究院

数据结构-线性表(顺序表与链表的基本知识 以及ArrayList 源码分析)

比如:美女和野兽,抽象的事物表示美女:头发长 前凸后翘。。。 可以表示为一个数据单元,野兽也是一个数据单元。

27110
来自专栏大数据和云计算技术

算法基础6:二叉树查找

算法是基础,小蓝同学准备些总结一系列算法分享给大家,这是第6篇《二叉树查找》,非常赞!希望对大家有帮助,大家会喜欢! 前面系列文章: 归并排序 #算法基...

37250
来自专栏python学习路

数据结构与算法(二)

排序与搜索 排序算法(英语:Sorting algorithm)是一种能将一串数据依照特定顺序进行排列的一种算法。 排序算法的稳定性 稳定性:稳定排序算法会让原...

36780
来自专栏数据结构与算法

2010 求后序遍历

2010 求后序遍历 时间限制: 1 s 空间限制: 64000 KB 题目等级 : 白银 Silver 题目描述 Description 输入一...

33060
来自专栏用户画像

6.3.2 B+树基本概念

2)非叶根(不是叶子的根结点)结点至少有两棵子树,其他每个分支结点至少有【m/2】(向下取整)棵子树。(B树是要求至少2棵子树)

10120
来自专栏Bingo的深度学习杂货店

Q101 Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric aroun...

33680
来自专栏Java爬坑系列

【Java入门提高篇】Day26 Java容器类详解(八)HashSet源码分析

  前面花了好几篇的篇幅把HashMap里里外外说了个遍,大家可能对于源码分析篇已经讳莫如深了。

11740
来自专栏猿人谷

二叉搜索树的后序遍历序列

题目:输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。如果是返回true,否则返回false。 例如输入5、7、6、9、11、10、8,由于这一...

21370
来自专栏个人分享

JAVA源码走读(一) HashMap与ArrayList

HashMap是基于哈希表的Map接口的实现。此实现提供所有可选的映射操作,并允许使用null值和null键。此类不保证映射的顺序,特别是它不保证该顺序恒久不变...

11620

扫码关注云+社区

领取腾讯云代金券