I have used a purely functional binary tree structure in which there is a single node that is "marked". It allows for $O(1)$ access and modification of the marked node's value, as well as $O(1)$ traversal upwards and downwards.
It is represented as a pair $(M, P)$, where $M$ is the marked sub-tree and $P$ is a list of parent segments. For example, in the following tree
, the blue subtree is "marked". Groups of nodes joined by solid lines are parent segments, and parent segments are separated by dotted lines.
The marked subtree could be represented as follows (where
Terminal represents the absence of such a node in the diagram):
(Tree 17 (Tree 19 Terminal Terminal) (Tree 23 Terminal Terminal))
The parents could be represented as:
[ (Right 13 (Tree 29 Terminal Terminal)) , (Right 11 (Tree 31 Terminal (Tree 37 (Tree 41 Terminal Terminal) Terminal))) , (Left 2 (Tree 3 (Tree 5 (Tree 7 Terminal Terminal) Terminal) Terminal)) ]
- The marked node's value can be accessed and modified in $O(1)$ because it is at the top of the marked subtree.
- Traversal downwards can be done by choosing one subtree and turning the previous node into a Left- or Right-valued tree that stores the other child, which is added to the list of parents.
- Traversal upwards can be done by converting the most direct parent from a Left- or Right-valued tree to a full tree by filling in the other side, and then using the result as the new marked subtree.
I used the term
AccessTree for this representation of the tree, but I decided the name was unclear.
Has this representation of a tree ever been given a name? If so, what is it?