From 12ba49b7826c64a85032e1640db29d4c947347f9 Mon Sep 17 00:00:00 2001 From: Jim Pryor Date: Wed, 1 Dec 2010 04:00:58 -0500 Subject: [PATCH] leafs->leaves Signed-off-by: Jim Pryor --- coroutines_and_aborts.mdwn | 2 +- tree_and_list_zippers.mdwn | 8 ++++---- 2 files changed, 5 insertions(+), 5 deletions(-) diff --git a/coroutines_and_aborts.mdwn b/coroutines_and_aborts.mdwn index 272765a4..50b6600f 100644 --- a/coroutines_and_aborts.mdwn +++ b/coroutines_and_aborts.mdwn @@ -21,7 +21,7 @@ Supposing you did work out an implementation of the tree zipper, then one way to / \ / \ 1 2 2 3 -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. +you won't move upwards at the same steps. Keep comparing "the next leaves" until they are different, or you exhaust the leaves of only one of the trees (then again the trees have different fringes), or you exhaust the leaves of both trees at the same time, without having found leaves 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 build a list containing the rest of each tree's fringe. diff --git a/tree_and_list_zippers.mdwn b/tree_and_list_zippers.mdwn index fafde0a4..ee627a7e 100644 --- a/tree_and_list_zippers.mdwn +++ b/tree_and_list_zippers.mdwn @@ -93,7 +93,7 @@ to represent a list zipper where the break is at position 3, and the element occ 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: +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 leaves 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 / \ @@ -102,7 +102,7 @@ It's important to set some ground rules for what will follow. If you don't under / \ 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: +The leftmost leaf and the rightmost leaf have the same label; but they are different leaves. The leftmost leaf has a sibling leaf with the label 2; the rightmost leaf has no siblings that are leaves. 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 / \ @@ -111,9 +111,9 @@ The leftmost leaf and the rightmost leaf have the same label; but they are diffe / \ 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 information labeling its leafs, not any of its inner nodes. The identity of its inner nodes is exhausted by their position in the tree. +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 information labeling its leaves, not any of its inner nodes. The identity of its inner nodes is exhausted by their position in the tree. -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. +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 leaves. The diagrams below will tag all of the nodes, as in the second diagram above, and won't display what the leaves' 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. -- 2.11.0