any ideas to improve search performance in a tree structure

• 06-07-2006
George2
any ideas to improve search performance in a tree structure
Hello everyone,

I am developing an application which contains a tree structure. The tree structure reflects the management structure of a big company -- child node represents the employees managed by direct manager (parent node), one parent node may have multiple (various) number of child nodes (employees he/she managed in his/her department).

I need to find all the employees a manager managed in the tree structure, the direct child node, the child node's child node, ... and so on (for example, if he is a senior manager, there are multiple levels of child nodes).

Currently, I am using brute force tree traverse approach to print all (direct and indirect) child nodes -- layer by layer. The tree is very large. I am wondering whether there are any good ideas about how to improve the search performance?

George
• 06-08-2006
hk_mp5kpdw
Is the tree balanced? How many child nodes are there per parent node?
• 06-08-2006
Salem
> Is the tree balanced?
Yeah, I thought that at first, but the tree represents the management structure of the company (however unbalanced it may be).

@George2
How is the list of each subordinate of each manager represented?
• 06-08-2006
George2
Hi hk_mp5kpdw,

Quote:

Originally Posted by hk_mp5kpdw
Is the tree balanced? How many child nodes are there per parent node?

It is not balanced. For each parent node, there may be 0-50 child nodes.

Any ideas?

regards,
George
• 06-08-2006
George2
Thank you Salem,

Quote:

Originally Posted by Salem
> Is the tree balanced?
Yeah, I thought that at first, but the tree represents the management structure of the company (however unbalanced it may be).

@George2
How is the list of each subordinate of each manager represented?

Yes, as you presented, it is un-balanced since it represents a real management structure.

What do you mean "list of each subordinate of each manager represented" -- do you mean how child nodes of a parent nodes are organized? Currently, I store it in a linked list. But it is not mandatory, I can re-design it to achieve overall performence improvement.

Any ideas?

regards,
George
• 06-08-2006
jafet
You could place the nodes (all layers) into a binary tree (or similiar datastructure) for quick searching, and link to the nodes from your original tree. It would incur a little overhead in terms of space, though.

Code:

```~~~~MANAGEMENT TREE~~~~         CEO Doe (ID 1)                   |         ------------------------------         |                                    | Director John (ID 2)  Director Smith (ID 3) ~~~~BINARY TREE~~~~   John(2)   /          \ Doe(1)  Smith(3)```
• 06-09-2006
Salem
> do you mean how child nodes of a parent nodes are organized? Currently, I store it in a linked list.
I think I'd probably allocate a variable length array (using malloc), and adjust it's length (using realloc) as necessary.
Given that the program is likely to be run many times before the next promotion, recruitment, sacking or whatever.

What sort of performance problem are you seeing?
I can't really imagine it taking more than a couple of seconds to traverse even the largest of management trees.

> I can re-design it to achieve overall performence improvement.
Code readability and maintainability is also a metric which should concern people.
As it testability.