3
$\begingroup$

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

 

Example of such a 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?

$\endgroup$
3
$\begingroup$

This representation is known as a "zipper" and is described by Gérard Huet in his paper "The Zipper":

The basic idea is simple: the tree is turned inside-out like a returned glove, pointers from the root to the current position being reversed in a path structure. The current location holds both the downward current subtree and the upward path. All navigation and modification primitives operate on the location structure. Going up and down in the structure is analogous to closing and opening a zipper in a piece of clothing, whence the name.

$\endgroup$
  • $\begingroup$ I didn't actually know this when I posted the question; I found this by accident. $\endgroup$ – Noncontextual Spelling Jul 15 '17 at 21:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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