any ideas to improve search performance in a tree structure

This is a discussion on any ideas to improve search performance in a tree structure within the C Programming forums, part of the General Programming Boards category; Hello everyone, I am developing an application which contains a tree structure. The tree structure reflects the management structure of ...

  1. #1
    Registered User
    Join Date
    May 2006
    Posts
    1,579

    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?


    thanks in advance,
    George

  2. #2
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,801
    Is the tree balanced? How many child nodes are there per parent node?
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  3. #3
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,535
    > 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?
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  4. #4
    Registered User
    Join Date
    May 2006
    Posts
    1,579
    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

  5. #5
    Registered User
    Join Date
    May 2006
    Posts
    1,579
    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

  6. #6
    Registered User
    Join Date
    Mar 2006
    Posts
    725
    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)
    Code:
    #include <stdio.h>
    
    void J(char*a){int f,i=0,c='1';for(;a[i]!='0';++i)if(i==81){
    puts(a);return;}for(;c<='9';++c){for(f=0;f<9;++f)if(a[i-i%27+i%9
    /3*3+f/3*9+f%3]==c||a[i%9+f*9]==c||a[i-i%9+f]==c)goto e;a[i]=c;J(a);a[i]
    ='0';e:;}}int main(int c,char**v){int t=0;if(c>1){for(;v[1][
    t];++t);if(t==81){J(v[1]);return 0;}}puts("sudoku [0-9]{81}");return 1;}

  7. #7
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,535
    > 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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help with insert/delete binary search tree
    By Nazgulled in forum C Programming
    Replies: 39
    Last Post: 03-25-2009, 04:24 PM
  2. Replies: 0
    Last Post: 11-04-2006, 10:07 AM
  3. Binary Search Tree
    By penance in forum C Programming
    Replies: 4
    Last Post: 08-05-2005, 05:35 PM
  4. searching and insertion in a binary search tree
    By galmca in forum C Programming
    Replies: 1
    Last Post: 03-26-2005, 04:15 PM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21