>>>Hi
>>>
>>>I have implemented a binary tree in a table using at least the following three fields: id, left and right where id is the node identification and left and right are children of the node. Each child can point to another node id of the same table using its identification number. I used 0 when there is no child.
>>>
>>>I Created a class to iterate on that three using postfix search but it is not very performant. For a tree that has only 64 nodes, it takes about 5 seconds to do only a postfix search for each node without doing any piece of code during the search. A GOTO statement is used each time a child must be visited resulting of a lots of disk access. I know that the search time must increase as the tree growth but I can't live with a very poor performance like that.
>>>
>>>Is there a way to improve performance significantly using my tree implementation ?
>>>
>>>Is there any other way faster to implement a tree in a data base environment ?
>>>
>>>thanks in advance
>>
>>Francois,
>>
>>Admittedly, I haven't fooled with binary trees in about 10 years, so if its implementation has changed, I'll trust that you'll forgive me.
>>
>>I've read and re-read this posting several times, and my problem isn't in understanding what you're trying to do, but rather why you're trying to do it this way. In order to properly search a tree, there must be a member or members to be searched. The thing I keep coming back to is: Why not just create a index on the field(s) and seek the value you need?
>>
>>My gut feeling on this (and I may be way off base) this that you're try to establish some sort of hierarchy (the use of the word children). If this is the case, then my reaction would be that you're not using the b-tree correctly, since the purpose of the structure is to produced an organized (from least to greatest) list or structure.
>
>You're right, I must established a hierarchy with no more than two children for each node. Moreover, I must absolutely start from a node and visit every node I can find in its right child and do some action for each node found. Same thing applied to the left child, so it's not only a one element search. I know that a b-tree is very efficient in searching data but what about doing special action to the node's descendants ?
>
>I think that indexes are implemented as b-tree but you can only search one node, not the whole descendants, am I right ?
>
>Tell me if I missed something, but is it possible to get whole descendants of a node using b-tree approach ?
>
>If it is possible, could you give me a small example please.
>
>Thanks.
>
>>
>>At any rate, any attempt to locate a value in an organized list, such as a b-tree or sorted array, should require the exmaination of no more than Log2(n + 1) elements. In this case, with 64 nodes, that would mean 7 of them. If this is taking 5 seconds, somethings very wrong.
>>
>>hth,
>>
>>George

Francois,

I'm still not quite sure I get what you're trying to accomplish here, so let me see if I can sum up your problem correctly. You have a table containing, for want of a better word, "parents" who a related to no more than two "children", one (child) somehow lesser than the other. Is this right? If so, it seems like the solution is two relational tables with the appropriate indexes. In that sort of scenario, all you have to do is index the keys, relate them, and do a seek against the keyfield in the parent.

I see a lot of problems with trying to maintain both "parent" and "child" records in the same table. It would be very easy to get into a cylic relation, where the parent is a child of one of its children or a child of another parent. It become a nightmare to straighten out, especially if the table gained any significant size.

You're right about indexes. FoxPro does implement indexes as b-trees. Lastly, for what it's worth (most likely nothing in this forum) here's some code (in Pascal, I don't have the time right now to translate it) which traverses (with output noted at the appropriate proint) a binary tree in order.

PROCEDURE TRAVERSE(ROOT: ROOTPOINTERTYPE)

BEGIN {TRAVERSE}
IF ROOT <> NIL THEN
BEGIN
TRAVERSE(ROOT^.LEFT)
{Usually output goes here}
TRAVERSE(ROOT^.RIGHT)
END
END; {TRAVERSE}

hth,

George