Thread: any smarter ways to design this tree structure

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

    any smarter ways to design this tree structure

    Hello everyone,


    I am designing a small budget assignment/checking application for a hierarchy organization structure. The purpose is to check and assign the budget for each employee not exceeds the total budget of a department.

    The most difficult part is, a sub-department's total budget is not always lower than the upper level department's budget (i.e. the organization tree does not 100% reflects the relationship that father department node's budget is always more than that of child department node).

    So, I put many exception rules to check in such situation. I am wondering whether there is any smarter ways to implement and represent the budget assignment and check model?

    (I can re-write anything in this application, including data structure and algorithm, if the budget assignment and checking function is met.)

    An example,

    department goo under larger department foo, is represented as, /foo/goo, and /foo/zoo's budget is lower than /foo (this is a normal senses), but /foo/goo's budget is larger than /foo(this is a special rule, in the business model, even if goo under management of foo, its budget is not controlled by foo, so larger), and I maintain the remaining budget for each department,

    for employee, /foo/emp1 and /foo/zoo/emp2, I can check from father node to child node for making all child nodes' budget not exceed father node, but for /foo/goo/emp3, I have to check specially. This is my headache.

    If there are any smarter ways to represent the data structure and budget check, I would appreciated. :-)


    thanks in advance,
    George

  2. #2
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    First, mark the nodes that are exceptions (because they have their own budget independent of their parent) specially. Next, for each node, add up the budgets of their unmarked children. Check that this value does not exceed the node's own allocation.

    Unless the rules are more complicated than that. For example, if the budget of these exceptions comes partially from their parent. In that case, instead of a mark flag, give every node a "parent allocation" budget and a "separate allocation" budget. When adding up children, only add up parent allocations, but when testing the result against the node's own allocation, add the two parts together.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  3. #3
    Registered User
    Join Date
    Apr 2008
    Posts
    890
    Show us your design/code and we can suggest improvements, if necessary. It's hard to follow what's going on from your post.

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


    Your insights give me more ideas. Now I make the algorithm in details and want to let you review and comment. :-)

    1. Any node can have multiple childs, for example, foo has goo and zoo as two childs;

    2. If each child has its special money management system, I will put a special pointer to the money object, or else, it will share the same money source from parent (its money pointer points to the same money object of that of parent);

    3. In the money object, it contains the pool of nodes which gets money from the object and how much each node gets from the money object, from total amount of money of the money object, and the consumed money by all the nodes, we can make sure how much remains;

    4. When checking/assigning remaining budget for a specific child, traverse from the parent (root) of the tree to the specific child, and check its "money pointer" to see the remaining amount of money.

    Quote Originally Posted by CornedBee View Post
    First, mark the nodes that are exceptions (because they have their own budget independent of their parent) specially. Next, for each node, add up the budgets of their unmarked children. Check that this value does not exceed the node's own allocation.

    Unless the rules are more complicated than that. For example, if the budget of these exceptions comes partially from their parent. In that case, instead of a mark flag, give every node a "parent allocation" budget and a "separate allocation" budget. When adding up children, only add up parent allocations, but when testing the result against the node's own allocation, add the two parts together.

    regards,
    George

  5. #5
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    Sounds reasonable.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  6. #6
    Registered User
    Join Date
    May 2006
    Posts
    1,579
    Cool, CornedBee!


    Quote Originally Posted by CornedBee View Post
    Sounds reasonable.

    regards,
    George

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Binary Tree Search
    By C++Newbie in forum C++ Programming
    Replies: 7
    Last Post: 04-05-2011, 01:17 AM
  2. Tree structure programming question help?
    By Rob4226 in forum C++ Programming
    Replies: 4
    Last Post: 04-08-2008, 08:35 PM
  3. no tree data structure in STL
    By manav in forum C++ Programming
    Replies: 2
    Last Post: 01-11-2008, 01:23 AM
  4. design structure diagrams
    By ADR14N in forum C++ Programming
    Replies: 1
    Last Post: 05-17-2004, 06:41 AM
  5. Binary Search Tree, Inserting node
    By cheryl_li in forum C Programming
    Replies: 1
    Last Post: 09-13-2003, 03:53 AM