##Tree Zippers##
-Now how could we translate a zipper-like structure over to trees? What we're aiming for is a way to keep track of where we are in a tree, in the same way that the "broken" lists let us keep track of where we are in the base list. For simplicity, we'll only implement this for binary trees---trees where internal nodes always have exactly two subtrees. But to get the guiding idea, it's helpful first to think about trees which permit nodes to have many subtrees. Suppose we had the following tree:
+Now how could we translate a zipper-like structure over to trees? What we're aiming for is a way to keep track of where we are in a tree, in the same way that the "broken" lists let us keep track of where we are in the base list. In a particular application, you may only need to implement this for binary trees---trees where internal nodes always have exactly two subtrees. But to get the guiding idea, it's helpful first to think about trees that permit nodes to have many subtrees. Suppose we have the following tree:
1000
/ | \
20 50 80 91 92 93 94 95 96
1 2 3 4 5 6 7 8 9
-and we want to represent that we're at the node labeled `50`. We might use the following metalanguage notation to specify this:
+and we want to represent that we're at the node marked `50`. We might use the following metalanguage notation to specify this:
{parent = ...; siblings = [node 20; *; node 80]}, * filled by node 50
-This is modeled on the notation suggested above for list zippers. Here `node 20` refers not to a `int` label attached to that node, but rather to the whole subtree rooted at that node:
+This is modeled on the notation suggested above for list zippers. Here `node 20` refers not to a `int` label associated with that node, but rather to the whole subtree rooted at that node:
20
/ | \
siblings = [node 20; *; node 80]
}, * filled by node 50
-We're understanding the `20` here in `node 20` to just be a metalanguage tag to help us theorists keep track of which node we're referring to. We're supposing the tree structure itself doesn't associate any informative labelling information with those nodes. It only associates informative labels with the tree leafs. (We haven't represented any such labels in our diagreams.)
+We're understanding the `20` here in `node 20` to just be a metalanguage marker to help us theorists keep track of which node we're referring to. We're supposing the tree structure itself doesn't associate any informative labelling information with those nodes. It only associates informative labels with the tree leafs. (We haven't represented any such labels in our diagrams.)
We still do need to keep track of what fills the outermost targetted position---`* filled by node 50`---because that contain a subtree of arbitrary complexity, that is not determined by the rest of this data structure.
{parent = ...; siblings = [*; node 50; node 80]}, * filled by node 20
-and similarly for moving right. If the sibling list is implemented as a list zipper, you should already know how to do that. If one were designing a tree zipper for a more restricted kind of tree, however, such as a binary tree, one would probably not represented siblings with a list zipper, but with something more special-purpose and economical.
+and similarly for moving right. If the sibling list is implemented as a list zipper, you should already know how to do that. If one were designing a tree zipper for a more restricted kind of tree, however, such as a binary tree, one would probably not represent siblings with a list zipper, but with something more special-purpose and economical.
Moving downward in the tree would be a matter of constructing a tree targetted on some child of `node 20`, with the first part of the targetted tree above as its parent:
node 20
/ | \
/ | \
- lead 1 leaf 2 leaf 3
+ leaf 1 leaf 2 leaf 3
-We'll call this new untargetted tree `node 20`. The result of moving upward from our tree targetted on `leaf 1` would be the outermost `parent` element of that targetted tree, with `node 20` being the subtree that occupies that parent's `*` position:
+We'll call this new untargetted tree `node 20`. The result of moving upward from our previous targetter tree, targetted on `leaf 1`, would be the outermost `parent` element of that targetted tree, with `node 20` being the subtree that fills that parent's target position `*`:
{
parent = ...;
* Huet, Gerard. ["Functional Pearl: The Zipper"](http://www.st.cs.uni-sb.de/edu/seminare/2005/advanced-fp/docs/huet-zipper.pdf) Journal of Functional Programming 7 (5): 549-554, September 1997.
* As always, [Oleg](http://okmij.org/ftp/continuations/Continuations.html#zipper) takes this a few steps deeper.
-[[Same-fringe using a tree zipper]]
+##Same-fringe using a tree zipper##
Supposing you did work out an implementation of the tree zipper, then one way to determine whether two trees have the same fringe would be: go downwards (and leftwards) in each tree as far as possible. Compare the targetted leaves. If they're different, stop because the trees have different fringes. If they're the same, then for each tree, move rightward if possible; if it's not (because you're at the rightmost position in a sibling list), more upwards then try again to move rightwards. Repeat until you are able to move rightwards. Once you do move rightwards, go downwards (and leftwards) as far as possible. Then you'll be targetted on the next leaf in the tree's fringe. The operations it takes to get to "the next leaf" may be different for the two trees. For example, in these trees:
you won't move upwards at the same steps. Keep comparing "the next leafs" until they are different, or you exhaust the leafs of only one of the trees (then again the trees have different fringes), or you exhaust the leafs of both trees at the same time, without having found leafs with different labels. In this last case, the trees have the same fringe.
+If your trees are very big---say, millions of leaves---you can imagine how this would be quicker and more memory-efficient than traversing each tree to construct a list of its fringe, and then comparing the two lists so built to see if they're equal. For one thing, the zipper method can abort early if the fringes diverge early, without needing to traverse or built a list containing the rest of each tree's fringe.
+
+