A Flexible Tree Structure

Tony Marston - 31st October 2001

1. A traditional inflexible design
2. Trees, Nodes and Leaves
3. A modern flexible design
4. Building your Tree structure
4a. Define a Tree Type
4b. Define Levels within a Tree Type
4c. Adding Nodes to a Tree Level
4d. Linking Nodes with their parents
4e. Checking a Node's parentage
5. Adding another Tree Type
6. Adding a new Level into an existing Structure
7. Removing a Level from an existing Structure
8. Conclusion

1. A traditional inflexible design

In my many years as a software engineer I have often come across the requirement for a structure that will hold some sort of hierarchy, as represented in figure 1:

Figure 1 - A typical hierarchical structure

flexibletrees01.gif

A typical example of a structure like this is an organisational hierarchy, as shown in figure 2:

Figure 2 - An Organisational hierarchy

flexibletrees02.gif

A structure like this is typically implemented in an Entity-Relationship (E-R) diagram as shown in figure 3:

Figure 3 - A typical E-R diagram

flexibletrees03.gif

This is perfectly legitimate, but it results in a rigid rather than a flexible structure. How easy would it be to modify this structure for any of the following?:


2. Trees, Nodes and Leaves

This type of structure, with its hierarchical nature, is also known as a TREE structure. A common example of this is the view provided by Windows Explorer which shows the hierarchy of folders and the files contained within those folders (although the structure is displayed from left-to-right rather than from top-to-bottom). A similar view is available in Uniface forms by using the TREE widget.

A tree contains objects known as NODES and LEAVES. These obey the following rules:

NODES

LEAVES

In Windows Explorer the NODES are equivalent to FOLDERS (previously known as DIRECTORIES) with the ROOT NODE representing a drive such as C: or D:, and the LEAVES are equivalent to FILES.

In figure 3 COMPANY, DEPARTMENT and SECTION are the nodes, with PERSON providing the leaves.


3. A modern flexible design

In designing my flexible structure I concentrated solely on the nodes. A leaf can be any other object within the database (eg: a person, a place, or a part), and linking a leaf to a node is as simple as storing the primary key of the node within the details of the leaf. There is no need to include the Tree Type or the Tree Level as these are obtained from the node details.

I wanted a table for NODES, and I needed to be able to relate a node to its parent node.

I needed to organise nodes into various LEVELS, each which its own customisable description.

I needed to have different sets of levels so that I could have more than one TYPE of structure.

This enabled me to produce the database design shown in figure 4:

Figure 4 - My database design

flexibletrees04.gif

Where TREE_NODE is related to itself this is handled by creating a subtype with a one-to-many relationship as shown in figure 5:

Figure 5 - Subtype for node-to-parent relationship

flexibletrees05.gif

These database tables have the following contents:

TREE TYPE
TREE_TYPE_ID C8 Primary Key
TREE_TYPE_DESC C40 Description

TREE LEVEL
TREE_TYPE_ID C8 Primary key, foreign key to TREE_TYPE
TREE_LEVEL_ID N2 Primary key
TREE_LEVEL_SEQ N2 Sort Sequence
TREE_LEVEL_DESC C40 Description

TREE NODE
NODE_ID N4 Primary key (technical key)
TREE_TYPE_ID C8 Foreign key to TREE_TYPE
TREE_LEVEL_ID N2 Foreign key to TREE_LEVEL
NODE_DESC C40 Description
NODE_ID_SNR N4 ID of parent node (foreign key to TREE_NODE_SNR)

Each TREE_TYPE is subject to the following rules:

Each TREE_LEVEL is subject to the following rules:

Each TREE_NODE is subject to the following rules:


4. Building your Tree structure

The following screen shots are part of the example application which is available for download on my Building Blocks page.

4a. Define a Tree Type

First go into the List Tree Type screen - on a new database this will be empty.

flexibletrees06.gif

From here select the navigation button to go into the Add Tree Type screen.

flexibletrees07.gif

In this example we are creating an entry with an ID of 'ORG' and description of 'Organisation'. Ignore the remaining fields as they are used to customise the list view of the tree widget. Press the OK button to update the database and return to the List Tree Type screen.

flexibletrees08.gif

This will now show the entry which has just been added.

4b. Define Levels within a Tree Type

From within the List Tree Type screen press the navigation button to go into the List Tree Levels screen.

flexibletrees09.gif

This will initially be empty, but will show the Tree Type selected in the previous screen, which in this case is 'Organisation'. From here press the navigation button to go into the Add Tree Level screen.

flexibletrees10.gif

Again this will show the Tree Type we are dealing with, and will set both Tree Level ID and Level Sequence to their next available values for this Tree Type, which in this case will be 1. Enter a description for level 1, which in this example is 'Company'. Ignore the Icon fields as they are used to customise the display in the tree widget. Press the STORE button to update the database without leaving this screen. The description field will clear and the ID and SEQ numbers will automatically be incremented to their next available numbers.

flexibletrees11.gif

Enter the description for level 2, which is this example is 'Department'. Press the STORE button to update the database without leaving this screen.

flexibletrees12.gif

Enter the description for level 3, which is this example is 'Section'. Press the OK button to update the database and return to the List Tree Levels screen.

flexibletrees13.gif

This will now show all the Levels which have been defined for this Tree Type.

4c. Adding Nodes to a Tree Level

From the List Tree Levels screen highlight the level to which you want to add nodes by clicking on it, then press the navigation button to go into the List Tree Nodes screen.

flexibletrees14.gif

This will show the current Type as 'Organisation' and Level as 'Company'. From here press the navigation button to go into the Add Tree Node screen.

flexibletrees15.gif

Again the current Type and Level are displayed. Enter the description for the node, in this example it will be 'AJM Solutions Plc'. The node ID is not shown as it is an automatically generated technical key. Press the OK button to update the database and return to the List Tree Nodes screen.

flexibletrees16.gif

This will show the details of the entry which you have just added. Press the CLOSE button to return to the List Tree Level screen.

flexibletrees17.gif

Highlight the 'Department' level by clicking on it, then press the navigation button to go into the List Tree Node screen.

flexibletrees18.gif

This will show the current Type as 'Organisation' and Level as 'Department'. From here press the navigation button to go into the Add Tree Node screen.

flexibletrees19.gif

Create an entry for 'Accounts' and press the STORE button. The entry will be added to the database and the screen will clear ready for new input.

flexibletrees20.gif

Create an entry for 'Sales' and press the STORE button.

flexibletrees21.gif

Create an entry for 'Support' and press the STORE button.

flexibletrees22.gif

Create an entry for 'Development' and press the OK button. This will update the database and return you to the List Tree Nodes screen.

flexibletrees23.gif

This will now show all the nodes that exist for the 'Department' level in the 'Organisation' structure. Press the CLOSE button to return to the List Tree Levels screen, select the occurrence for the 'Section' level, press the List Tree Nodes button followed by the Add Tree Nodes button to create various nodes at the 'Section' level in the 'Organisation' hierarchy. Then return to the List Tree Nodes screen to view the result.

flexibletrees24.gif

The node descriptions here are purely for illustrative purposes. In the real world you would probably use something completely different.

4d. Linking Nodes with their parents

None of the nodes created so far has been linked to a parent, so they are all considered to be orphan nodes. This does not matter for any node at level 1 as root nodes do not have parents, but all nodes at other levels must have their parentage defined before they will show up in the tree structure. To do this return to the List Tree Type screen and press the navigation button for View Tree (1).

flexibletrees25.gif

This will show the current structure of the selected Tree Type. This version has navigation buttons which will allow the structure to be amended. This will start by only showing the root nodes (those at level 1) for the selected Tree Type, which is shown here as 'Organisation'. If you press the '+' button to expand the tree to the next level down nothing will happen yet as this root node does not have any children. To create a relationships, and thereby a usable structure, it will be necessary to first select the parent node, then press the navigation button to bring up the Link Junior Node screen.

flexibletrees26.gif

This will show the description and level for the selected parent node. The only way to select a child node is to go via the Choose Orphan Node screen which is automatically activated upon initial entry.

flexibletrees27.gif

This will show those orphan nodes (nodes without parents) which exist for the selected Tree Type and Tree Level. Only these nodes can be linked as children to the current parent.

If the node you require has not been defined yet it will be possible to use the navigation button labeled Add Tree Node to create it without having to return to the List Tree Nodes screen. Highlight a node and press the SELECT button to return to the Link Junior Node screen.

flexibletrees28.gif

This will now show the selected orphan node. Press the STORE button to update the database with the relationship. The screen will then clear, so it will be necessary to press the flexibletrees29.gif button to reactivate the Choose Orphan Node screen. Select all the remaining nodes at this level, then return to the Display Tree Structure screen.

flexibletrees30.gif

This will now show all the child nodes that have just been related (linked) with the selected parent node. From this screen you can now select each of these nodes at level 2 and relate the relevant orphan nodes which exist at level 3.

flexibletrees31.gif

You will note here that the nodes at level 3 have been split across the nodes at level 2.

4e. Checking a Node's parentage

Sometimes it may be necessary to trace a node's ancestry all the way to the top of the tree. From the List Tree Type screen press the navigation button to go into the List Tree levels screen. Select a level (in this example level 3 'Section') then press the navigation button to bring up the List Tree Node screen. From here select any desired node then press the navigation button for the List Senior Nodes screen.

flexibletrees32.gif

This will show the selected node on the bottom line ('Blondes' in this example) with its associated level number and description. Immediately above that will be the details for its parent, and its parent and so on until a root node is reached. If a root node at level 1 is not shown it means that a link to a parent node has yet to be defined.


5. Adding another Tree Type

The previous example showed how to create a tree structure called 'Organisation' with its own set of levels and nodes. Using the same software I can create any number of other structure (tree) types. To do this start at the List Tree Types screen:

flexibletrees08.gif

This shows the existing entries for Tree Type. Press the navigation button to go into the Add Tree Type screen.

flexibletrees33.gif

In this example we are creating an entry with an ID of 'PROJ' and description of 'Project'. Ignore the remaining fields as they are used to customise the list view of the tree widget. Press the OK button to update the database and return to the List Tree Type screen.

flexibletrees34.gif

This now shows the entry that has just been created. Click on this entry to highlight it and then press the navigation button to go into the List Tree Levels screen.

flexibletrees35.gif

This will initially be empty, but will show the Tree Type selected in the previous screen, which in this case is 'Project'. From here press the navigation button to go into the Add Tree Level screen.

flexibletrees36.gif

Again this will show the Tree Type we are dealing with, and will set both Tree Level ID and Level Sequence to their next available values for this Tree Type, which in this case will be 1. Enter a description for level 1, which in this example is 'Project'. Ignore the Icon fields as they are used to customise the list view of the tree widget. Press the STORE button to update the database without leaving this screen. The description field will clear and the ID and SEQ numbers will automatically be incremented to their next available numbers.

flexibletrees37.gif

Enter the description for level 2, which is this example is 'Phase'. Press the STORE button to update the database without leaving this screen.

flexibletrees38.gif

Enter the description for level 3, which is this example is 'Module'. Press the OK button to update the database and return to the List Tree Levels screen.

flexibletrees39.gif

This will now show all the Levels which have been defined for this Tree Type. All you need do now is to create the required nodes for each of these new levels, then relate each node to its parent After this you could end up with a structure something like this:

flexibletrees40.gif

From this you can see that this design can support any number of structure (tree) types, each with its own set of levels and nodes. However, the flexibility of this design does not end there - you can also add new levels into existing structures, and remove redundant levels.


6. Adding a new Level into an existing Structure

The power of this design lies in its ability to amend the number of levels in an existing structure without having to erase and rebuild it. In the following example the original company at level 1 merged with two other companies, with the requirement that a new level called 'Group' be added at the top to create a 4-level structure as shown in figure 6:

Figure 6 - The new 4-level structure

flexibletrees41.gif

Here is how the existing structure can be modified. Go into the List Tree Type screen, highlight 'Organisation' by clicking on it and press the navigation button for the List Tree Levels screen.

flexibletrees13.gif

This will show the existing 3 levels. Press the navigation button to go into the Add Tree level screen.

flexibletrees42.gif

This will automatically fill in the next available values for Level ID and Level Sequence. All you have to do is fill in the description, which in this example is 'Group'. Press the OK button to update the database and return to the List Tree Levels screen.

flexibletrees43.gif

This shows the new entry at level 4 when we actually want it at level 1. To do this press the navigation button to go into the Modify Level Sequence screen.

flexibletrees44.gif

This shows the existing ID's which cannot be changed (as they are primary keys), but we are able to change the sequence in which they are to be placed in the structure.

flexibletrees45.gif

What we have done here is to put 'Group' at sequence 1 and move all the others down by 1. Note that the sequence numbers must start at 1 and continue in an unbroken sequence. Press the OK button to update the database and return to the List Tree Levels screen.

flexibletrees46.gif

As you can see these levels have now been resequenced without changing the primary keys. As all nodes are tied to a Level by its primary key (Level ID) this means that all nodes will automatically stay with that level description regardless of any changes to its sequence number. All we need to do now is to create the required node(s) for the new level, then perform any linking to the lower level. Leave 'Group' highlighted and press the navigation button to go into the List Tree Nodes screen.

flexibletrees47.gif

This will show the current Type as 'Organisation' and Level as 'Group'. From here press the navigation button to go into the Add Tree Node screen.

flexibletrees48.gif

Again the current Type and Level are displayed. Enter the description for the node, in this example it will be 'The AJM Group of Companies'. The node ID is not shown as it is an automatically generated technical key. Press the OK button to update the database and return to the List Tree Nodes screen.

flexibletrees49.gif

This will show the details of the entry which you have just added. Press the CLOSE button to return to the List Tree Level screen.

flexibletrees46.gif

We must now add the new companies that are in the group. Highlight 'Company' by clicking on it, then press the navigation button for the List Tree Nodes screen.

flexibletrees16.gif

Press the navigation button for the Add Tree Node screen and create entries such as 'AJM Problems Plc' and 'AJM Excuses Plc'. Return to the List Tree Nodes screen to view the results.

flexibletrees50.gif

You must now return to the List Tree Type screen and go into the View Tree (1) screen in order to link the new node at level 1 (Group) with the nodes at level 2 (Company) so that they will be visible in the structure. Afterwards you should see something like this:

flexibletrees51.gif

Note that all the existing nodes which were linked to 'AJM Solutions Plc' are still there. They have remained attached to that node although the levels have changed. The same applies to any leaves - they stay attached to the same node regardless of its position within the structure.


7. Removing a Level from an existing Structure

This activity is also possible with this design although the steps are a little more involved. This is what you do:

  1. Remove all relationships between the nodes on the target level and the levels immediately above and below it.
  2. Unlink all leaves from the nodes on the target level.
  3. Remove all nodes on the target level.
  4. Delete the target level.
  5. Modify the sequence numbers for the remaining levels.
  6. Create new relationships between the levels that were immediately above and below the level that has just been removed.
  7. Relink any leaves from step (b) with their new nodes.

All these steps are required if you remove a level from the middle of the structure. If you remove just the top or bottom level then some of these steps will not be necessary.


8. Conclusion

Although this design requires no more than three database tables you can see that it can cater for any number of structure types with any number of levels and any number of nodes. The ability to expand or contract existing structures without changing the database and without changing any software is another powerful benefit that is simply not possible with traditional, less flexible designs.

The software used to create the screen shots in this article is available for download from my Building Blocks page.

Associated articles:
Using Nodes in a Tree Structure to provide Record-Level Security.
Using Nodes in a Tree Structure to generate Nominal Codes.


Tony Marston
31st October, 2001

mailto:tony@marston-home.demon.co.uk
mailto:TonyMarston@hotmail.com
http://www.tonymarston.net

Back to TOP.

counter