WWW.DISSERTATION.XLIBX.INFO FREE ELECTRONIC LIBRARY - Dissertations, online materials

<< HOME
CONTACTS

Pages:   || 2 | 3 |

# «Abstract We build upon the previous work on the subset of permutations known as stack words and stack-sortable words. We use preorder, inorder and ...»

-- [ Page 1 ] --

Tree Traversals and Permutations

Todd Feil, Kevin Hutson, R. Matthew Kretchmar

Abstract

We build upon the previous work on the subset of permutations

known as stack words and stack-sortable words. We use preorder,

inorder and postorder traversals of binary trees to establish multiple

bijections between binary trees and these words. We show these

operators satisfy a sort of multiplicative cancellation. We further

expand the study of these operators by demonstrating how properties

on trees are related to properties on words.

1 Introduction Knuth [9] considered permutations created by using a stack. Consider pass- ing the sequence 1, 2, 3,..., n through a single stack by means of a series of pushes and pops, where a push will push the next number in the input string and a pop removes the top of the stack to the output string, with the proviso that the stack empties after all integers have been pushed. For example, if n = 4, then the sequence, push, push, pop, push, pop, push, pop, pop, would result in the permutation (2341). (Our convention is to represent the permutation π with the sequence π(1), π(2),..., π(n). Thus, if π = (2341) then π(1) = 2, π(2) = 3, and so on.) Figure 1 shows midway through the creation of the permutation (2341).

It is easy to see that a permutation obtained in this way is a 312-avoiding permutation (For example, see Grimaldi [7].); that is, a permutation π(1), π(2),..., π(n) for which there is no i j k where π(j) π(k) π(i). A permutation π obtained in this manner is called a stack word. For example, the permutation π = (25134) is not 312-avoiding since π(2) = 5, π(4) = 3 and π(5) = 4.

Likewise, a permutation that can be sorted using a stack in the man- ner described is called a stack-sortable word. These are precisely the 231- avoiding permutations; that is, a permutation π for which there is no i j k where π(k) π(i) π(j).

output input output input 1234 2 4 3 1 initial state after push, push, pop, push Figure 1: Creating a stack word Recently, there has been interest in stack words, restricted permuta- tions, stack-sortable words, and their extensions. (See [1], [2], [3], [4], [8], [9], [10], [14], [16], [17], and [18].) Several have related these restricted permutations to various structures, for example, stacks. While bijections between stack words (or stack-sortable words) and binary trees have been given previously (see [4], [6], [15], and especially [9], [12], and [13]), we give additional bijections in which the structure of the tree reﬂects the stack operations in a straightforward manner.

These stack and stack-sortable words can be produced by applying various traversals of binary trees. This idea has been used by [9], [12], [13], and [4]. In eﬀect, we are modeling stack operations with these traversals.

We apply the three common binary tree traversal algorithms of preorder, inorder and postorder to ﬁrst label the tree, then read the labels. The order the labels are read gives us a permutation. That is, for a given binary tree T, we pick a labeling traversal from preorder, inorder and postorder traversals. We then pick a reading traversal from among these three options.

Thus, we produce a permutation by:

1. Labeling the nodes of T with 1, 2,..., n using the chosen labeling traversal.

2. Reading the labels from the nodes of T produced in step (1) using the reading traversal.

Note for a given binary tree T, each choice of labeling and reading traversal produces a potentially diﬀerent permutation of 1, 2,..., n. Obviously, if the labeling and reading traversals are the same, the resultant permutation is the identity permutation. If a permutation is obtained from a binary tree by labeling with a preorder traversal and reading with an inorder traversal, we’ll call it a PreIn permutation. Permutations obtained by this process using diﬀerent labeling and reading traversals will be similarly named.

2 In Section 2 we show a bijection between stack words and binary trees which are labeled using an inorder traversal and read using a postorder traversal. That is, we can convert stack words to trees and vice versa.

Section 3 shows how an inorder labeling and a preorder reading produces stack-sortable words. Furthermore, we can produce stack words and stack sortable words with two other label/read traversals.

Section 5 reveals an interesting “canceling” feature of these traversal operators when they are composed. The preorder labeled and postorder read permutations possess some properties not present in the other stack words; these are discussed in Section 6.

We can use a combination of operators to convert from a binary tree to a stack word and then back to another (diﬀerent) binary tree. If we repeat this process, we create a series of trees (and their intervening stack words). This process creates cycles that partition the set of stack words.

We develop an equivalence relation in Section 7.

2 Stack Words, Stack-sortable Words and Binary Trees Notice that the sequence of pushes and pops necessary to produce a stack word (or sort a stack-sortable word) can be conveniently given by a sequence of n pairs of parentheses, where a left parenthesis corresponds to a push and a right parenthesis corresponds to a pop. (This was observed by West [16].) For example, the sequence of pushes and pops producing (2341) can be expressed as (()()()). If you label the parentheses pairs starting at 1, then reading oﬀ the label of the right parentheses will give the corresponding stack word. In our example (1 (2 )2 (3 )3 (4 )4 )1 yields 2341. This establishes a bijection between the set of stack words of length n and the set of n pairs of parentheses.

If π is a stack word, that is, a 312-avoiding permutation of {1, 2,..., n}, then clearly π −1 is a stack-sortable word; that is, a 231-avoiding permutation. Furthermore, the sequence of parentheses (sequence of pushes and pops) that sorts π −1 is precisely the sequence of parentheses that creates π. Thus, the stack word we obtained above, 2341 corresponds to the stacksortable word 4123, which is sorted by the sequence of stack operations given by (()()()).

Now consider binary trees. We describe a bijection between binary trees with n nodes and sequences of n pairs of parentheses. There are many such bijections, of course. For example, see [4] and [6]. The one we give has 3 the advantage of naturally extending to stack words and stack-sortable words. We do this recursively. The empty tree corresponds to zero pairs of parentheses; that is, the empty sequence. A tree of one node corresponds to the sequence (). A tree with more than one node corresponds to the sequence L(R), where L is the sequence of parentheses corresponding to the tree rooted at the left child of the root node and R is the sequence of parentheses corresponding to the tree rooted at the right child of the root node. Some examples are given in Figure 2.

()(()) ()()(()((()))) ((()(()))) Figure 2: Binary trees and nested parentheses The stack word associated with a binary tree T with n vertices can also be realized by labeling the vertices of T with 1, 2,..., n using an inorder traversal and then reading the labels using a postorder traversal. Call such a word an inorder labeled, postorder read word for the tree T and denote the permutation by [In : P ost]T. (This idea is similar to that given in [4].) We formalize this in the following proposition.

Proposition 1 There is a bijection between the inorder labeled, postorder read words and stack words.

Proof: Since stack words are precisely the 312-avoiding permutations, we show that a word is inorder labeled, postorder read if and only if it is 312avoiding. In a binary tree, we’ll say a is a right descendant of b if the node labeled a is in the subtree rooted at the right child of the node labeled b.

Left descendant is similarly deﬁned.

Suppose π is a permutation with a 312 subsequence. Hence there exist i, j, k where i j k with π(j) π(k) π(i). Now if π(j) π(i) on an inordered labeled tree, then one of the three situations hold: (1) π(i) is a right descendant of π(j), (2) π(j) is a left descendant of π(i), or (3) there is some node x where π(i) is a right descendant of x and π(j) is a left descendant of x. These three situations are pictured in Figure 3.

–  –  –

But if i j in the postorder output, only situation (1) can hold. Now, restricting our attention to the situation (1), if π(j) π(k) π(i) either (a) π(k) is a right descendant of π(j) and π(i) is a right descendant of π(k), or (b) π(k) is a left descendant of π(i). These are pictured in Figure 4.

–  –  –

But in postorder output, (a) yields the order π(i), π(k), π(j) and (b) yields π(k), π(i), π(j). In either case, this is not the order desired (π(i), π(j), π(k)). Thus, there is no binary tree T where [In : P ost]T = π.

Now suppose π is a 312-avoiding permutation. We construct the binary tree that is inorder labeled, postorder read that yields π. Since we have a postorder read, label the root node π(n) (the last number in the permutation). Due to the inorder labeling, the right subtree of π(n) will be all nodes labeled π(k) with π(k) π(n) and the left subtree of π(n) will be all nodes labeled π(j) where π(j) π(n). Let L = {π(j) : π(j) π(n)} and R = {π(k) : π(k) π(n)}. We claim that if π(j) ∈ L and π(k) ∈ R, then j k. That is π(j) comes before π(k) in the permutation π. For otherwise we have k j n and π(j) π(n) π(j), which is a 312 subsequence.

We now apply this construction recursively to L and R. Note a postorder reading of the tree will output L, then R, and then π(n). 2 Given the bijection between binary trees and nested parentheses noted before this proposition, one can see there is also a bijection between nested

–  –  –

Note that if [In : P ost]T = π and we label the nodes of the same binary tree T inorder with the labels π −1, then a postorder reading of the nodes will yield the nodes in sorted order 1, 2,..., n. We observed this phenomenon before when we noted that the same stack operations sort π −1 as create π.

One can realize π −1 by labeling the nodes of the InPost tree of π with 1, 2,..., n using a postorder labeling and reading the labels in an inorder traversal. (Similar to our previous notation, we’ll denote such a permutation by [P ost : In]T.) We illustrate with the InPost tree of π = (23154) in Figure 6.

–  –  –

This is true since if we label the InPost tree of π using a postorder labeling, then the label π(i) in the original labeling is replaced by i in the new labeling for each i. Thus each i in the original inorder labeling will be replaced by π −1 (i). Now reading the new labels using an inorder traversal will produce labels in the order π −1 (1),π −1 (2),π −1 (3),..., π −1 (n).

6 3 Stack-sortable Words and Preorder Traversals In light of the above proposition, it is natural to ask what is the permutation that results from an inorder labeled, preorder read tree. Adopting notation

similar to above, we denote a permutation obtained in this way by [In :

P re]T. The following proposition answers this, which has been noted in section 2.3.1, exercise 6 of [9] and further exploited in [13] and [12].

Proposition 2 There is a bijection between the inorder labeled, preorder read words and stack-sortable words.

Proof: The proof is similar to the proof of Proposition 1, noting that stacksortable words are precisely those 231-avoiding permutations. When showing that a 231-avoiding permutation, ρ, can be realized as an inorder labeled, preorder read tree, we label the root with ρ(1), the leftmost number of the permutation, and note that all ρ(j) with ρ(j) ρ(1) come before all ρ(k) with ρ(k) ρ(1). As before, we construct the tree recursively. 2 In Figure 7 we illustrate by constructing the inorder labeled, preorder read tree for the stack-sortable word (31254). The reader should note that the tree constructed in this manner does not reﬂect the stack operations necessary to sort the stack-sortable word in a straightforward way. Indeed, the tree structures look very diﬀerent; compare the trees in Figures 6 and

7. Furthermore, if ρ is a stack-sortable word and T is the binary tree so that ρ = [In : P re]T, then the permutation [P re : In]T will be the stack word ρ−1. (See Corollary 1 in Section 5.)

–  –  –

The conversion of a stack word to a preorder labeled, inorder read tree will be used in following sections and so we will illustrate how this tree is constructed directly from the stack word. ([13] and [12] give a similar construction for InPre trees from stack-sortable words.) Note that since T will be preorder labeled, the root node must be labeled with 1. Those values 7 in the stack word to the left of 1 will comprise the left subtree while those to the right of 1 will comprise the right subtree. We apply this technique recursively to each subtree, labeling the root with the smallest number in the subtree. We illustrate this conversion on the stack word (23154) in Figure 8.

–  –  –

If π is a stack word, we call the binary tree T such that [P re : In]T = π the PreIn tree of π.

4 Counting Permutations that are both Stack Words and Stack-sortable Words Rotem [12] counted the number of permutations on {1, 2,..., n} that are both stack words and stack-sortable words, but his proof was diﬃcult and required advanced graph theory techniques and terminology such as interval and permutation graphs. The characterization of stack words on {1, 2,..., n} as a permutation [P re : In]T for some binary tree T with n nodes, as noted in the last section, allows us to perform this count easily.

Since a stack word that is also stack-sortable is a stack word that is 231avoiding, we need only characterize those trees T where [P re : In]T have a 231 subsequence. We then will be able to count the remaining trees with n nodes.

Note that [P re : In]T has a 231 subsequence if and only if there is a left elbow subtree (as shown in Figure 9) in T. The proof of this follows along lines similar to the proof of Proposition 1 and will not be included here.

Pages:   || 2 | 3 |

Similar works:

«A/68/255–S/2013/463 Nations Unies Assemblée générale Distr. générale 2 août 2013 Conseil de sécurité Français Original : anglais Assemblée générale Conseil de sécurité Soixante-huitième session Soixante-huitième année Point 74 de l’ordre du jour provisoire* Rapport du Tribunal international chargé de juger les personnes accusées de violations graves du droit international humanitaire commises sur le territoire de l’ex-Yougoslavie depuis 1991 Rapport du Tribunal pénal...»

«WORKING BIBLIOGRAPHY ON LANGUAGES OF SPATIAL RELATIONS First Edition Compiled by David M. Mark, Michael D. Gould, and Scott M. Freundschuh NCGIA, Department of Geography, State University of New York at Buffalo Max J. Egenhofer and Werner Kuhn NCGIA, Department of Surveying Engineering, University of Maine Matthew McGranaghan Department of Geography, University of Hawaii at Manoa and Soteria Svorou 2323 Van Ness, Apt #202, San Francisco, California National Center for Geographic Information and...»

«SOME REMARKS ON THE ISOPERIMETRIC PROBLEM FOR THE HIGHER EIGENVALUES OF THE ROBIN AND WENTZELL LAPLACIANS J. B. KENNEDY School of Mathematics and Statistics, University of Sydney, NSW 2006, Australia J.Kennedy@maths.usyd.edu.au Abstract. We consider the problem of minimising the kth eigenvalue, k ≥ 2, of the (p-)Laplacian with Robin boundary conditions with respect to all domains in RN of given volume M. When k = 2, we prove that the second eigenvalue of the p-Laplacian is minimised by the...»

«BOARD OF SELECTPERSON’S MEETING PUBLIC HEARING FOR ORDINANCES AND CHARTER AMENDMENTS February 25, 2016 6:00 p.m. Rumford Falls Auditorium PRESENT: Chairperson Bradford Adley, Vice-Chairperson Jeffrey Sterling, Selectperson Frank DiConzo, Selectperson Mark Belanger, Selectperson Michael Peter Chase, Town Manager John Madigan, Jr. ATTENDEES: Bromley Cook 1. Meeting Call to Order by Chairperson Adley at 6:10 p.m. 2. Pledge of Allegiance to the American Flag 3. Approval of Charter Amendment...»

«ADDITIONAL INFORMATION 2016 on CRM Archaeology Field School Central Washington University Updated February 2, 2016 Eligibility The field school is open to anyone eligible to register for college credits (whether college students are not), and may be audited by those not wanting college credit. There are no pre-requisites, but some background in archaeology is strongly encouraged. Schedule The field school will meet weekdays from June 13 through August 5, 2016. It is possible to take the full...»

«Standard Eurobarometer European Commission EUROBAROMETER 63.4 PUBLIC OPINION IN THE EUROPEAN UNION SPRING 2005 NATIONAL REPORT Standard Eurobarometer 63.4 / Spring 2005 – TNS Opinion & Social EXECUTIVE SUMMARY HUNGARY The survey was requested and coordinated by the Directorate General Press and Communication. This report was produced for the European Commission’s Representation in Hungary. This document does not represent the point of view of the European Commission. The interpretations and...»

«Eagle, N., and Pentland, A., Reality Mining: Sensing Complex Social Systems', J. of Personal and Ubiquitous Computing. To appear: June 2005. Reality Mining: Sensing Complex Social Systems Nathan Eagle and Alex (Sandy) Pentland MIT Media Laboratory 20 Ames St. Cambridge, MA 02139 {nathan, sandy}@media.mit.edu Abstract. We introduce a system for sensing complex social systems with data collected from one hundred mobile phones over the course of six months. We demonstrate the ability to use...»

«STRONGLY NONCOSINGULAR MODULES A Thesis Submitted to the Graduate School of Engineering and Sciences of ˙ Izmir Institute of Technology in Partial Fulﬁllment of the Requirements for the Degree of MASTER OF SCIENCE in Mathematics by Yusuf Alag¨ z o July 2014 ˙ ˙ IZMIR We approve the thesis of Yusuf Alag¨ z o Examining Committee Members: ¨¨ Assoc. Prof. Dr. Engin BUYUKASIK ¸ ˙ Department of Mathematics, Izmir Institute of Technology Assist. Prof. Dr. Basak AY SAYLAM ¸ Department of...»

«TABLE OF CONTENTS MINISTERING TO CHILDREN OF DIVORCE /Table of Contents Practical Ministry Skills: Ministering to Children of Divorce Leader’s Guide NO SUCH THING AS A “GOOD DIVORCE” by Amy O’Brien MINISTERING TO PART-TIME KIDS by Brian Dykes AS IF THEY NEVER EXISTED by Amy O’Brien COMMON EMOTIONS AND REACTIONS by Wayne Stocks FAITH THROUGH THE LENSE OF DIVORCE interview with Elizabeth Marquardt A PROGRAM THAT MEETS THEIR NEEDS by Amy O’Brien Resources FURTHER EXPLORATION From...»

«GOLD COAST IS NOT ONLY ALL THAT GLITTERS UNDERSTANDING VISITOR AND RESIDENT PERCEPTIONS OF THE GOLD COAST Abstract Utilising the case study of the Gold Coast Australia, this paper aims to discuss city identity and the role of branding in the formation of the city image and explore whether residents and tourists perceive identity of a city differently. The paper views place identity from the perspective of modern practices of place marketing and branding rather than experiential self-identity....»

«EnterText 6.1 FELICIA CHAN Wuxia Cross-dressing and Transgender Identity: The Roles of Brigitte Lin Ching-hsia from Swordsman II to Ashes of Time The act of cross-dressing in the theatrical and cinematic traditions has been consistently employed as a method of transgressing and thus exploring the limits of the boundaries in gender but also in identity and selfhood. In some cases, these transgressions were a response to prevailing institutional, cultural and social restrictions of the day. This...»

«Auctions for Salesforce Installation & Configuration Guide Version 4.1 June 2, 2013 abs@.org.org Djhconsulting.com 1 CONTENTS 1. Overview 2. Installation Instructions 2.1 Upgrading an Existing Installation of Auctions 2.2 Installing Auctions for the First Time 2.3 Requirements Before Installing 2.4 Installation Steps 2.5 Requirements After Installing 3. Feature Configuration 3.1 Custom Settings 3.2 Non Profit Starter Pack Considerations 3.3 Periodic Auction Setting Adjustments 4. Customizing...»

<<  HOME   |    CONTACTS
2016 www.dissertation.xlibx.info - Dissertations, online materials

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.