From 671e314f91abff10acfa31eab2211bb7eeb17881 Mon Sep 17 00:00:00 2001 From: Jim Pryor Date: Tue, 30 Nov 2010 10:45:03 -0500 Subject: [PATCH 1/1] week11 tweaks Signed-off-by: Jim Pryor --- week11.mdwn | 32 ++++++++++++++++++++++++++++++-- 1 file changed, 30 insertions(+), 2 deletions(-) diff --git a/week11.mdwn b/week11.mdwn index a7558ffd..79543c8a 100644 --- a/week11.mdwn +++ b/week11.mdwn @@ -91,7 +91,33 @@ to represent a list zipper where the break is at position 3, and the element occ ##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. 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: +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. + +It's important to set some ground rules for what will follow. If you don't understand these ground rules you will get confused. First off, for many uses of trees one wants some of the nodes or leafs in the tree to be *labeled* with additional information. It's important not to conflate the label with the node itself. Numerically one and the same piece of information---for example, the same `int`---could label two nodes of the tree without those nodes thereby being identical, as here: + + root + / \ + / \ + / \ label 1 + / \ + label 1 label 2 + +The leftmost leaf and the rightmost leaf have the same label; but they are different leafs. The leftmost leaf has a sibling leaf with the label 2; the rightmost leaf has no siblings that are leafs. Sometimes when one is diagramming trees, one will annotate the nodes with the labels, as above. Other times, when one is diagramming trees, one will instead want to annotate the nodes with tags to make it easier to refer to particular parts of the tree. So for instance, I could diagram the same tree as above as: + + 1 + / \ + 2 \ + / \ 5 + / \ + 3 4 + +Here I haven't drawn what the labels are. The leftmost leaf, the node tagged "3" in this diagram, doesn't have the label `3`. It has the label 1, as we said before. I just haven't put that into the diagram. The node tagged "2" doesn't have the label `2`. It doesn't have any label. The tree in this example only has labels on its leafs, not on any of its inner nodes. + +That is a second thing to note. In what follows, we'll only be working with *leaf-labeled* trees. In some uses of trees, one also wants labels on inner nodes. But we won't be discussing any such trees now. Our trees only have labels on their leafs. The diagrams below will tag all of the nodes, as in the second diagram above, and won't display what the leafs' labels are. + +Final introductory comment: in particular applications, you may only need to work with binary trees---trees where internal nodes always have exactly two subtrees. That is what we'll work with in the homework, for example. But to get the guiding idea of how tree zippers work, it's helpful first to think about trees that permit nodes to have many subtrees. So that's how we'll start. + +Suppose we have the following tree: 9200 / | \ @@ -104,7 +130,9 @@ Now how could we translate a zipper-like structure over to trees? What we're aim 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 marked `50`. We might use the following metalanguage notation to specify this: +This is a leaf-labeled tree whose labels aren't displayed. The `9200` and so on are tags to make it easier for us to refer to particular parts of the tree. + +Suppose 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 -- 2.11.0