Data-Structures-And-Algorithms/splaytree1.java at main · saranathrajaram11/Data-Structures-And-Algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
class node{
int data;
node left,right,parent;

node(int data)
{
this.data=data;
left=right=parent=null;
}
}

class splaytree1{
node root;

splaytree1()
{
root=null;
}

void insert(int value)
{
node dup=root;
node p=null;

if(dup==null)
  root=new node(value);
while(dup!=null)
{
p=dup;
if(value<dup.data)
dup=dup.left;

else
dup=dup.right;
}
dup=new node(value);
if(p=null)
root=dup;
else if(dup.data<p.data)
p.left=dup;
else
p.right=dup;
splay(dup);


void splay(node d)
{
while(dup.parent!=null)
{
if(dup.parent.parent==null)
{
if(dup==dup.parent.left)
rightrotate(dup.parent)
else
leftrotate(dup.parent)
}
else {
if(dup==dup.parent.left && dup.parent.parent.left==dup.parent )//zigzig
{
rightrotate(dup.parent.parent);
rightrotate(dup.parent);
}
else if (dup==dup.parent.right && dup.parent==dup.parent.parent.right)
{
  leftroate(dup.parent.parent);
  leftroate(dup.parent);
}
else if(dup==dup.parent.left && dup.parent==dup.parent.right)
{
  rightrotate(dup.parent);
  rightrotate(dup.parent);
}
else{
  leftrotate(dup.parent);
  leftrotate(dup.parent);
}
}
}

void leftrotate(node h)
{
  node x;

}

void rightrotate(node h)
}

}
}       //end of the class