Tree Structure

1 Usages of Tree Structure

Tree structure is one of basic data structure which presents one type of nonlinear logic.

Tree structure can describe relationships in hierarchy and membership accurately.

2 Features of Tree Structure

2.1 Concepts

Information can be organized as a tree:

1. "Node" stores a piece of information.
2. "Children Nodes": In lower level and belong to the node. Also called "Branches".
3. One node can have multiple children.
4. "Parent Node": In higher level and owns the node.
5. One node can have only one "Parent".
6. "Descendant Nodes": All lower nodes extended recursively from children.
7. "Ancestral Nodes": All higher nodes extended recursively from parent.
8. "Root Node": In top level and be ancestry of all other nodes.
9. "Leaf Nodes": Have not children.
10. "Hierarchy Number": The chain of sequence numbers from root to the node.
11. "Node Name": String to describe the node.
12. "Chain Name": The chain of node names from root to the node.
13. "Steady Node Name": During the tree is being watched or handled, node name is not changed.
14. "Static Tree": During the tree is being watched or handled, tree structure is not changed, that is no node is deleted, added, or moved.
15. "Dynamic Tree": During the tree is being watched or handled, tree structure is changed, that is some nodes are deleted, added, or moved.

2.2 Identify and Locate Nodes

To locate specific node in the tree correctly:

• An unique identify should be assigned to each node. That is, identifies of all nodes are different.
• The identify of node should be steady. That is, it should not change during the tree is being watched or handled.

2.3 Ordered Tree

"Ordered Tree" has following features:

• The order of each node's children are steady. That is, the sequence numbers of children are always same for each query when children are not changed.
• Hierarchy number can identify each node uniquely.
• Hierarchy number of same node may change in dynamic tree.

So hierarchy number can be used to locate a node only for static ordered tree.

2.4 Tree with Unique Chain Names

"Tree with unique Chain Names" has following features:

• Names of each node's children are not duplicated.
• Names of different nodes' children can be duplicated.
• Chain names can identify each node uniquely.
• When nodes' names are steady, chain names do not change in dynamic tree.

So chain names can be used to locate nodes for dynamic or static tree when it is "unique chain names".

3 Implement Tree Structure

In MyBox, attributes of tree node include: ID, Title(Node Name), Value, Modify_Time, ID of parent node.

3.1 ID of Node

ID of node is generated and increased automactically, and used to identify and locate each node uniquely. It is absolutely steady attribute:

• Generated by database automactically and never updated once the value is set.
• IDs of all nodes are different.
• Does not change when tree structure is changed.
• Does not change when other attributes of node are changed.

IDs of nodes have following disadvantages:

• Unfit for person to remember and recognize nodes, and unfit for operations of interfaces.
• Tightly coupled with application environment, and may cause conflicts and incompatibilities when import data.

3.2 Title of Node

Title of node is string to describe node:

• Should not be null.
• Should not include " > "(Blank before and after greater-than sign), which is separator of chain name and reserved internally.
• Titles of children can be duplicated.
• Does not change when tree structure is changed.
• Does not change when other attributes of node are changed.

Because titles of children can be duplicated, if treat node title as node name, then chain name may not be unique and can not locate node correctly with it.

Titles of nodes have following advantages:

• Fit for person to remember and recognize nodes, and fit for operations of interfaces.
• Do not coupled with application environment, and fit to import data.

3.3 Value of Node

Value of node is stored as large text of length 2G.

In MyBox, objects handled by following functions are stored and managed in tree:

3.4 Tags of Node

• Tags are extra attributes assigned to node, and customized by user.
• Purpose of tags is to categorize, query, and locate nodes with keywords.
• One node can have multiple tags.
• One tag can belong to multiple nodes.

3.5 Reserved Strings

• Node's title should not include " > "(Blank before and after greater-than sign), which is separator of chain name.
• Node's tag value should not include ";;;", which is separator between tags.
• All attributes of node should not include following strings:
  • "MyBoxTreeRoot;;;": This is identify of root node.
  • "##MyBox#": This is separator among nodes.
  • "_:;MyBoxNodeValue;:_": This is separator of node's internal values.
  • "MyBoxTreeNodeMore:": This is prefix of node's internal values.

4 Manage Tree Structure

4.1 Tree View

Select one node, and display its "Tree View" with this node as root:

• Tree information is shown in html page.
• Click node name to unfold/fold its childrent.
• Options to display hierarchy number, tags, and node values.

4.2 Examples

MyBox provides examples for functions in tree.
Click menu item "Examples" to import example data of the function.

Examples' tree view of of each function tree can be viewed in MyBox documents list.

4.3 Export

Select one node, and export its tree with this node as root:

• Format can be chosen: text, single html, html frameset, xml, or json.
• Options to export node's modified time, and its tags.
• Style of exported html can be set.

4.4 Import

Tree information can be imported in batch:

• Select multiple files which hold tree information as source.
• File format is text encoded with special delimiters. Exported text can be referred.
• Rulers of text format are displayed in interface, and example is provided.

Notice:

• Can not locate node by ID when import nodes, because ID is an attribute which couples application environment tightly:
  • After node is exported, it can not keep pace with the application environment.
  • When node is imported, its ID may be missed or conflicted in the imported environment.
  • The hierarchy of imported nodes can not be defined by their IDs because the IDs may be incompatible with the imported environment.
• Although MyBox permits duplicated names of children nodes, it locates nodes by chain name when import nodes:
  • Chain name is a stable attribute, which can identify and locate node uniquely in environment of "No duplicated names of children".
  • To existed chain name, options: "Change attributes", "Not change attributes", and "Create child of duplicated name".
  • Algorithm locates parent node in nearest way, that always queries recently written node at first. So the exported tree can be restored when imported.

4.5 Query and Select Nodes

To select nodes, following ways can be taken:

• Click node in the tree.
• To node in the tree, click menu item "Load Children" or "Load Descendant", and select one or multiple nodes in the nodes list.
• Select multiple tags, and select one or multiple nodes in result list of the query.
• Select multiple time values, and select one or multiple nodes in result list of the query.
• Input multiple keywords, query against node title or node value, and select one or multiple nodes in result list of the query.

4.6 Add/Delete/Modify Nodes

Select one or multiple nodes, and:

• Add child node.
• Delete the nodes and their descendant.
• Rename node.
• Copy nodes:
  • Choices: Only copy node, Copy node's descendant, or Copy node and its descendant
  • Select the target node to copy into.
  • Target node should not be source node nor its descendant.
• Move nodes:
  • Select the target node to move into.
  • Target node should not be source node nor its descendant.
• Edit Node.

4.7 View Nodes

Select one node:

• View node's information in popped window.
• Copy node's title or value into system clipboard.
• Fold node, or node and its descendant.
• Unfold node, or node and its descendant.
• Load children or decendant.

4.8 Menu

• Click buttons in interface to view menus.
• Right click the tree to pop the menu.
• Actions can be chosen for left click, right click, or double click against the tree.