How to implement juggle tree operations in C

[trickae]

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?

 

[neurocomp2003]

write it on paper. and is the term "juggle" tree correct I thought thta was a normal shuffle or a binary tree?

 

[trickae]

write it on paper. and is the term "juggle" tree correct I thought thta was a normal shuffle or a binary tree?

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 that's all -

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

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