How do you make an insert method in a LS-RB tree?

[Deiby]

Hi there!
I'm having troubles making an insert method on a Leftest Son - Right Brother tree (I'm sorry if I wrote it wrong, please make me know), I just know how to make it on a binary tree, but if you know this kind of tree and know the implementation of this method, I will be very pleased if you help me.
Thank you and bye.


I'm sorry I didn't explain deeply how this tree works, first of all you may know that my native languaje is spanish, so sorry for any mistake.
In this kind of tree, any node may have any number of 'sons', but each node only has a pointer to the son in the left, how do you know the father of the other sons? Well, the son on the left begins a pionter list of the remaining sons, so a node has no pointers to all his sons, only the brother on the left can say who is their father.
There's something more I've just learned: it's very difficult to know in which node you have to insert, but knowing the father of a node when inserting makes things more easier.
I hope now you may understand and could help me.

[Manish Malik]

Never heard of it before ... may be there's a better name ...

[Gabriel Fleseriu]

I also never heard of such a tree before. If you don't know another name for it then maybe you could describe what it does...

[Bob Davis]

I'm not sure, but I think the tree that he is talking about is a way of representing a general tree within the structure of a binary tree. Basically, at each node, the left link points to that node's first child, and its right link points to its next sibling. Therefore, to add a node, you do something like this:


void addNode(Node *parent, Node *newChild)
{
// if parent has children already,
// we must follow its first child link and then traverse through its siblings.
if (parent->getLeft() != NULL)
{
parent = parent->getLeft();
while (parent->getRight() != NULL)
{
// traverse through any siblings on this tree level that might already exist
parent = parent->getRight();
}

// now parent points to the node we want to add onto.
parent->setRight(newChild);
}

// if we get here, then parent has no children. place the new child on its left link.
else parent->setLeft(newChild);
}


I have not tested this code, and it doesn't solve the traversal problem of actually finding the node to add to. Plus, this may not even be the tree you're talking about. I hope this helps.

[Yves : sorry, I have a low resolution, so long code lines look ugly ;) ]

[Gabriel Fleseriu]

Originally posted by Bob Davis
I'm not sure, but I think the tree that he is talking about is a way of representing a general tree within the structure of a binary tree. Basically, at each node, the left link points to that node's first child, and its right link points to its next sibling.

Interesting. I think that such a tree could have any number of root nodes, isn't it? Or, better said, it has one root node and any number of nodes that have the same deepness level as the root node. Also, if a node has only the 'left' and 'right' links (but no 'parent' link) then it is a hard job to find all siblings of a given node.

I think that te version with a 'parent' link is very simmilar to what the standard Windows tree control implements...

[Bob Davis]

I think your observation of having a number of root nodes is correct; actually in this case, I would think of the structure representing a forest, with each root being its own tree. I don't think that's how this particular implementation is meant to be used, but I guess it would work.

I have never seen anyone else's (read: well-coded) implementation of a class like this. I wrote a very sloppy one in Java for a project I was working on a while back that I never finished. It was basically a tree for a wizard sort of system, that asks questions, then asks another based on the answer to the previous question, therefore traversing down the tree. It was meant to be used as a troubleshooter for customers of an Internet service, but it fell by the wayside. The structure worked pretty well, though. I'd be interested in seeing a well-written version. :)