1HTML::Tree::AboutTrees(U3s)er Contributed Perl DocumentatHiToMnL::Tree::AboutTrees(3)
2
3
4

NAME

6       HTML::Tree::AboutTrees -- article on tree-shaped data structures in
7       Perl
8

SYNOPSIS

10         # This an article, not a module.
11

DESCRIPTION

13       The following article by Sean M. Burke first appeared in The Perl Jour‐
14       nal #18 and is copyright 2000 The Perl Journal. It appears courtesy of
15       Jon Orwant and The Perl Journal.  This document may be distributed
16       under the same terms as Perl itself.
17

Trees

19       -- Sean M. Burke
20
21           "AaaAAAaauugh!  Watch out for that tree!"
22             -- George of the Jungle theme
23
24       Perl's facility with references, combined with its automatic management
25       of memory allocation, makes it straightforward to write programs that
26       store data in structures of arbitrary form and complexity.
27
28       But I've noticed that many programmers, especially those who started
29       out with more restrictive languages, seem at home with complex but uni‐
30       form data structures -- N-dimensional arrays, or more struct-like
31       things like hashes-of-arrays(-of-hashes(-of-hashes), etc.) -- but
32       they're often uneasy with buliding more freeform, less tabular struc‐
33       tures, like tree-shaped data structures.
34
35       But trees are easy to build and manage in Perl, as I'll demonstrate by
36       showing off how the HTML::Element class manages elements in an HTML
37       document tree, and by walking you through a from-scratch implementation
38       of game trees.  But first we need to nail down what we mean by a
39       "tree".
40
41       Socratic Dialogues: "What is a Tree?"
42
43       My first brush with tree-shaped structures was in linguistics classes,
44       where tree diagrams are used to describe the syntax underlying natural
45       language sentences.  After learning my way around those trees, I
46       started to wonder -- are what I'm used to calling "trees" the same as
47       what programmers call "trees"?  So I asked lots of helpful and patient
48       programmers how they would define a tree.  Many replied with a answer
49       in jargon that they could not really explain (understandable, since
50       explaining things, especially defining things, is harder than people
51       think):
52
53           -- So what is a "tree", a tree-shaped data structure?
54
55           -- A tree is a special case of an acyclic directed graph!
56
57           -- What's a "graph"?
58
59           -- Um... lines... and... you draw it... with... arcs! nodes!  um...
60
61       The most helpful were folks who couldn't explain directly, but with
62       whom I could get into a rather Socratic dialog (where I asked the half-
63       dim half-earnest questions), often with much doodling of illustra‐
64       tions...
65
66       Question: so what's a tree?
67
68       Answer: A tree is a collection of nodes that are linked together in a,
69       well, tree-like way!  Like this [drawing on a napkin]:
70
71            A
72           / \
73          B   C
74            / ⎪ \
75           D  E  F
76
77       Q: So what do these letters represent?
78
79       A: Each is a different node, a bunch of data.  Maybe C is a bunch of
80       data that stores a number, maybe a hash table, maybe nothing at all
81       besides the fact that it links to D, E, and F (which are other nodes).
82
83       Q: So what're the lines between the nodes?
84
85       A: Links.  Also called "arcs".  They just symbolize the fact that each
86       node holds a list of nodes it links to.
87
88       Q: So what if I draw nodes and links, like this...
89
90            B -- E
91           / \  / \
92          A   C
93           \ /
94            E
95
96       Is that still a tree?
97
98       A: No, not at all.  There's a lot of un-treelike things about that.
99       First off, E has a link coming off of it going into nowhere.  You can't
100       have a link to nothing -- you can only link to another node.  Second
101       off, I don't know what that sideways link between B and E means...
102
103       Q: Okay, let's work our way up from something simpler.  Is this a
104       tree...?
105
106           A
107
108       A: Yes, I suppose.  It's a tree of just one node.
109
110       Q: And how about...
111
112          A
113
114          B
115
116       A: No, you can't just have nodes floating there, unattached.
117
118       Q: Okay, I'll link A and B.  How's this?
119
120          A
121
122          B
123
124       A: Yup, that's a tree.  There's a node A, and a node B, and they're
125       linked.
126
127       Q: How is that tree any different from this one...?
128
129          B
130
131          A
132
133       A: Well, in both cases A and B are linked.  But it's in a different
134       direction.
135
136       Q: Direction?  What does the direction mean?
137
138       A: Well, it depends what the tree represents.  If it represents a cate‐
139       gorization, like this:
140
141                 citrus
142              /    ⎪    \
143          orange  lemon  kumquat ...
144
145       then you mean to say that oranges, lemons, kumquats, etc., are a kind
146       of citrus.  But if you drew it upside down, you'd be saying, falsely,
147       that citrus is a kind of kumquat, a kind of lemon, and a kind of
148       orange.  If the tree represented cause-and-effect (or at least what
149       situations could follow others), or represented what's a part of what,
150       you wouldn't want to get those backwards, either.  So with the nodes
151       you draw together on paper, one has to be over the other, so you can
152       tell which way the relationship in the tree works.
153
154       Q:  So are these two trees the same?
155
156            A          A
157           / \        / \
158          B   C      B   \
159                          C
160
161       A: Yes, although by convention we often try to line up things in the
162       same generation, like it is in the diagram on the left.
163
164       Q: "generation"?  This is a family tree?
165
166       A: No, not unless it's a family tree for just yeast cells or something
167       else that reproduces asexually.  But for sake of having lots of terms
168       to use, we just pretend that links in the tree represent the "is a
169       child of" relationship, instead of "is a kind of" or "is a part of", or
170       "could result from", or whatever the real relationship is.  So we get
171       to borrow a lot of kinship words for describing trees -- B and C are
172       "children" (or "daughters") of A; A is the "parent" (or "mother") of B
173       and C.  Node C is a "sibling" (or "sister") of node C; and so on, with
174       terms like "descedants" (a node's children, children's children, etc.),
175       and "generation" (all the nodes at the same "level" in the tree, i.e.,
176       are either all grandchildren of the top node, or all great-grand-chil‐
177       dren, etc.), and "lineage" or "ancestors" (parents, and parent's par‐
178       ents, etc., all the way to the topmost node).
179
180       So then we get to express rules in terms like "A node cannot have more
181       than one parent", which means that this is not a valid tree:
182
183           A
184          / \
185         B   C
186          \ /
187           E
188
189       And: "A node can't be its own parent", which excludes this looped-up
190       connection:
191
192           /\
193          A  ⎪
194           \/
195
196       Or, put more generally: "A node can't be its own ancestor", which
197       excludes the above loop, as well as the one here:
198
199             /\
200            Z  ⎪
201           /   ⎪
202          A    ⎪
203         / \   ⎪
204        B   C  ⎪
205             \/
206
207       That tree is excluded because A is a child of Z, and Z is a child of C,
208       and C is a child of A, which means A is its own great-grandparent.  So
209       this whole network can't be a tree, because it breaks the sort of
210       meta-rule: once any node in the supposed tree breaks the rules for
211       trees, you don't have a tree anymore.
212
213       Q: Okay, now, are these two trees the same?
214
215            A         A
216          / ⎪ \     / ⎪ \
217         B  C  D   D  C  B
218
219       A: It depends whether you're basing your concept of trees on each node
220       having a set (unordered list) of children, or an (ordered) list of
221       children.  It's a question of whether ordering is important for what
222       you're doing.  With my diagram of citrus types, ordering isn't impor‐
223       tant, so these tree diagrams express the same thing:
224
225                 citrus
226              /    ⎪    \
227          orange  lemon  kumquat
228
229                  citrus
230              /     ⎪    \
231          kumquat  orange  lemon
232
233       because it doesn't make sense to say that oranges are "before" or
234       "after" kumquats in the whole botanical scheme of things.  (Unless, of
235       course, you are using ordering to mean something, like a degree of
236       genetic similarity.)
237
238       But consider a tree that's a diagram of what steps are comprised in an
239       activity, to some degree of specificity:
240
241                  make tea
242                /    ⎪     \
243          pour     infuse   serve
244        hot water    / \
245       in cup/pot  /     \
246                  add     let
247                  tea     sit
248                 leaves
249
250       This means that making tea consists of putting hot water in a cup or
251       put, infusing it (which itself consists of adding tea leaves and let‐
252       ting it sit), then serving it -- in that order.  If you serve an empty
253       dry pot (sipping from empty cups, etc.), let it sit, add tea leaves,
254       and pour in hot water, then what you're doing is performance art, not
255       tea preparation:
256
257                 perfomance
258                   art
259               /    ⎪     \
260          serve   infuse    pour
261                   / \       hot water
262                 /     \      in cup/pot
263                let     add
264                sit     tea
265                       leaves
266
267       Except for my having renamed the root, this tree is the same as the
268       making-tea tree as far as what's under what, but it differs in order,
269       and what the tree means makes the order important.
270
271       Q: Wait -- "root"?  What's a root?
272
273       A: Besides kinship terms like "mother" and "daugher", the jargon for
274       tree parts also has terms from real-life tree parts:  the part that
275       everything else grows from is called the root; and nodes that don't
276       have nodes attached to them (i.e., childless nodes) are called
277       "leaves".
278
279       Q: But you've been drawing all your trees with the root at the top and
280       leaves at the bottom.
281
282       A: Yes, but for some reason, that's the way everyone seems to think of
283       trees.  They can draw trees as above; or they can draw them sort of
284       sideways with indenting representing what nodes are children of what:
285
286         * make tea
287            * pour hot water in cup/pot
288            * infuse
289               * add tea leaves
290               * let sit
291            * serve
292
293       ...but folks almost never seem to draw trees with the root at the bot‐
294       tom.  So imagine it's based on spider plant in a hanging pot.  Unfortu‐
295       nately, spider plants aren't botanically trees, they're plants; but
296       "spider plant diagram" is rather a mouthful, so let's just call them
297       trees.
298
299       Trees Defined Formally
300
301       In time, I digested all these assorted facts about programmers' ideas
302       of trees (which turned out to be just a more general case of linguistic
303       ideas of trees) into a single rule:
304
305       * A node is an item that contains ("is over", "is parent of", etc.)
306       zero or more other nodes.
307
308       From this you can build up formal definitions for useful terms, like
309       so:
310
311       * A node's descendants are defined as all its children, and all their
312       children, and so on.  Or, stated recursively: a node's descendants are
313       all its children, and all its children's descendants.  (And if it has
314       no children, it has no descendants.)
315
316       * A node's ancestors consist of its parent, and its parent's parent,
317       etc, up to the root.  Or, recursively: a node's ancestors consist of
318       its parent and its parent's ancestors.  (If it has no parent, it has no
319       ancestors.)
320
321       * A tree is a root node and all the root's descendants.
322
323       And you can add a proviso or two to clarify exactly what I impute to
324       the word "other" in "other nodes":
325
326       * A node cannot contain itself, or contain any node that contains it,
327       etc.  Looking at it the other way: a node cannot be its own parent or
328       ancestor.
329
330       * A node can be root (i.e., no other node contains it) or can be con‐
331       tained by only one parent; no node can be the child of two or more par‐
332       ents.
333
334       Add to this the idea that children are sometimes ordered, and sometimes
335       not, and that's about all you need to know about defining what a tree
336       is.  From there it's a matter of using them.
337
338       Markup Language Trees: HTML-Tree
339
340       While not all markup languages are inherently tree-like, the best-known
341       family of markup languages, HTML, SGML, and XML, are about as tree-like
342       as you can get.  In these languages, a document consists of elements
343       and character data in a tree structure where there is one root element,
344       and elements can contain either other elements, or character data.
345
346           Footnote: For sake of simplicity, I'm glossing over comments (<!--
347           ... -->), processing instructions (<?xml version='1.0'>), and dec‐
348           larations (<!ELEMENT ...>, <!DOCTYPE ...>).  And I'm not bothering
349           to distinguish entity references (&lt;, &#64;) or CDATA sections
350           (<![CDATA[ ...]]>) from normal text.
351
352       For example, consider this HTML document:
353
354         <html lang="en-US">
355           <head>
356             <title>
357               Blank Document!
358             </title>
359           </head>
360           <body bgcolor="#d010ff">
361             I've got
362             <em>
363               something to saaaaay
364             </em>
365             !
366           </body>
367         </html>
368
369       I've indented this to point out what nodes (elements or text items) are
370       children of what, with each node on a line of its own.
371
372       The HTML::TreeBuilder module (in the CPAN distribution HTML-Tree) does
373       the work of taking HTML source and building in memory the tree that the
374       document source represents.
375
376           Footnote: it requires the HTML::Parser module, which tokenizes the
377           source -- i.e., identifies each tag, bit of text, comment, etc.
378
379       The trees structures that it builds represent bits of text with normal
380       Perl scalar string values; but elements are represented with objects --
381       that is, chunks of data that belong to a class (in this case,
382       HTML::Element), a class that provides methods (routines) for accessing
383       the pieces of data in each element, and otherwise doing things with
384       elements.  (See my article in TPJ#17 for a quick explanation of
385       objects, the POD document "perltoot" for a longer explanation, or
386       Damian Conway's excellent book Object-Oriented Perl for the full
387       story.)
388
389       Each HTML::Element object contains a number of pieces of data:
390
391       * its element name ("html", "h1", etc., accessed as $element->tag)
392
393       * a list of elements (or text segments) that it contains, if any
394       (accessed as $element->content_list or $element->content, depending on
395       whether you want a list, or an arrayref)
396
397       * what element, if any, contains it (accessed as $element->parent)
398
399       * and any SGML attributes that the element has, such as "lang="en-US"",
400       "align="center"", etc. (accessed as $element->attr('lang'), $ele‐
401       ment->attr('center'), etc.)
402
403       So, for example, when HTML::TreeBuilder builds the tree for the above
404       HTML document source, the object for the "body" element has these
405       pieces of data:
406
407        * element name: "body"
408        * nodes it contains:
409           the string "I've got "
410           the object for the "em" element
411           the string "!"
412        * its parent:
413           the object for the "html" element
414        * bgcolor: "#d010ff"
415
416       Now, once you have this tree of objects, almost anything you'd want to
417       do with it starts with searching the tree for some bit of information
418       in some element.
419
420       Accessing a piece of information in, say, a hash of hashes of hashes,
421       is straightforward:
422
423         $password{'sean'}{'sburke1'}{'hpux'}
424
425       because you know that all data points in that structure are accessible
426       with that syntax, but with just different keys.  Now, the "em" element
427       in the above HTML tree does happen to be accessible as the root's child
428       #1's child #1:
429
430         $root->content->[1]->content->[1]
431
432       But with trees, you typically don't know the exact location (via
433       indexes) of the data you're looking for.  Instead, finding what you
434       want will typically involve searching through the tree, seeing if every
435       node is the kind you want.  Searching the whole tree is simple enough
436       -- look at a given node, and if it's not what you want, look at its
437       children, and so on.  HTML-Tree provides several methods that do this
438       for you, such as "find_by_tag_name", which returns the elements (or the
439       first element, if called in scalar context) under a given node (typi‐
440       cally the root) whose tag name is whatever you specify.
441
442       For example, that "em" node can be found as:
443
444         my $that_em = $root->find_by_tag_name('em');
445
446       or as:
447
448         @ems = $root->find_by_tag_name('em');
449          # will only have one element for this particular tree
450
451       Now, given an HTML document of whatever structure and complexity, if
452       you wanted to do something like change every
453
454           <em>stuff</em>
455
456       to
457
458           <em class="funky"> <b>[-</b> stuff <b>-]</b> </em>
459
460       the first step is to frame this operation in terms of what you're doing
461       to the tree.  You're changing this:
462
463             em
464
465             ...
466
467       to this:
468
469             em
470           /  ⎪  \
471          b  ...   b
472          ⎪        ⎪
473         "[-"     "-]"
474
475       In other words, you're finding all elements whose tag name is "em",
476       setting its class attribute to "funky", and adding one child to the
477       start of its content list -- a new "b" element whose content is the
478       text string "[-" -- and one to the end of its content list -- a new "b"
479       element whose content is the text string "-]".
480
481       Once you've got it in these terms, it's just a matter of running to the
482       HTML::Element documentation, and coding this up with calls to the
483       appropriate methods, like so:
484
485         use HTML::Element 1.53;
486         use HTML::TreeBuilder 2.96;
487         # Build the tree by parsing the document
488         my $root = HTML::TreeBuilder->new;
489         $root->parse_file('whatever.html'); # source file
490
491         # Now make new nodes where needed
492         foreach my $em ($root->find_by_tag_name('em')) {
493           $em->attr('class', 'funky'); # Set that attribute
494
495           # Make the two new B nodes
496           my $new1 = HTML::Element->new('b');
497           my $new2 = HTML::Element->new('b');
498           # Give them content (they have none at first)
499           $new1->push_content('[-');
500           $new2->push_content('-]');
501
502           # And put 'em in place!
503           $em->unshift_content($new1);
504           $em->push_content($new2);
505         }
506         print
507          "<!-- Looky see what I did! -->\n",
508          $root->as_HTML(), "\n";
509
510       The class HTML::Element provides just about every method I can image
511       you needing, for manipulating trees made of HTML::Element objects.
512       (And what it doesn't directly provide, it will give you the components
513       to build it with.)
514
515       Building Your Own Trees
516
517       Theoretically, any tree is pretty much like any other tree, so you
518       could use HTML::Element for anything you'd ever want to do with tree-
519       arranged objects.  However, as its name implies, HTML::Element is basi‐
520       cally for HTML elements; it has lots of features that make sense only
521       for HTML elements (like the idea that every element must have a
522       tag-name).  And it lacks some features that might be useful for general
523       applications -- such as any sort of checking to make sure that you're
524       not trying to arrange objects in a non-treelike way.  For a general-
525       purpose tree class that does have such features, you can use
526       Tree::DAG_Node, also available from CPAN.
527
528       However, if your task is simple enough, you might find it overkill to
529       bother using Tree::DAG_Node.  And, in any case, I find that the best
530       way to learn how something works is to implement it (or something like
531       it, but simpler) yourself.  So I'll here discuss how you'd implement a
532       tree structure, without using any of the existing classes for tree
533       nodes.
534
535       Implementation: Game Trees for Alak
536
537       Suppose that the task at hand is to write a program that can play
538       against a human opponent at a strategic board game (as opposed to a
539       board game where there's an element of chance).  For most such games, a
540       "game tree" is an essential part of the program (as I will argue,
541       below), and this will be our test case for implementing a tree struc‐
542       ture from stratch.
543
544       For sake of simplicity, our game is not chess or backgammon, but
545       instead a much simpler game called Alak.  Alak was invented by the
546       mathematician A. K.  Dewdney, and described in his 1984 book Plani‐
547       verse. The rules of Alak are simple:
548
549           Footnote: Actually, I'm describing only my interpetation of the
550           rules Dewdney describes in Planiverse.  Many other interpretations
551           are possible.
552
553       * Alak is a two-player game played on a one-dimensional board with
554       eleven slots on it.  Each slot can hold at most one piece at a time.
555       There's two kinds of pieces, which I represent here as "x" and "o" --
556       x's belong to one player (called X), o's to the other (called O).
557
558       * The initial configuration of the board is:
559
560          xxxx___oooo
561
562       For sake of the article, the slots are numbered from 1 (on the left) to
563       11 (on the right), and X always has the first move.
564
565       * The players take turns moving.  At each turn, each player can move
566       only one piece, once.  (This unlike checkers, where you move one piece
567       per move but get to keep moving it if you jump an your opponent's
568       piece.) A player cannot pass up on his turn.  A player can move any one
569       of his pieces to the next unoccupied slot to its right or left, which
570       may involve jumping over occupied slots.  A player cannot move a piece
571       off the side of the board.
572
573       * If a move creates a pattern where the opponent's pieces are sur‐
574       rounded, on both sides, by two pieces of the mover's color (with no
575       intervening unoccupied blank slot), then those surrounded pieces are
576       removed from the board.
577
578       * The goal of the game is to remove all of your opponent's pieces, at
579       which point the game ends.  Removing all-but-one ends the game as well,
580       since the opponent can't surround you with one piece, and so will
581       always lose within a few moves anyway.
582
583       Consider, then, this rather short game where X starts:
584
585         xxxx___oooo
586           ^         Move 1: X moves from 3 (shown with caret) to 5
587                      (Note that any of X's pieces could move, but
588                      that the only place they could move to is 5.)
589         xx_xx__oooo
590                 ^   Move 2: O moves from 9 to 7.
591         xx_xx_oo_oo
592            ^        Move 3: X moves from 4 to 6.
593         xx__xxoo_oo
594                  ^  Move 4: O (stupidly) moves from 10 to 9.
595         xx__xxooo_o
596             ^       Move 5: X moves from 5 to 10, making the board
597                     "xx___xoooxo".  The three o's that X just
598                     surrounded are removed.
599         xx___x___xo
600                     O has only one piece, so has lost.
601
602       Now, move 4 could have gone quite the other way:
603
604         xx__xxoo_oo
605                     Move 4: O moves from 8 to 4, making the board
606                     "xx_oxxo__oo".  The surrounded x's are removed.
607         xx_o__o__oo
608         ^           Move 5: X moves from 1 to 2.
609         _xxo__o__oo
610               ^     Move 6: O moves from 7 to 6.
611         _xxo_o___oo
612          ^          Move 7: X moves from 2 to 5, removing the o at 4.
613         __x_xo___oo
614                     ...and so on.
615
616       To teach a computer program to play Alak (as player X, say), it needs
617       to be able to look at the configuration of the board, figure out what
618       moves it can make, and weigh the benefit or costs, immediate or even‐
619       tual, of those moves.
620
621       So consider the board from just before move 3, and figure all the pos‐
622       sible moves X could make.  X has pieces in slots 1, 2, 4, and 5.  The
623       leftmost two x's (at 1 and 2) are up against the end of the board, so
624       they can move only right.  The other two x's (at 4 and 5) can move
625       either right or left:
626
627         Starting board: xx_xx_oo_oo
628          moving 1 to 3 gives _xxxx_oo_oo
629          moving 2 to 3 gives x_xxx_oo_oo
630          moving 4 to 3 gives xxx_x_oo_oo
631          moving 5 to 3 gives xxxx__oo_oo
632          moving 4 to 6 gives xx__xxoo_oo
633          moving 5 to 6 gives xx_x_xoo_oo
634
635       For the computer to decide which of these is the best move to make, it
636       needs to quantify the benefit of these moves as a number -- call that
637       the "payoff".  The payoff of a move can be figured as just the number
638       of x pieces removed by the most recent move, minus the nubmer of o
639       pieces removed by the mots recent move.  (It so happens that the rules
640       of the game mean that no move can delete both o's and x's, but the for‐
641       mula still applies.)  Since none of these moves removed any pieces, all
642       these moves have the same immediate payoff: 0.
643
644       Now, we could race ahead and write an Alak-playing program that could
645       use the immediate payoff to decide which is the best move to make.  And
646       when there's more than one best move (as here, where all the moves are
647       equally good), it could choose randomly between the good alternatives.
648       This strategy is simple to implement; but it makes for a very dumb pro‐
649       gram.  Consider what O's response to each of the potential moves
650       (above) could be.  Nothing immediately suggests itself for the first
651       four possibilities (X having moved something to position 3), but either
652       of the last two (illustrated below) are pretty perilous, because in
653       either case O has the obvious option (which he would be foolish to pass
654       up) of removing x's from the board:
655
656          xx_xx_oo_oo
657             ^        X moves 4 to 6.
658          xx__xxoo_oo
659                 ^    O moves 8 to 4, giving "xx_oxxo__oo".  The two
660                      surrounded x's are removed.
661          xx_o__o__oo
662
663       or
664
665          xx_xx_oo_oo
666              ^       X moves 5 to 6.
667          xx_x_xoo_oo
668                 ^    O moves 8 to 5, giving "xx_xoxo__oo".  The one
669                      surrounded x is removed.
670          xx_xo_o__oo
671
672       Both contingencies are quite bad for X -- but this is not captured by
673       the fact that they start out with X thinking his move will be harmless,
674       having a payoff of zero.
675
676       So what's needed is for X to think more than one step ahead -- to con‐
677       sider not merely what it can do in this move, and what the payoff is,
678       but to consider what O might do in response, and the payoff of those
679       potential moves, and so on with X's possible responses to those cases
680       could be.  All these possibilities form a game tree -- a tree where
681       each node is a board, and its children are successors of that node --
682       i.e., the boards that could result from every move possible, given the
683       parent's board.
684
685       But how to represent the tree, and how to represent the nodes?
686
687       Well, consider that a node holds several pieces of data:
688
689       1) the configuration of the board, which, being nice and simple and
690       one-dimensional, can be stored as just a string, like "xx_xx_oo_oo".
691
692       2) whose turn it is, X or O.  (Or: who moved last, from which we can
693       figure whose turn it is).
694
695       3) the successors (child nodes).
696
697       4) the immediate payoff of having moved to this board position from its
698       predecessor (parent node).
699
700       5) and what move gets us from our predecessor node to here.  (Granted,
701       knowing the board configuration before and after the move, it's easy to
702       figure out the move; but it's easier still to store it as one is figur‐
703       ing out a node's successors.)
704
705       6) whatever else we might want to add later.
706
707       These could be stored equally well in an array or in a hash, but it's
708       my experience that hashes are best for cases where you have more than
709       just two or three bits of data, or especially when you might need to
710       add new bits of data.  Moreover, hash key names are mnemonic --
711       $node->{'last_move_payoff'} is plain as day, whereas it's not so easy
712       having to remember with an array that $node->[3] is where you decided
713       to keep the payoff.
714
715           Footnote: Of course, there are ways around that problem: just swear
716           you'll never use a real numeric index to access data in the array,
717           and instead use constants with mnemonic names:
718
719             use strict;
720             use constant idx_PAYOFF => 3;
721             ...
722             $n->[idx_PAYOFF]
723
724           Or use a pseudohash.  But I prefer to keep it simple, and use a
725           hash.
726
727           These are, incidentally, the same arguments that people weigh when
728           trying to decide whether their object-oriented modules should be
729           based on blessed hashes, blessed arrays, or what.  Essentially the
730           only difference here is that we're not blessing our nodes or talk‐
731           ing in terms of classes and methods.
732
733           [end footnote]
734
735       So, we might as well represent nodes like so:
736
737         $node = { # hashref
738            'board'          => ...board string, e.g., "xx_x_xoo_oo"
739
740            'last_move_payoff' => ...payoff of the move
741                                   that got us here.
742
743            'last_move_from' =>  ...the start...
744            'last_move_to'   =>  ...and end point of the move
745                                     that got us here.  E.g., 5 and 6,
746                                     representing a move from 5 to 6.
747
748            'whose_turn'     => ...whose move it then becomes.
749                                  just an 'x' or 'o'.
750
751            'successors' => ...the successors
752         };
753
754       Note that we could have a field called something like 'last_move_who'
755       to denote who last moved, but since turns in Alak always alternate (and
756       no-one can pass), storing whose move it is now and who last moved is
757       redundant -- if X last moved, it's O turn now, and vice versa.  I chose
758       to have a 'whose_turn' field instead of a 'last_move_who', but it
759       doesn't really matter.  Either way, we'll end up inferring one from the
760       other at several points in the program.
761
762       When we want to store the successors of a node, should we use an array
763       or a hash?  On the one hand, the successors to $node aren't essentially
764       ordered, so there's no reason to use an array per se; on the other
765       hand, if we used a hash, with successor nodes as values, we don't have
766       anything particularly meaningful to use as keys.  (And we can't use the
767       successors themselves as keys, since the nodes are referred to by hash
768       references, and you can't use a reference as a hash key.)  Given no
769       particularly compelling reason to do otherwise, I choose to just use an
770       array to store all a node's successors, although the order is never
771       actually used for anything:
772
773         $node = {
774           ...
775           'successors' => [ ...nodes... ],
776           ...
777         };
778
779       In any case, now that we've settled on what should be in a node, let's
780       make a little sample tree out of a few nodes and see what we can do
781       with it:
782
783         # Board just before move 3 in above game
784         my $n0 = {
785           'board' => 'xx_xx_oo_oo',
786           'last_move_payoff' => 0,
787           'last_move_from' =>  9,
788           'last_move_to'   =>  7,
789           'whose_turn' => 'x',
790           'successors' => [],
791         };
792
793         # And, for now, just two of the successors:
794
795         # X moves 4 to 6, giving xx__xxoo_oo
796         my $n1 = {
797           'board' => 'xx__xxoo_oo',
798           'last_move_payoff' => 0,
799           'last_move_from' =>  4,
800           'last_move_to'   =>  6,
801           'whose_turn' => 'o',
802           'successors' => [],
803         };
804
805         # or X moves 5 to 6, giving xx_x_xoo_oo
806         my $n2 = {
807           'board' => 'xx_x_xoo_oo',
808           'last_move_payoff' => 0,
809           'last_move_from' =>  5,
810           'last_move_to'   =>  6,
811           'whose_turn' => 'o',
812           'successors' => [],
813         };
814
815         # Now connect them...
816         push @{$n0->{'successors'}}, $n1, $n2;
817
818       Digression: Links to Parents
819
820       In comparing what we store in an Alak game tree node to what HTML::Ele‐
821       ment stores in HTML element nodes, you'll note one big difference:
822       every HTML::Element node contains a link to its parent, whereas we
823       don't have our Alak nodes keeping a link to theirs.
824
825       The reason this can be an important difference is because it can affect
826       how Perl knows when you're not using pieces of memory anymore.  Con‐
827       sider the tree we just built, above:
828
829             node 0
830            /      \
831         node 1    node 2
832
833       There's two ways Perl knows you're using a piece of memory: 1) it's
834       memory that belongs directly to a variable (i.e., is necessary to hold
835       that variable's value, or values in the case of a hash or array), or 2)
836       it's a piece of memory that something holds a reference to.  In the
837       above code, Perl knows that the hash for node 0 (for board
838       "xx_xx_oo_oo") is in use because something (namely, the variable $n0)
839       holds a reference to it.  Now, even if you followed the above code with
840       this:
841
842         $n1 = $n2 = 'whatever';
843
844       to make your variables $n1 and $n2 stop holding references to the
845       hashes for the two successors of node 0, Perl would still know that
846       those hashes are still in use, because node 0's successors array holds
847       a reference to those hashes.  And Perl knows that node 0 is still in
848       use because something still holds a reference to it.  Now, if you
849       added:
850
851         my $root = $n0;
852
853       This would change nothing -- there's just be two things holding a ref‐
854       erence to the node 0 hash, which in turn holds a reference to the node
855       1 and node 2 hashes.  And if you then added:
856
857         $n0 = 'stuff';
858
859       still nothing would change, because something ($root) still holds a
860       reference to the node 0 hash.  But once nothing holds a reference to
861       the node 0 hash, Perl will know it can destroy that hash (and reclaim
862       the memory for later use, say), and once it does that, nothing will
863       hold a reference to the node 1 or the node 2 hashes, and those will be
864       destroyed too.
865
866       But consider if the node 1 and node 2 hashes each had an attribute
867       "parent" (or "predecessor") that held a reference to node 0.  If your
868       program stopped holding a reference to the node 0 hash, Perl could not
869       then say that nothing holds a reference to node 0 -- because node 1 and
870       node 2 still do.  So, the memory for nodes 0, 1, and 2 would never get
871       reclaimed (until your program ended, at which point Perl destroys
872       everything).  If your program grew and discarded lots of nodes in the
873       game tree, but didn't let Perl know it could reclaim their memory, your
874       program could grow to use immense amounts of memory -- never a nice
875       thing to have happen.  There's three ways around this:
876
877       1) When you're finished with a node, delete the reference each of its
878       children have to it (in this case, deleting $n1->{'parent'}, say).
879       When you're finished with a whole tree, just go through the whole tree
880       erasing links that children have to their children.
881
882       2) Reconsider whether you really need to have each node hold a refer‐
883       ence to its parent.  Just not having those links will avoid the whole
884       problem.
885
886       3) use the WeakRef module with Perl 5.6 or later.  This allows you to
887       "weaken" some references (like the references that node 1 and 2 could
888       hold to their parent) so that they don't count when Perl goes asking
889       whether anything holds a reference to a given piece of memory.  This
890       wonderful new module eliminates the headaches that can often crop up
891       with either of the two previous methods.
892
893       It so happens that our Alak program is simple enough that we don't need
894       for our nodes to have links to their parents, so the second solution is
895       fine.  But in a more advanced program, the first or third solutions
896       might be unavoidable.
897
898       Recursively Printing the Tree
899
900       I don't like working blind -- if I have any kind of a complex data
901       structure in memory for a program I'm working on, the first thing I do
902       is write something that can dump that structure to the screen so I can
903       make sure that what I think is in memory really is what's in memory.
904       Now, I could just use the "x" pretty-printer command in Perl's interac‐
905       tive debugger, or I could have the program use the "Data::Dumper" mod‐
906       ule.  But in this case, I think the output from those is rather too
907       verbose.  Once we have trees with dozens of nodes in them, we'll really
908       want a dump of the tree to be as concise as possible, hopefully just
909       one line per node.  What I'd like is something that can print $n0 and
910       its successors (see above) as something like:
911
912         xx_xx_oo_oo  (O moved 9 to 7, 0 payoff)
913           xx__xxoo_oo  (X moved 4 to 6, 0 payoff)
914           xx_x_xoo_oo  (X moved 5 to 6, 0 payoff)
915
916       A subroutine to print a line for a given node, and then do that again
917       for each successor, would look something like:
918
919         sub dump_tree {
920           my $n = $_[0]; # "n" is for node
921           print
922             ...something expressing $n'n content...
923           foreach my $s (@{$n->{'successors'}}) {
924             # "s for successor
925             dump($s);
926           }
927         }
928
929       And we could just start that out with a call to "dump_tree($n0)".
930
931       Since this routine...
932
933           Footnote: I first wrote this routine starting out with "sub dump
934           {".  But when I tried actually calling "dump($n0)", Perl would dump
935           core!  Imagine my shock when I discovered that this is absolutely
936           to be expected -- Perl provides a built-in function called "dump",
937           the purpose of which is to, yes, make Perl dump core.  Calling our
938           routine "dump_tree" instead of "dump" neatly avoids that problem.
939
940       ...does its work (dumping the subtree at and under the given node) by
941       calling itself, it's recursive.  However, there's a special term for
942       this kind of recursion across a tree: traversal.  To traverse a tree
943       means to do something to a node, and to traverse its children.  There's
944       two prototypical ways to do this, depending on what happens when:
945
946         traversing X in pre-order:
947           * do something to X
948           * then traverse X's children
949
950         traversing X in post-order:
951           * traverse X's children
952           * then do something to X
953
954       Dumping the tree to the screen the way we want it happens to be a mat‐
955       ter of pre-order traversal, since the thing we do (print a description
956       of the node) happens before we recurse into the successors.
957
958       When we try writing the "print" statement for our above "dump_tree", we
959       can get something like:
960
961         sub dump_tree {
962           my $n = $_[0];
963
964           # "xx_xx_oo_oo  (O moved 9 to 7, 0 payoff)"
965           print
966             $n->{'board'}, "  (",
967             ($n->{'whose_turn'} eq 'o' ? 'X' : 'O'),
968             # Infer who last moved from whose turn it is now.
969             " moved ", $n->{'last_move_from'},
970             " to ",    $n->{'last_move_to'},
971             ", ",      $n->{'last_move_payoff'},
972             " payoff)\n",
973           ;
974
975           foreach my $s (@{$n->{'successors'}}) {
976             dump_tree($s);
977           }
978         }
979
980       If we run this on $n0 from above, we get this:
981
982         xx_xx_oo_oo  (O moved 9 to 7, 0 payoff)
983         xx__xxoo_oo  (X moved 4 to 6, 0 payoff)
984         xx_x_xoo_oo  (X moved 5 to 6, 0 payoff)
985
986       Each line on its own is fine, but we forget to allow for indenting, and
987       without that we can't tell what's a child of what.  (Imagine if the
988       first successor had successors of its own -- you wouldn't be able to
989       tell if it were a child, or a sibling.)  To get indenting, we'll need
990       to have the instances of the "dump_tree" routine know how far down in
991       the tree they're being called, by passing a depth parameter between
992       them:
993
994         sub dump_tree {
995           my $n = $_[0];
996           my $depth = $_[1];
997           $depth = 0 unless defined $depth;
998           print
999             "  " x $depth,
1000             ...stuff...
1001           foreach my $s (@{$n->{'successors'}}) {
1002             dump_tree($s, $depth + 1);
1003           }
1004         }
1005
1006       When we call "dump_tree($n0)", $depth (from $_[1]) is undefined, so
1007       gets set to 0, which translates into an indenting of no spaces.  But
1008       when "dump_tree" invokes itself on $n0's children, those instances see
1009       $depth + 1 as their $_[1], giving appropriate indenting.
1010
1011           Footnote: Passing values around between different invocations of a
1012           recursive routine, as shown, is a decent way to share the data.
1013           Another way to share the data is by keeping it in a global vari‐
1014           able, like $Depth, initially set to 0.  Each time "dump_tree" is
1015           about to recurse, it must "++$Depth", and when it's back, it must
1016           "--$Depth".
1017
1018           Or, if the reader is familiar with closures, consider this
1019           approach:
1020
1021             sub dump_tree {
1022               # A wrapper around calls to a recursive closure:
1023               my $start_node = $_[0];
1024               my $depth = 0;
1025                # to be shared across calls to $recursor.
1026               my $recursor;
1027               $recursor = sub {
1028                 my $n = $_[0];
1029                 print "  " x $depth,
1030                   ...stuff...
1031                 ++$depth;
1032                 foreach my $s (@{$n->{'successors'}}) {
1033                   $recursor->($s);
1034                 }
1035                 --$depth;
1036               }
1037               $recursor->($start_node); # start recursing
1038               undef $recursor;
1039             }
1040
1041           The reader with an advanced understanding of Perl's reference-
1042           count-based garbage collection is invited to consider why it is
1043           currently necessary to undef $recursor (or otherwise change its
1044           value) after all recursion is done.
1045
1046           The reader whose mind is perverse in other ways is invited to con‐
1047           sider how (or when!) passing a depth parameter around is unneces‐
1048           sary because of information that Perl's caller(N) function reports!
1049
1050           [end footnote]
1051
1052       Growing the Tree
1053
1054       Our "dump_tree" routine works fine for the sample tree we've got, so
1055       now we should get the program working on making its own trees, starting
1056       from a given board.
1057
1058       In "Games::Alak" (the CPAN-released version of Alak that uses essen‐
1059       tially the same code that we're currently discussing the tree-related
1060       parts of), there is a routine called "figure_successors" that, given
1061       one childless node, will figure out all its possible successors.  That
1062       is, it looks at the current board, looks at every piece belonging to
1063       the player whose turn it is, and considers the effect of moving each
1064       piece every possible way -- notably, it figures out the immediate pay‐
1065       off, and if that move would end the game, it notes that by setting an
1066       "endgame" entry in that node's hash.  (That way, we know that that's a
1067       node that can't have successors.)
1068
1069       In the code for "Games::Alak", "figure_successors" does all these
1070       things, in a rather straightforward way.  I won't walk you through the
1071       details of the "figure_successors" code I've written, since the code
1072       has nothing much to do with trees, and is all just implementation of
1073       the Alak rules for what can move where, with what result.  Espicially
1074       interested readers can puzzle over that part of code in the source
1075       listing in the archive from CPAN, but others can just assume that it
1076       works as described above.
1077
1078       But consider that "figure_successors", regardless of its inner work‐
1079       ings, does not grow the tree; it only makes one set of successors for
1080       one node at a time.  It has to be up to a different routine to call
1081       "figure_successors", and to keep applying it as needed, in order to
1082       make a nice big tree that our game-playing program can base its deci‐
1083       sions on.
1084
1085       Now, we could do this by just starting from one node, applying "fig‐
1086       ure_successors" to it, then applying "figure_successors" on all the
1087       resulting children, and so on:
1088
1089         sub grow {  # Just a first attempt at this!
1090           my $n = $_[0];
1091           figure_successors($n);
1092            unless
1093             @{$n->{'successors'}}
1094               # already has successors.
1095             or $n->{'endgame'}
1096               # can't have successors.
1097           }
1098           foreach my $s (@{$n->{'successors'}}) {
1099             grow($s); # recurse
1100           }
1101         }
1102
1103       If you have a game tree for tic-tac-toe, and you grow it without limi‐
1104       tation (as above), you will soon enough have a fully "solved" tree,
1105       where every node that can have successors does, and all the leaves of
1106       the tree are all the possible endgames (where, in each case, the board
1107       is filled).  But a game of Alak is different from tic-tac-toe, because
1108       it can, in theory, go on forever.  For example, the following sequence
1109       of moves is quite possible:
1110
1111         xxxx___oooo
1112         xxx_x__oooo
1113         xxx_x_o_ooo
1114         xxxx__o_ooo (x moved back)
1115         xxxx___oooo (o moved back)
1116         ...repeat forever...
1117
1118       So if you tried using our above attempt at a "grow" routine, Perl would
1119       happily start trying to construct an infinitely deep tree, containing
1120       an infinite number of nodes, consuming an infinite amount of memory,
1121       and requiring an infinite amount of time.  As the old saying goes: "You
1122       can't have everything -- where would you put it?"  So we have to place
1123       limits on how much we'll grow the tree.
1124
1125       There's more than one way to do this:
1126
1127       1. We could grow the tree until we hit some limit on the number of
1128       nodes we'll allow in the tree.
1129
1130       2. We could grow the tree until we hit some limit on the amount of time
1131       we're willing to spend.
1132
1133       3. Or we could grow the tree until it is fully fleshed out to a certain
1134       depth.
1135
1136       Since we already know to track depth (as we did in writing
1137       "dump_tree"), we'll do it that way, the third way.  The implementation
1138       for that third approach is also pretty straightforward:
1139
1140         $Max_depth = 3;
1141         sub grow {
1142           my $n = $_[0];
1143           my $depth = $_[1] ⎪⎪ 0;
1144           figure_successors($n)
1145            unless
1146             $depth >= $Max_depth
1147             or @{$n->{'successors'}}
1148             or $n->{'endgame'}
1149           }
1150           foreach my $s (@{$n->{'successors'}}) {
1151             grow($s, $depth + 1);
1152           }
1153           # If we're at $Max_depth, then figure_successors
1154           #  didn't get called, so there's no successors
1155           #  to recurse under -- that's what stops recursion.
1156         }
1157
1158       If we start from a single node (whether it's a node for the starting
1159       board "xxxx___oooo", or for whatever board the computer is faced with),
1160       set $Max_depth to 4, and apply "grow" to it, it will grow the tree to
1161       include several hundred nodes.
1162
1163           Footnote: If at each move there are four pieces that can move, and
1164           they can each move right or left, the "branching factor" of the
1165           tree is eight, giving a tree with 1 (depth 0) + 8 (depth 1) + 8 **
1166           2 + 8 ** 3 + 8 ** 4  = 4681 nodes in it.  But, in practice, not all
1167           pieces can move in both directions (none of the x pieces in
1168           "xxxx___oooo" can move left, for example), and there may be fewer
1169           than four pieces, if some were lost.  For example, there are 801
1170           nodes in a tree of depth four starting from "xxxx___oooo", suggest‐
1171           ing an average branching factor of about five (801 ** (1/4) is
1172           about 5.3), not eight.
1173
1174       What we need to derive from that tree is the information about what are
1175       the best moves for X.  The simplest way to consider the payoff of dif‐
1176       ferent successors is to just average them -- but what we average isn't
1177       always their immediate payoffs (because that'd leave us using only one
1178       generation of information), but the average payoff of their successors,
1179       if any.  We can formalize this as:
1180
1181         To figure a node's average payoff:
1182           If the node has successors:
1183             Figure each successor's average payoff.
1184             My average payoff is the average of theirs.
1185           Otherwise:
1186             My average payoff is my immediate payoff.
1187
1188       Since this involves recursing into the successors before doing anything
1189       with the current node, this will traverse the tree in post-order.
1190
1191       We could work that up as a routine of its own, and apply that to the
1192       tree after we've applied "grow" to it.  But since we'd never grow the
1193       tree without also figuring the average benefit, we might as well make
1194       that figuring part of the "grow" routine itself:
1195
1196         $Max_depth = 3;
1197         sub grow {
1198           my $n = $_[0];
1199           my $depth = $_[1] ⎪⎪ 0;
1200           figure_successors($n);
1201            unless
1202             $depth >= $Max_depth
1203             or @{$n->{'successors'}}
1204             or $n->{'endgame'}
1205           }
1206
1207           if(@{$n->{'successors'}}) {
1208             my $a_payoff_sum = 0;
1209             foreach my $s (@{$n->{'successors'}}) {
1210               grow($s, $depth + 1);  # RECURSE
1211               $a_payoff_sum += $s->{'average_payoff'};
1212             }
1213             $n->{'average_payoff'}
1214              = $a_payoff_sum / @{$n->{'successors'}};
1215           } else {
1216             $n->{'average_payoff'}
1217              = $n->{'last_move_payoff'};
1218           }
1219         }
1220
1221       So, by time "grow" has applied to a node (wherever in the tree it is),
1222       it will have figured successors if possible (which, in turn, sets
1223       "last_move_payoff" for each node it creates), and will have set "aver‐
1224       age_benefit".
1225
1226       Beyond this, all that's needed is to start the board out with a root
1227       note of "xxxx___oooo", and have the computer (X) take turns with the
1228       user (O) until someone wins.  Whenever it's O's turn, "Games::Alak"
1229       presents a prompt to the user, letting him know the state of the cur‐
1230       rent board, and asking what move he selects.  When it's X's turn, the
1231       computer grows the game tree as necessary (using just the "grow" rou‐
1232       tine from above), then selects the move with the highest average payoff
1233       (or one of the highest, in case of a tie).
1234
1235       In either case, "selecting" a move means just setting that move's node
1236       as the new root of the program's game tree.  Its sibling nodes and
1237       their descendants (the boards that didn't get selected) and its parent
1238       node will be erased from memory, since they will no longer be in use
1239       (as Perl can tell by the fact that nothing holds references to them
1240       anymore).
1241
1242       The interface code in "Games::Alak" (the code that prompts the user for
1243       his move) actually supports quite a few options besides just moving --
1244       including dumping the game tree to a specified depth (using a slightly
1245       fancier version of "dump_tree", above), resetting the game, changing
1246       $Max_depth in the middle of the game, and quitting the game.  Like
1247       "figure_successors", it's a bit too long to print here, but interested
1248       users are welcome to peruse (and freely modify) the code, as well as to
1249       enjoy just playing the game.
1250
1251       Now, in practice, there's more to game trees than this: for games with
1252       a larger branching factor than Alak has (which is most!), game trees of
1253       depth four or larger would contain too many nodes to be manageable,
1254       most of those nodes being strategically quite uninteresting for either
1255       player; dealing with game trees specifically is therefore a matter of
1256       recognizing uninteresting contingencies and not bothering to grow the
1257       tree under them.
1258
1259           Footnote: For example, to choose a straightforward case: if O has a
1260           choice between moves that put him in immediate danger of X winning
1261           and moves that don't, then O won't ever choose the dangerous moves
1262           (and if he does, the computer will know enough to end the game), so
1263           there's no point in growing the tree any further beneath those
1264           nodes.
1265
1266       But this sample implementation should illustrate the basics of how to
1267       build and manipulate a simple tree structure in memory.  And once
1268       you've understood the basics of tree storage here, you should be ready
1269       to better understand the complexities and peculiarities of other sys‐
1270       tems for creating, accessing, and changing trees, including
1271       Tree::DAG_Node, HTML::Element, XML::DOM, or related formalisms like
1272       XPath and XSL.
1273
1274       [end body of article]
1275
1276       [Author Credit]
1277
1278       Sean M. Burke ("sburke@cpan.org") is a tree-dwelling hominid.
1279
1280       References
1281
1282       Dewdney, A[lexander] K[eewatin].  1984.  Planiverse: Computer Contact
1283       with a Two-Dimensional World.  Poseidon Press, New York.
1284
1285       Knuth, Donald Ervin.  1997.  Art of Computer Programming, Volume 1,
1286       Third Edition: Fundamental Algorithms.  Addison-Wesley,  Reading, MA.
1287
1288       Wirth, Niklaus.  1976.  Algorithms + Data Structures = Programs Pren‐
1289       tice-Hall, Englewood Cliffs, NJ.
1290
1291       Worth, Stan and Allman Sheldon.  Circa 1967.  George of the Jungle
1292       theme.  [music by Jay Ward.]
1293
1294       Wirth's classic, currently and lamentably out of print, has a good sec‐
1295       tion on trees.  I find it clearer than Knuth's (if not quite as ency‐
1296       clopedic), probably because Wirth's example code is in a block-struc‐
1297       tured high-level language (basically Pascal), instead of in assembler
1298       (MIX).  I believe the book was re-issued in the 1980s under the titles
1299       Algorithms and Data Structures and, in a German edition, Algorithmen
1300       und Datenstrukturen.  Cheap copies of these editions should be avail‐
1301       able through used book services such as "abebooks.com".
1302
1303       Worth's classic, however, is available on the soundtrack to the 1997
1304       George of the Jungle movie, as performed by The Presidents of the
1305       United States of America.
1306

BACK

1308       Return to the HTML::Tree docs.
1309
1310
1311
1312perl v5.8.8                       2006-08-04         HTML::Tree::AboutTrees(3)
Impressum