- #1
trickae
- 83
- 0
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?
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: