In an n-ary tree…
- Given a reference to some child node
- And a reference to a distant parent of the referenced child node
- Is there a method that a parent node can use to figure out which of its children is closest to the referenced child node and has a big-oh that’s less than O(number of edges between parent and child)
Picture to illustrate my question:
A
|
|
B
/
/
C D <-- distant parent
/|
/ |
E F G <-- which child?
/| |
/ | |
H I J K L
/ /| /|
/ / | / |
M N O P Q R
^ |
| |
That child node S
(original image)
Things I’ve tried:
-
Iterating up the tree (O(n)), from “that child node” until the parent is found, and returning the previously visited node. This is when I noticed that my program spent too much time iterating up the tree, and could use some kind of improvement.
-
Have each node save a reference to every single parent it had in an array, and the index used is the number of edges between the node in the array, and the root node.
Example: “that child node” will have an array of size 5, and its immediate parent would be at index 4, and the root, index 0.
Advantage: this makes finding the node to return very quick (O(1)) because, the level (number of edges between the node, and the root node) + 1 of the parent node, will give me the index in the array in “that child node” of the node that I want to return.
Disadvantage: adding nodes to the tree becomes very expensive in memory, and computational time especially if the node is very far from the root node. expensive in memory, because it will have a huge array, and computational time because the array needs to be populated, weather it be populated by tree traversal, or copying the array from it’s parent, it can take a while…
-
Like above, except, instead of saving references to every node, it saves log2(level) node references to nodes, in a log2() like way
Example: a node at level 1000000 would have 20 references to parent nodes. these references would be to a parent at each of the following levels: 500000, 750000, 875000, 937500, 968750 … 999999.
Advantage: finds the node to return in O(log2(n)) to O(n), not as fast as solution above, but fast enough. much more memory efficient than above solution, but still pretty bad.
Disadvantage: still quite expensive to add new nodes to the tree in computational time, but not that bad.
I can think of variations of the above 3rd method to make things slightly more memory efficient, and time efficient, but I’m wondering if there is a method that takes O(1) time to find the solution to this problem that I am not seeing … something like the binary search tree property, but for an n-ary tree.
The binary search tree property is desirable, because given a child node, the parent can make a step towards it, regardless of the number of edges between the given child node, and the parent.
I don’t mind putting an extra index or ID or whatever data into the child node to make the method possible.
2
I can think of a variety of possible solutions, but they all involve a high memory overhead.
Let k be the number of candidate parent nodes, ℓ the level of the distant child node (i.e. the distance from the root), c the child node, and p the candidate parent node(s).
O(k) – Store directions to each node
Each node has an ordered array of IDs (e.g. pointers) of all ancestors. This array can be understood as the directions from the root to that node. To test whether a node p is parent of another node n, we simply compare the ID at the appropriate level:
fun is_parent(c: Node, p: Node): Bool =
c.directions[p.directions.length - 1] == p.id
Advantages: pretty compact storage.
Disadvantages: Inserting nodes is pretty expensive because their directions have to be updated.
O(k) to O(k log ℓ) – Store sets of all ancestors
This is a variant of the above solution, but using just some kind of set (or a list ordered by ID rather than by level). Depending on how that set is implemented, algorithmic complexity of the lookup differs.
fun is_parent(c: Node, p: Node): Bool =
c.ancestors.contains(p.id)
This shares the same advantages and disadvantages as the previous solution.
O(k log ℓc), worst case O(k ℓ) – Skip Lists
This is a variant of the first solution, but with much less memory overhead.
A skip list is a linked list that contains not only a pointer to the next element, but also to more distant elements. This allows O(log n) search in an ordered skip list, similar to a binary search in an array. Skip lists can also be used for efficient indexing in linked lists, which is what we’ll do here. Our “index” is actually the relative level of a node.
In our case, each child contains at least one link to the immediate parents, but possibly also to other ancestors. A link is a pair of a pointer to the target node and of an integer that tells us how many levels this link advances.
data Link(distance: Int, target: Node)
fun is_parent(c: Node, p: Node): Bool = {
val skip_length = p.level - c.level
if (skip_length <= 0)
return c.id == p.id
// Node.links stores links sorted in descending distance
val link = c.links.first(link => link.distance <= skip_length)
return is_parent(link.target, p)
}
Advantages: uses less memory than the other solutions.
Disadvantage: has O(n) worst case (when the skip list degrades to a simple linked list). This can be avoided by re-threading the skip list upon insertion.