Suitable tree data structure

Question

I have been reading about tree data structure to model a problem. I need to construct memory representation of a data which is very similar to folder/file representation in file system (I don't imply the actual file stored in disk but the explorer like structure). The tree may be maximum 10 deep The intermediate nodes may only have moderate number of children (say 10 ), but there could be thousands of leaf nodes.[that is like thousands of files in the folder and file is the leaf node]

Some thoughts

• A Binary tree cannot work as one node can at the most have only 2 children. (say we can have 3 subfolders)
• A very generic tree implementation may be inefficient as my data can be ordered. Like the left sibling is smaller/lesser than the right ones. I hope this allow to have efficient traversal.
• A B-tree sounds very close, but does it insist balancing requirements. In my case, the depth won't be more than 10, but not necessarily all the branch that deep.(say c:/windows , C:/MyDoc../A/B/C)

Please help with your experience. Should I custom make a tree or any suitable data structure available (don't mean specific to a programming language)

Answer 1

You have two different kinds of nodes: files and folders.

A folder node contains a set (or map) of children, where the children may themselves be files or folders.

Alternatively, you might prefer for a folder node to contain a set of files and a set of folders.

For the sets, just use your favorite representation of ordered sets (probably the one that comes with whatever language you are using). Depending the exact details of your situation, you might prefer to use a map instead.

Answer 2

Use two separate data structures:

1. A binary search tree for search
2. And a general binary tree for representation

and link these two together.

Note:

• In general tree put folders first in order and put all files in a BST as one last node.

Or Use:

Node:
    Node* Left_Most_Child_Folder;
    Node* Right_Sibling_Folder;
    BST_Node* Files_Root;

Answer 3

In a typical file system, the "directory-tree" and the search tree are not the same thing, and are usually maintained separately. The "directory-tree", which tells you what files/sub-folders a folder has, or the path to a particular file, simply reflects how the user organizes the files and is only useful to the user. The search tree on the other hand maintains the global index of all files, so as to facilitate a fast search.

For example, you can implement a Linux like file system, where a folder is a file that records the pointers of the other files/folders it contains. At the same time you maintain a B+ tree, which has every file pointer as a leaf. The balance condition of the B+ tree has nothing to do with how the user organizes the folders.

Answer 4

One way to do this would be to use a binary tree of binary trees. For example:

Node
  Node* Children;
  Node* Left;
  Note* Right;

And the root of your tree is a Node*.

This makes for easy traversal and quick insertion and removal of a node. Provided, of course, you know the path to the level where you want to insert the node, or the path to the node that you want to delete. But since you indicate that you want a model similar to Explorer, I assume that finding a particular level doesn't pose a problem.

Searching for a node at a particular level is as simple as searching a binary tree.

Without a little bit more information about what you're trying to model, that's the best I can do.