treap,在平衡二叉搜索树中是一种相对简单的数据结构，它的本质是tree +heap。
它即有二叉树的特性，即节点的左孩子的关键值（key）小于节点的关键值，节点右孩子的关键值大于节点的关键值。 我们前文讲二叉搜索树的随机化策略的时候提到过，二叉搜索树可能退化成链表，降低了搜索性能。所以需要进行各种处理来防止这种退化的产生。在我的博文
随机二叉搜索树的C实现 中提到了一种解决的办法，即通过随机化的策略，使每个节点成为根的概率相等。 treap维护了一个优先级的字段，也就是heap部分。对于最小堆而言，节点的左右孩子的优先级（priority）要高于节点本身的优先级。
对于treap的插入而言，分两步走：
1 和普通的二叉搜索树一样，根据key的值，插入到二叉树
2通过旋转调整。新插入节点 可能破坏了heap的性质，即新节点可能优先级低于其父亲节点。需要调整。
如下图所示 （图来自byvoid大牛的文章，如有侵权，请通知我立即删除）
第一步 插入
第二步 根据优先级字段调整
不满足heap的要求，继续调整（4节点的优先级15 低于5节点的20，不符合最小堆的要求）
还是没解释清楚，为什么加上 优先级字段，维护了heap的性质，就保证了二叉树的平衡。秘密在于，优先级字段的值是随机值。换句话说，就是我们随机指定优先级字段。这种随机性来保证二叉树的平衡。
讲完插入，继续解释删除
情况一,该节点为叶节点或链节点,则该节点是可以直接删除的节点。若该节点有非空子节点,用非空子节点代替该节点的,否则用空节点代替该节点,然后删除该节点。
情况二,该节点有两个非空子节点。我们的策略是通过旋转,使该节点变为可以直接删除的节点。如果该节点的左子节点的优先级小于右子节点的优先级,右旋该节点,使该节点降为右子树的根节点,然后访问右子树的根节点,继续讨论;反之,左旋该节点,使该节点降为左子树的根节点,然后访问左子树的根节点,继续讨论,知道变成可以直接删除的节点。
情况1
情况2
-------------------------------------treap.h-------------------------------------------------------------
#ifndef _TREAP_H
#define _TREAP_H
typedef int key_type ;
typedef int ;
typedef struct _treap_node
{
struct _treap_node *left;
struct _treap_node *right;
key_type key;
prio_type priority;
int data;
}treap_node;
typedef struct _treap
{
treap_node* root;
}treap;
treap_node* treap_insert(treap_node* root,int key,int data);
treap_node* treap_delete(treap_node* root,int key);
#endif
----------------------------------------treap.c-----------------------------------------------------
#include
#include"treap.h"
#include
treap_node* treap_left_rotate(treap_node *node)
{
assert(node->right != NULL);
treap_node* right = node->right;
node->right = right->left;
right->left = node;
return right;
}
treap_node* treap_right_rotate(treap_node* node)
{
assert(node->left !=NULL)
treap_node* left = node->left;
node->left = left->right;
left->right->node;
return left;
}
treap_node* treap_allocnode(key_type key,int data)
{
treap_node* node = NULL;
node = (treap_node*)malloc(sizeof(treap_node));
if(node == NULL)
return NULL;
else
{
node->left = node->right = NULL;
node->key = key;
node->data = data;
node->priority = rand()*rand();
return node;
}
}
void treap_freenode(treap_node* node)
{
if(node)
free(node);
}
treap_node* treap_insert(treap_node* root,int key,int data)
{
if(root == NULL)
{
treap_node *new_node = treap_allocnode(key,data);
return new_node;
}
if(root->key > key)
{
root->left = treap_insert(root->left,key,data);
if(root->left->priority < root->priority)
return treap_right_rotate(root);
else
return root;
}
if(root->key < key)
{
root->right = treap_insert(root->right,key,data);
if(root->right->priority < root->priority)
return treap_left_rotate(root);
else
return root;
}
}
treap_node* treap_delete(treap_node* root,int key)
{
if(root == NULL)
{
return NULL;/*not find a element with key equal to key*/
}
if(root->key == key)
{
if(root->left == NULL || root->right == NULL)
{
treap_node* delnode =root;
if(root->left == NULL)
root = root->right;
else
root = root->left;
treap_freenode(delnode);
return root;
}
else
{
if(root->left->priority < root->right->priority)
{
treap_node* retnode = root->left;
treap_right_rotate(root);
retnode->right = treap_delete(root);
return retnode;
}
else
{
treap_node* retnode = root->right;
treap_left_rotate(root);
retnode->left = treap_delete(root);
return retnode;
}
}
}
else
{
if(root->key < key)
root->right = treap_delete(root->right,key);
else
root->left = treap_delete(root->left,key);
return root;
}
}
------------------------------treap_test.c-------------------------------------------------
#include
#include
#include
#define NODE_NUM 10
#define random(x) (rand()%x)
void test_treap()
{
int i;
int array_random[NODE_NUM] ;
for(i = 0;i
array_random[i] = rand(10000);
treap my_treap;
my_treap.root = NULL;
for(i = 0;i
{
my_treap.root = treap_insert(my_treap.root,array_random[i],array_random[i]);
}
}
int main()
{
test_treap();
return 0;
}
我相信总有一篇文章能清楚明白的解释我想了解的知识。对于treap这种数据结构，这篇文章无疑是：
byvoid大牛的文章《随机平衡二叉查找树 Treap 的分析与应用》，强烈推荐byvoid的这篇文章。看了这篇文章，基本上就不需要看听我在此JJYY了。
参考文献：
1 byvoid大牛的文章《随机平衡二叉查找树 Treap 的分析与应用》
2 维基百科
阅读(1863) | 评论(0) | 转发(2) |
