7

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.

Improve this question
20
  • Other than the name lookup (which can be satisfied by putting all the nodes in a hashtable) this looks like a run-of-the-mill tree structure.
    – Robert Harvey
    Commented Oct 20, 2014 at 15:13
  • @RobertHarvey - how can you do a less than O(D) path-up for a node in a regular tree structure? Wouldn't you have to cache the paths in some way? I agree that adding a hashtable would be one way to solve the name lookup (that's how I'm doing it now).
    – DVK
    Commented Oct 20, 2014 at 15:19
  • How deep is the tree likely to get? Trees 20 deep can handle billions of nodes, if they're balanced, and a 20-depth traversal takes minimal time, unless, perhaps, you're doing string concatenation along the way.
    – Robert Harvey
    Commented Oct 20, 2014 at 15:21
  • 3
    You could help the process by answering some of my other questions I asked here in the comments.
    – Robert Harvey
    Commented Oct 20, 2014 at 16:12
  • 1
    I really doubt there's a magic wand here. If you need that fine of a control over the strings, you might look at something like a bloom filter, but I think the problem is more mundane than that. Normally concatenated paths like that are required for display purposes, so I don't see what the need for speed is, even on a 50 deep tree.
    – Robert Harvey
    Commented Oct 20, 2014 at 16:21

2 Answers 2

Reset to default
-1

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.

Improve this answer
1
  • 1
    Odd to see a delete request with no comment. Seems a bit silly. This is really the answer! You have to do an exhaustive survey of all the different binary algorithms if you want to optimize for some set of cases. This is discussed mathematically in the book that does that survey, mentioned above.
    – RubyPanther
    Commented Jan 4, 2019 at 5:28
-3

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.

Improve this answer
3
  • 1
    Using Windows filesystem for a unix server would be a cute trick
    – DVK
    Commented Oct 27, 2014 at 14:56
  • I didn't know it was a unix server.
    – ghosts_in_the_code
    Commented Oct 28, 2014 at 14:46
  • 1
    that's why when the question asks for data structures and algorithms, it asks for just that, and not specific implementation :)
    – DVK
    Commented Oct 28, 2014 at 15:04

Not the answer you're looking for? Browse other questions tagged or ask your own question.