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


    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.



    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.


    (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;
                    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
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook