DaniWeb Forum Index > Software Development > C++

C++ RSS

splaying algorithm

Please support our C++ advertiser: Intel Parallel Studio Home

•

Join Date: Nov 2006

Posts: 202

Reputation: n.aggel is an unknown quantity at this point

Solved Threads: 11

n.aggel

Offline

Posting Whiz in Training

splaying algorithm

Aug 20th, 2007

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

 Help with Code Tags 
 c++ Syntax (Toggle Plain Text) 
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;
        }
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;
        }