[Solved]: Tree data structure for fast merges

Problem Detail: 

I need trees that have the following properties:

1. Each node in the tree has two values associated with it - a key and an associated opaque data element.

2. An internal node in the tree has unbounded number of children. The tree reflects a real world hierarchy that is in flux over time - hence the maximum number of children of a given node are not known ahead of time.

3. There is an ordering defined on sibling nodes that is a function of the keys stored in the nodes.

Allow the following operations to be $O(\lg n)$.

Update operations

• merge(tree_1, tree_2) - Destructively consumes tree_1 and tree_2 to create a new tree which contains keys from both input trees. I realize now that this operation is underdefined, I will put more thought into the semantics of the merge.

• insert(tree, parent_key, child_key, value) - inserts the given key-value pair into the given subtree rooted at the node pointed to by the parent key.

• delete(tree, key) - Delete subtree rooted at node with given key.

• update(tree, key, value) - Destructively updates the existing data associated with the given key-value pair.

Query operations

• find(tree, key) - returns the value associated with the given key in the given tree.

• get_tree(tree, key) - Return a subtree that is rooted at node with given key. The returned tree must a reference and share identity with corresponding nodes in the incoming tree. Modifying any nodes via the returned tree will hence result in changes to the initial tree.

• children(tree, key) - Returns sequence of (key, data) of child nodes of node corresponding to key.

Things I looked at before I asked this question - Binary trees, AVL trees, Red Black trees, 2-3 trees and they were not suitable because of fixed degree of internal nodes.

Asked By : user17191

Answered By : D.W.

If you have a guarantee that any given key will be present in at most one tree, you can implement these operations using the Union-Find data structure for disjoint sets. Basically, you use the disjoint sets data structure to keep track of which keys are present in the same "tree". Then, you have a separate hash table on the side to map keys to values. With these two data structures, each of your operations can be implemented in $O(\alpha(n))$ time, where $\alpha(n)$ is the inverse Ackerman function. In fact, you can treat each operation as running in essentially constant time.

Some examples of how to implement your algorithms:

• merge(tree_1, tree_2): Invoke Union(tree_1, tree_2).

• insert(tree, key, value): Check that key is not already present, by looking it up in the hashtable. If it is already present, bail out (abort). Otherwise, create a new singleton disjoint set containing just the value key. Merge that new set with tree_1, using a Union() operation. Insert (key, value) into the hashtable.

• update(tree, key, value): Check that key is in this tree, by calling Find(key); if it's not, bail. Then, update the mapping for key in the hashtable.

• find(tree, key): Check that key is in this tree, by calling Find(key); if it's not, bail. Then, get the mapping for key from the hashtable.

• get_tree(tree, key): Check that key is in this tree, by calling Find(key); if it's not, bail. Then, return key.

• children(tree, key): Return the single-entry list [(key, value)] (pretend key is a leaf).

With this implementation, the merge operation has the side effect of destroying the old trees (so you are not allowed to retain handles to the old trees). If you wanted a persistent data structure, you can look at persistent disjoint-set data structures.

However, this answer has two serious limitations: first, it does not allow you to specify or control the parent-child relationship; second, it requires that the key sets of the trees be disjoint (no key appear in more than one tree). It sounds like these limitations make this answer unusable in your context, but I'm not certain yet (perhaps a future revision of the question will make this clearer).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/24235