I need to represent a directed rooted tree in memory.
What would be a good data structure and algorithms for performing main actions, given the particulars listed below?
-
Size: ~40,000 nodes. But ideally should scale well to 10x the size or more.
-
Arity: Very variable. Some nodes have 2-3 children. Some have 10. Some (rarer) have 1000.
-
Data is NOT static – throughout the day, ~1-3% of the nodes/edges will be added/removed/moved to different parts of the tree (for a good real life example, let’s pretend it’s a filesystem tree where people are very active, and has symlinks).
For the purposes of notation:
- D(V) – depth of the vertex (distance from the root).
- A(V) – arity of the vertex (how many children it has).
- V – Size of the tree (how many total vertices)
The following actions are needed (with desired speed of action indicated).
-
Ability to add a single vertex or a new subtree
O(N) where N is the amount of vertices being ADDED (not already in the tree) and O(D(V)) where V is the vertex where new nodes are attached.
-
Ability to delete a subtree
O(N) where N is the amount of vertices being deleted and O(D(V)) where V is the vertex where new nodes are deleted from.
-
Ability to move a subtree to another parent elsewhere in the tree
O(N) where N is the amount of vertices being moved and O(D(V)) where V is the vertex where new nodes are moved between.
Note that due to retrieval needs described below, I do NOT anticipate that you can do this in O(1) independent of how many nodes are being moved, like in a regular basic tree data structure with child node pointers.
-
Ability to find a node by its name (needed for all the subsequent steps)
Ideally, O(1). Most definitely much less than O(log V).
-
Ability to know the full path up from the vertex to the root
O(1) ideally. But definitely less than O(D(V)). This is very important; and is the reason why standard linked implementations of the tree won’t work, even with 2-way links.
20
The long answer is, “The Art of Computer Programming, Vol. 4A: Combinatorial Algorithms Part 1.”
The shorter answer is, there are a whole bunch of different ways to do it. If you’re not sure what representation to use, you’re getting way ahead of yourself. The first question is, is there a way of implementing it in the language that you’re using that you’re comfortable with? Once you get that part nailed down and you have a working implementation, then you can worry about if it is optimized.
You don’t want to be worrying about O() stuff at all unless you already learned two ways to do it, and you’re choosing between them. If you want to learn how to analyze the different representations in advance and choose the perfect one, you really do have to read the book mentioned above. Each question you ask is a few dozen pages of dense mathematical explanation that builds on previous information in the book. You have to make it nearly 500 pages in, and then you’ll know how to “generate all the trees,” and you can determine which set of trees you want to optimize for.
1
As you said it is similar to a file system, why can’t you actually use the Windows file system. Make each node an extentionless file (to save memory) and put them in folders. Once you index the locations, Windows will use the best possible algorithm to find the required subtrees (folders).
Using a hash table with double hashing with 1st function based on any 3-5 random digits of the name and 2nd based on all the rest of the characters.
3