STL for AVL tree?

[Josh Peters]

Does anyone know if there's an STL container we might be able to
modify to use as an AVL? I'm about half way through the project and
it's taking forever so any tips that would save some time (especially
this week) would be greatly appreciated.

Thanks in advance,
-josh

[Konstantin Vyshetsky]

STL doesn't have a tree container. I would recommend writing your own binary search tree and then just adding a few methods to balance it. I found it to be helpful printing out each node and what it links too when writing and debugging the tree. 

- Kon

[Josh Peters]

second question.... Are we supposed to have a class for the tree, and
a class for the node of the tree? or like how does it know which node
is the root otherwise?

[Josh Peters]

thanks for the info!

On Oct 3, 6:11 pm, Konstantin Vyshetsky <kvyshet...@gmail.com> wrote:
> STL doesn't have a tree container. I would recommend writing your own binary
> search tree and then just adding a few methods to balance it. I found it to
> be helpful printing out each node and what it links too when writing and
> debugging the tree.
> - Kon
>

[Konstantin Vyshetsky]

I used a separate class for the node, this class will contain your data and also pointers to the left node and right node. For my tree I found it useful to also have a pointer to the top. Your tree class itself should store the root node, and from it you can reach any other node in the tree. Another thing I found useful is to have public methods for add/delete etc, that deal with the root, and then have them call on private recursive methods.

- Kon

[prateek grover]

Did anyone found a decent , organized algorithm/code for delete/remove
function?

[Konstantin Vyshetsky]

There are 3 scenarios for delete/remove:

1) Node has no children, you simply remove it and the pointers pointing to it.

2) Node has one child, you adjust the pointers from it's child and it's parent.

3) Node has two children, in this situation you can either find the next element closest to it from the left or from the right.

- For example if you want next largest, go to it's right child and then keep going left until you reach a node that has no left children. That will be the one to replace the node you're deleting. What you want to do is handle pointers on the node that's replacing, in case it has children itself etc, then simply put it's data into the node you want to remove.

Hope this helps,

Kon

[prateek grover]

thanks, one more thing..its the HW due today or Tuesday
 midnight?

[Konstantin Vyshetsky]

04-Oct-201111:59PM
According to turnitin :)

[Frank (sjsu) Lin]

Hi Kons,

It is really good, not only for your answer, but also for your attitude of helping others.

cheers,
frank