Thread: Left and Right rotation in a balanced binary tree problem

hi,

need some help with these rotations guys, going mental now, stucked with it for two days already...
trying to implement a balanced binary tree (also known as TREAP), where nodes inserted have both key and priority value. general rules are:
if node A is left child of node B -> key[A] < key[B]
if node A is right child of node B -> key[A] > key[B]

thats the easy part.
additional condition in the treap structure is as follows:
if A is a child of B -> priority(A) > priority(B)

which messes everything up, 'cos now with every insertion, if the priority of new node is smaller than we have to rotate the tree, either to the left or right.
ok, enough theory, here is the code that I've come up with so far, for inserting a new node :

public void insert(char id, double dd)
    {
    Node newNode = new Node(); // make new node
    newNode.iData = id; // key value
    newNode.dData = dd; // priority value
 
 
    if(root==null) // no node in root
        root = newNode;
    else if(root != null)  // root occupied
    {
        Node current = root; // start at root
        Node parent;
        Node temp;
 
        while(true)  //  (exits internally)
        {
            parent = current;
            if(id < current.iData && dd > current.dData) // go left?
            {
                current = current.leftChild;
                if(current == null) // if end of the line,
                { // insert on left
                    parent.leftChild = newNode;
                    return;
                }
 
            } // end if go left
            else if(id < current.iData && dd < current.dData)
            {
                if(parent == null)
                {
                    root = newNode;
                }
                else
                {
                    temp = current;
                    current = newNode;
                    newNode.leftChild = temp.rightChild;
                    temp.rightChild = temp;
                    return;
                }
 
            }
            else if(id > current.iData && dd > current.dData) // or go right?
            {
                current = current.rightChild;
                if(current == null) // if end of the line
                { // insert on right
                    parent.rightChild = newNode;
                    return;
                }
            }
            else if(id > current.iData && dd < current.dData)
            {
                if(parent == null)
                {
                    root = newNode;
                }
                else
                {
                    temp = current;
                    current = newNode;
                    newNode.rightChild = temp.leftChild;
                    temp.leftChild = temp;
                    return;
                }
            } // end else go right
        } // end while
        } // end else not root
    }    // end insert()

any comments, hints suggestions.. anything !!! would be great, don't want to go completly bonkers, with xmas so close

I'm guessing you are a student and this due the 10th January 2011? I am probably in you class LOL!

I need help with this too... No idea what the lecturer wants and I have no idea why he is giving us MIT based coursework when he has not prepared us for the work. I'm convinced the whole class is in the same boat and it's sinking FAST!

So, someone please help us!

Break the problem up into steps...you could do so by splitting the insertion into 2 steps: add the node to the binary tree, then rotate the node (if needed) based upon priority. You could do both using a while loop, or alternatively using recursion