Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Juggle trees help

  1. Jan 27, 2006 #1
    How do we find information on how to modify a binary Search tree to that of a juggle tree. SUch as add, delete, treaverse etc. Somehow all can be done with a call to the recursive function juggle.

    basics of a juggle tree

    given

    a binary tree will have two nodes left and right, and another to its parent
    if the number is less than the root node - it will be placed to the left, if its greater than the root then it will be placed on the right. If there is already is a node on either left or right pointers then the comparison is made with the next node and it will go either left or right and so forth.

    bst
    -----------10-----
    ---------4----11
    -------3---6-----12
    -----2----5--8---------
    ----1--------7-9--------


    juggle(4,bst)

    traverses the list, looks for '4'. then it will keep everything to the left of 4 and go up to the parent. Parent is now the right node of 4. Everything on the right of 4 is now the left node of the parent.


    juggle(4,bst)

    ------------4
    ---------3----10
    -------2-----6---11
    -----5--------8----12
    -------------7-9
    (edit: i appologize for the 'guitar tab' notation but the spacing kept getting messed up)
    This must be done for multiple parent nodes let so if we took 2 of the original bst we'd have to repeat this process by replacing the right node by the upper parent.

    * i.e we'd check the last right leaf of the current tree and put the parent * at the end of that and so forth.

    any help on or further information on how this would be done in C?
     
    Last edited: Jan 27, 2006
  2. jcsd
  3. Jan 27, 2006 #2
    write it on paper. and is the term "juggle" tree correct I thought thta was a normal shuffle or a binary tree?
     
  4. Jan 28, 2006 #3
    for the redrawn diagrams see attachement


    well our assingment spec called it a juggle tree and we need calls to this juggle function to insert and delete.

    i just need some rough help with the theory for these two functions thats all -

    if you guys want i can post my juggle function that i've wrote so far.


    Code (Text):


    typedef struct node {
      key          info;
      struct node *left;
      struct node *right;
      struct node *parent;
    } *JuggleTree;


    JuggleTree* findNode(key data, JuggleTree *jtr)
    {
        if (jtr != NULL )
        {
            if (data < jtr->info)
                jtr = findNode(data, jtr->left);
            else if (data > jtr->info)
                jtr = findNode(data, jtr->right);
            else if (data != jtr->info)
                return NULL;
        }
        return jtr;
    }

    void juggle (key data, JuggleTree *jtr)
    {
        JuggleTree* currNode = findNode(data, jtr);
       
        if(currNode->parent != NULL){
            JuggleTree* parentNode = currNode->parent;
            if (parentNode->parent != NULL) {
                if(parentNode->right == currNode)
                {
                    JuggleTree* leftNode = currNode;
                    while (currNode->left != NULL) {
                        leftNode = leftNode->left;
                    }
                    leftNode->left = parentNode;
                    parentNode->parent = leftNode;
                    currNode->parent = parentNode->parent;
                    currNode->parent->left = currNode;
                    parentNode->right = NULL;
                }
                else{              
                    parentNode->parent->left = parentNode->right;
                    parentNode->right = parentNode->parent;
                    parentNode->parent->parent = parentNode;
                    parentNode->parent = NULL;
                    jtr = parentNode;
                }
                juggle(data, jtr);
            }
            else {
                parentNode->left = currNode->right;
                parentNode->parent = currNode;
                currNode->right = parentNode;
                currNode->parent = NULL;
                jtr = currNode;
            }
        }
                           
        if (currNode->parent == NULL) {
             jtr = currNode;
        }          
    }


     

    thanx again
     

    Attached Files:

    Last edited: Jan 28, 2006
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Juggle trees help
  1. Binary tree (Replies: 5)

Loading...