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.