any ideas to improve search performance in a tree structure

[George2]

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?


thanks in advance,
George

[hk_mp5kpdw]

Is the tree balanced? How many child nodes are there per parent node?

[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?

[George2]

Hi 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

[George2]

Thank you 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

[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.

~~~~MANAGEMENT TREE~~~~
        CEO Doe (ID 1)
                   |
        ------------------------------
         |                                    |
Director John (ID 2)   Director Smith (ID 3)

~~~~BINARY TREE~~~~
   John(2)
   /          \
Doe(1)  Smith(3)

[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.