hi, i recently heard about splay trees
and i am searching for a splaying algorithm...,i ve found one
but it isn't very easy to understand....so if anyone has to share an implementation followed by a short explanation it would be great!
PS: i 've undestand the basic concepts like zig, zig-zig, zig-zag but still the implementations out on the web utilize things that don't make much sense...
here is an alogorithm i found that i don't understand
void SplayTree::splay( const int & x, BinaryNode* t )
{
BinaryNode *leftTreeMax, *rightTreeMin;
static BinaryNode header;
header.left = header.right = nullNode;
leftTreeMax = rightTreeMin = &header;
nullNode->element = x; // Guarantee a match
for( ; ; )
if( x < t->element )
{
if( x < t->left->element )
rotateWithLeftChild( t );
if( t->left == nullNode )
break;
// Link Right
rightTreeMin->left = t;
rightTreeMin = t;
t = t->left;
}
else if( t->element < x )
{
if( t->right->element < x )
rotateWithRightChild( t );
if( t->right == nullNode ) //to neo t pou irthe apo to rotate....
break;
// Link Left
leftTreeMax->right = t;
leftTreeMax = t;
t = t->right;
}
else
break;
leftTreeMax->right = t->left;
rightTreeMin->left = t->right;
t->left = header.right;
t->right = header.left;
}
if anyone can shed some light, i would be gratefull!