954,202 Members — Technology Publication meets Social Media
Username:
Password:
Lost login information?
Have something to say? Contribute New Article Reply to this Article

splaying algorithm

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!

n.aggel
Posting Whiz in Training
203 posts since Nov 2006
Reputation Points: 23
Solved Threads: 12
 

This article has been dead for over three months

Post: Markdown Syntax: Formatting Help
You