juggle trees help

[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 thats 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