I need trees that have the following properties:
Each node in the tree has two values associated with it - a key and an associated opaque data element.
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.
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)$.
merge(tree_1, tree_2)- Destructively consumes
tree_2to 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.
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.