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.


closed as unclear what you're asking by D.W., FrankW, David Richerby, Juho, Wandering Logic Apr 30 '14 at 17:45

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ Thanks, this helped a lot! More questions: 1. Why do you need an unbounded degree of internal nodes, or for that matter the data to be represented as a tree? It seems like that is an internal implementation decision that shouldn't matter, if you are only using the data structure through its defined API (if you are only using it via the operations you mentioned). 2. Is there any guarantee that any given key will be present in at most one tree (it'll never be present in multiple trees)? That's simplify the problem. 3. What do you want to happen after merge if both trees contain a common key. $\endgroup$ – D.W. Apr 30 '14 at 17:13
  • $\begingroup$ 1) The tree represents a real world hierarchy that is in flux over time. The real world hierarchy has an unpredictable structure, the tree cannot know ahead of time how many children a given node will have. An example is a file system where the number of child directories or files arent known ahead of time. 2) No - the keys can occur in both trees and the definition of the merge is recursive. I would like to provide a blending functor that gets applied to the data elements from tree_1 and tree_2 to determine the data element that should be inserted into the merged tree for the repeating key. $\endgroup$ – user17191 Apr 30 '14 at 17:25
  • 1
    $\begingroup$ You need to specify where the tree structure comes from. Typically, the abstract operations you define are called "dictionary" but you require more. Also, you need to specify what happens with duplicate keys during merge. $\endgroup$ – Raphael Apr 30 '14 at 17:30
  • $\begingroup$ Thanks. I recommend you edit the question to include the information you mentioned here, and the information Raphael mentions, into the question. $\endgroup$ – D.W. Apr 30 '14 at 17:42
  • $\begingroup$ I'm particularly unable to understand the children operation, and your objection to Binary, AVL, red-black and 2-3 because they have "fixed degree of internal nodes." If you care about parent-child relationships then shouldn't insert take a parent parameter? $\endgroup$ – Wandering Logic Apr 30 '14 at 17:48

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).

  • $\begingroup$ This does neither preserve any structure the tree needs to have (question is unclear in this regard) nor does it work if trees do not contain disjoint key sets. $\endgroup$ – Raphael Apr 30 '14 at 17:31
  • $\begingroup$ @Raphael, thanks. My original answer answered the question as originally stated, but the question changed after I posted my answer. I've just edited my answer to show how to address all of the requirements in the revised question, assuming trees have disjoint key sets. If the trees don't have disjoint key sets, then this doesn't work (though in that case the author will need to specify what is supposed to happen during a merge operation of two trees that have overlapping key sets). $\endgroup$ – D.W. Apr 30 '14 at 17:40
  • $\begingroup$ Well, I don't get what the OP wants at all; apparently, the parent-child relationship is to hold some semantics, too? Apparently your answer helps them, though. $\endgroup$ – Raphael Apr 30 '14 at 17:42
  • 1
    $\begingroup$ @Raphael, indeed. Same here. I missed the comment at the top. Given the direction this question is heading, I suspect my answer isn't going to meet the requirements, but I'll wait to see if the question gets edited a bit more to specify more clearly what's needed. $\endgroup$ – D.W. Apr 30 '14 at 17:44

Refer to literature of AVL tree, which is a balanced binary tree. Using AVL tree all of the operations you mentioned can be performed in O(log n) time, where n is the sum of the number of nodes in tree_1 and tree_2 for (a), and number of nodes of the tree for (b) and (c), and as far as I know this time bound is the tightest one among the tree data-structures.


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