treapツリーおよび関連アルゴリズム
14208 ワード
<!--
-->
-->
#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct treenode
{
int key;
int priority;
int flag;
treenode* parent;
treenode* lchild;
treenode* rchild;
}node,*pnode;
pnode treeroot=NULL;
void adjusttree(pnode p)
{
if(p->parent==NULL)return;
if(p->priority>=p->parent->priority)return;
if(p->flag==1)//p lie in the left subtree, rotate right
{
pnode prt=p->parent,rchild=p->rchild;
if(p->parent->flag==0)
{
prt->lchild=rchild;
if(rchild)rchild->parent=prt;
if(rchild)rchild->flag=1;
p->rchild=prt;
prt->parent=p;
prt->flag=2;
treeroot=p;
p->parent=NULL;
p->flag=0;
return;
}
else if(p->parent->flag==1)
{
pnode grdp=prt->parent;
prt->lchild=rchild;
if(rchild)rchild->parent=prt;
if(rchild)rchild->flag=1;
p->rchild=prt;
prt->parent=p;
prt->flag=2;
grdp->lchild=p;
p->parent=grdp;
p->flag=1;
adjusttree(p);
}
else if(p->parent->flag==2)
{
pnode grdp=prt->parent;
prt->lchild=rchild;
if(rchild)
rchild->parent=prt;
if(rchild)
rchild->flag=1;
p->rchild=prt;
prt->parent=p;
prt->flag=2;
grdp->rchild=p;
p->parent=grdp;
p->flag=2;
adjusttree(p);
}
}
else if(p->flag==2)//p lie in the right tree, rotate left
{
pnode prt=p->parent,lchild=p->lchild;
if(p->parent->flag==0)
{
prt->rchild=lchild;
if(lchild)lchild->parent=prt;
if(lchild)lchild->flag=2;
p->lchild=prt;
prt->parent=p;
prt->flag=1;
treeroot=p;
p->parent=NULL;
p->flag=0;
return;
}
else if(p->parent->flag==1)
{
pnode grdp=prt->parent;
prt->rchild=lchild;
if(lchild)lchild->parent=prt;
if(lchild)lchild->flag=2;
p->lchild=prt;
prt->parent=p;
prt->flag=1;
grdp->lchild=p;
p->parent=grdp;
p->flag=1;
adjusttree(p);
}
else if(p->parent->flag==2)
{
pnode grdp=prt->parent;
prt->rchild=lchild;
if(lchild)lchild->parent=prt;
if(lchild)lchild->flag=2;
p->lchild=prt;
prt->parent=p;
prt->flag=1;
grdp->rchild=p;
p->parent=grdp;
p->flag=2;
adjusttree(p);
}
}
}
void insert_node(pnode root,pnode p,pnode parent,int flag)
{
if(root==NULL)
{
p->flag=flag;
p->parent=parent;
if(flag==1)parent->lchild=p;
if(flag==2)parent->rchild=p;
if(p->priority<p->parent->priority)adjusttree(p);
return;
}
if(root->key>=p->key)insert_node(root->lchild,p,root,1);
else insert_node(root->rchild,p,root,2);
}
pnode createnode(int key,int priority)
{
pnode tmp;
tmp=(pnode)malloc(sizeof(node));
tmp->flag=0;
tmp->parent=NULL;
tmp->rchild=NULL;
tmp->lchild=NULL;
tmp->key=key;
tmp->priority=priority;
return tmp;
}
void dsptree(pnode p)
{
if(p)dsptree(p->lchild);
if(p){printf("#%dsubtree key=%d
",p->flag,p->key);}
if(p)dsptree(p->rchild);
}
int main()
{
treeroot=createnode(10,8);
pnode n1=createnode(6,5);
pnode n2=createnode(2,3);
pnode n3=createnode(4,3);
pnode n4=createnode(9,2);
insert_node(treeroot,n1,0,0);
insert_node(treeroot,n2,0,0);
insert_node(treeroot,n3,0,0);
insert_node(treeroot,n4,0,0);
dsptree(treeroot);
system("pause");
return 0;
}