臺灣博碩士論文加值系統

有許多研究致力於兩棵ｎ個點二元樹的轉換距離，即是否能在多項式的時間內利用一般的旋轉計算出兩棵二元樹轉換的距離，這個問題仍是一個待解決的開放問題。我們提出一些新形式的旋轉，這些旋轉只在二元樹左臂和右臂上的點作旋轉。對於二元樹的轉換，在左臂上做左旋和右旋及右臂上做右旋和左旋能提供快速且有效的轉換，我們改進轉換任意兩棵ｎ點二元樹之演算法，且能在至多(n-1)的時間來轉換兩棵ｎ點二元樹的左權重序列和右權重序列。特別的是對一序列的旋轉以合計方法分析之，每一旋轉能在一常數攤還時間完成。除了ｎ點二元樹的轉換距離之外，利用左臂上左旋和右旋及右臂上右旋和左旋，可以建構出所有ｎ點二元樹之間的旋轉圖Gn，利用在右臂上左旋，從Gn我們可以建構出一棵特殊的旋轉樹Tn，當走訪此旋轉樹Tn時，我們可以辭彙編纂的方式列舉出所有ｎ點二元樹的左權重序列，也就是列舉出所有ｎ點二元樹。

我們對ｎ個點多元樹用一簡單的右距離序列表示之，其和 Zaks 所提出的Z序列存在著密切關係。運用多元遞迴樹及其伴隨關係表使我們在ｎ點多元樹作有系統的研究。因此，在辭彙編纂方式下，決定一ｎ點多元樹的排列次序及在轉換一正整數為其相對應的ｎ點多元樹，我們皆有效地改進次序演算法及反次序演算法。這兩演算法毋需建立任何關係表皆能在O(tn)時間內被執行完。

此外，利用右距離序列表示，我們也提出一無迴圈演算法可以列舉所有ｎ點多元樹，此一無迴圈演算法只需要3n+O(1)記憶空間並且比現存的演算法更有效率。由於它在右距離序列所表示的Gray-code圖上列舉所有ｎ點多元樹過程就是哈密爾敦路徑。最後，我們在右距離序列所表示的Gray-code圖上找到了哈密爾敦迴路。

We consider a transformation on binary trees using new types of rotations. Each of the newly proposed rotations is permitted only at nodes on the left-arm or the right-arm of a tree. Consequently, we develop a linear time algorithm with at most n - 1 rotations for converting weight sequences between any two binary trees. In particular, from an analysis of aggregate method for a sequence of rotations, each rotation of the proposed algorithm can be performed in a constant amortized time. Next, we show that a specific directed rooted tree called rotation tree can be constructed using one of the new type rotations. As a by-product, a naive algorithm for enumerating weight sequences of binary trees in lexicographic order can be implemented by traversing the rotation tree.
Then, we use a concise representation, called right distance sequences (or RD-sequences for short), to describe all t-ary trees with n internal nodes. A result reveals that there exists a close relationship between the representation and the well-formated sequences suggested by Zaks [Theoret. Comput. Sci.
10 (1980) 63-82]. Using a t-ary recursion tree and its concomitant tables, a systematical way can help us to investigate the structural representation of t-ary trees. Consequently, we develop efficient algorithms for determining the rank of a given t-ary tree in lexicographic order (i.e., the ranking algorithm), and for converting a positive integer to its corresponding RD-sequence (i.e., the unranking algorithm). Both the ranking and unranking algorithms can be run in O(tn) time and without really building any auxiliary table.
In addition, we also present a loopless algorithm to enumerate Gray-codes of t-ary trees using RD-sequences. The proposed algorithm requires 3n+O(1) memory space and is more efficient than all the existing algorithms. Because it fits a Hamiltonian path P in RDtn, we find that there exists a Hamiltonian
cycle in RDtn.

Contents
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Rotation Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Enumerating, Ranking and Unranking Problems . . . . . . . . . . . . . . . . . 5
1.4 Loopless Generating t-ary Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.5 Organization of this Dissertation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2 Tree Rotation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 LeftWeight Sequences and RightWeight Sequences . . . . . . . .. . . . . . . 11
2.3 Left-arm and Right-arm Rotations . . . . . . . . . . . . . . . . . .. . . . . . . . . 15
2.4 A Tree Transformation Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.5 An Improved Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .23
3 Enumerations of Binary Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .26
3.1 A-order, B-order and Related Representations . . . . . . . . . . . . . . . . . 26
3.2 Enumerated Sequences of Binary Trees . . . . . . . . . . . . . . . . . . . . . . . 38
3.3 Enumerate Binary Trees by Using the Rotation Tree . . . . . . . . . . . . . .39
4 Ranking and Unranking of t-ary Trees . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.2 Structural Representations of t-ary Trees . . . . . . . . . . . . . . . . . . . . . 44
4.3 A Ranking Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .55
4.4 An Unranking Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.5 Enumerate Sequences of t-ary Trees. . . . . . . . . . . . . . . . . . . . . . . . . 58
5 A Loopless Algorithm to Generate Gray-codes of t-ary Trees . . . . . .. . 61
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
5.2 RD-representation Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .63
5.3 Loopless Gray-code Generation for t-ary Trees. . . . . . . . . . . . . . . . . 67
5.4 Hamiltonian RD-representation Graphs . . . . . . . . . . . . . . . . . . . . . . .73
6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .77
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .81

List of Tables
3.1 A-order and B-order definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.2 left weight sequence and left distance sequence . . . . . . . . . . . . . . . . 37
4.1 The 3-ary recursion table for n = 6 . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.2 The 3-ary accumulation table for n = 6 . . . . . . . . . . . . . . . . . . . . . . . 52
5.1 A summary of loopless algorithms for generating sequences of
binary trees and t-ary trees with n internal nodes . . . . . . . . . . . . . . . . . . .63
5.2 The RD-representation graph RD3n for all n-node 3-ary trees . . . . . .66
6.1 The diameter and the average rotation distance for various types
of rotation graph Gn with n = 3, 4, 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

List of Figures
1.1 The corresponding representations including triangulations of a 5-gon,
the ways to parenthesize the product x1x2x3x4, 3-node binary trees,
3-pair balanced parentheses strings, and all X-sequences of 3-node
binary trees. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 A left or right rotation at node x. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4
2.1 The LW-sequence and the RW-sequence of a tree T. . . . . . . . . . . . . . . 12
2.2 The left-arm and right-arm rotations. . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.3 An example of tree transformation. . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.1 Three binary trees. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .27
3.2 A 9-node binary tree and its X-sequence. . . . . . . . . . . . . . . . . . . . . . . 28
3.3 The X-sequences of all 4-node binary trees. . . . . . . . . . . . . . . . . . . . . 29
3.4 The Z-sequences and Y -sequences of all 4-node binary trees. . . . . . . 29
3.5 The P-sequences and level sequences of all 4-node binary trees. . . . . .30
3.6 The permutations of all 4-node binary trees. . . . . . . . . . . . . . . . . . . . . 31
3.7 The inversion tables of all 4-node binary trees. . . . . . . . . . . . . . . . . . . 32
3.8 The left weight sequences and L-sequences of all 4-node binary trees. 33
3.9 The tree permutations and A-sequences of all 4-node binary trees. . . . 34
3.10 The node number sequences of all 4-node binary trees. . . . . . . . . . . . 34
3.11 The inorder left weight sequences and left distance sequences of
all 4-node binary trees. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .35
3.12 The rotation tree T4 whose nodes in each level are labeled in
lexicographic order. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.1 The 3-ary trees with 3 internal nodes. . . . . . . . . . . . . . . . . . . . . . . .. . . 45
4.2 A 4-ary tree T such that every internal node i 2 T is labeled by di/zi . . .46
4.3 The recursion tree, RD-sequences, Z-sequences, and the rank of 3-ary trees .48
4.4 The label for each node corresponds to the number of leaves in the
subtree rooted at the node of 3-ary recursion tree. . . . . . . . . . . . . . . . . . . 49
4.5 The sum of labels corresponded by the path (d1, d2, d3) is
Rank(d1, d2, d3) in the 3-ary recursion tree (n = 3) . . . . . . . . . . . . . . . . . . 54
5.1 A trinary recursion tree and a Gray-code graph RD33 . . . . . . . . . . . . . .64
5.2 A trinary recursion tree and a Gray-code graph Z33 . . . . . . . . . . . . . . . 67
5.3 A Hamiltonian path in the graph RD34 . . . . . . . . . . . . . . . . . . . . . . . . . 68
5.4 A listing of RD-sequences for 3-ary trees with 4 internal nodes
in Gray-code order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .69
5.5 The flowchart of procedure NextRD() . . . . . . . . . . . . . . . . . . . . . . . . . . 71
5.6 A binary recursion tree, a corresponding Hamiltonian path and
a Hamiltonian cycle in RD25 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .75
5.7 A trinary recursion tree, two corresponding paths P1 and P2 and
a Hamiltonian cycle in RD34. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

References
[1] G. M. Adel’son-Vel’ski?i and E. M. Landis, An algorithm for organization of information,
Soviet Mathematics Doklady 3 (1962) 1259–1263.
[2] H. Ahrabian and A. Nowzari-Dalini, On the generation of binary trees in A-order,
International Journal of Computer Mathematics 71 (1999) 351–357.
[3] H. Ahrabian and A. Nowzari-Dalini, Generation of t-ary trees with Ballot-sequences,
International Journal of Computer Mathematics 80 (2003) 1243–1249.
[4] H. Ahrabian, A. Nowzari-Dalini, and E. Salehi, Gray code algorithm for listing k-ary
trees, Studies in Informatics and Control 13 (2004) 243–251.
[5] H. Ahrabian and A. Nowzari-Dalini, Adaptive generation of t-ary trees in parallel,
The Electronic International Journal Advanced Modeling and Optimization 8 (2006) 19–28.
[6] S. G. Akl and I. Stojmenovi?c, Generating t-ary trees in parallel, Nordic Journal of
Computing 3 (1996) 63–71.
[7] A. Andersson, General balanced trees, Journal of Algorithms 30 (1999) 1–18.
[8] V. Bapiraju and V.V.B. Rao, Enumeration of binary trees Information Processing
Letters 51 (1994) 125-127.
[9] R. Bayer, Symmetric binary B-trees: data structure and maintenance algorithms,
Acta Informatica 1 (1972) 290–306.
[10] M. K. Bennet and G. Birkhoff, Two families of Newman lattices, Algebra Universalis
32 (1994) 115–144.
[11] A. Bonnin and J. Pallo, A shortest path metric on unlabeled binary Trees, Pattern
Recognition Letters 13 (1992) 411–415.
[12] Yen-Ju Chen, Jou-Ming Chang, and Yue-LiWang, An efficient algorithm for estimating
rotation distance between two binary trees, International Journal of Computer
Mathematics 82 (2005) 1095-1106.
[13] S. Cleary, Restricted rotation distance between binary trees, Information Processing
Letters 84 (2002) 333–338.
[14] S. Cleary and J. Taback, Bounding restricted rotation distance, Information Processing
Letters 88 (2003) 251–256.
[15] K. Culik and D. Wood, A note on some tree similarity measures, Information Processing
Letters 15 (1982) 39–42.
[16] B. Effantin, Generation of valid labelled binary trees, Proceedings of the 2003 International
Conference on Computational Science and Its Applications (ICCSA’2003),
Lecture Notes in Computer Science (LNCS) 2667, 2003, pp. 245-253.
[17] G. Ehrlich, Loopless algorithms for generating permutations, combination, and other
combinatorial configurations, Journal of the ACM 20 (1973) 500–513.
[18] M. C. Er, Efficient generation of k-ary trees in natural order, The Computer Journal
35 (1992) 306–308.
[19] A. Gibbons and P. Sant, Rotation sequences and edge-colouring of binary tree pairs,
Theoretical Computer Science 326 (2004) 409–418.
[20] L. Guibas and J. Hershberger, Morphing simple polygons, Proceedings of the ACM
10th Annual Symposium of Computational Geometry (SCG’94), 1994, pp. 267-276.
[21] J. Hershberger and S. Suri, Morphing binary trees, Proc. ACM-SIAM 6th Annual
Symposium of Discrete Algorithms (SODA’95), 1995, pp. 396-404.
[22] F. Hurtado and M. Noy, Graph of triangulations of a convex polygon and tree of
triangulations, Computational Geometry 13 (1999) 179–188.
[23] D. A. Klarner, Correspondences between plane trees and binary sequences, Journal
of Combinatorial Theory 9 (1970) pp. 401–411.
[24] G. D. Knott, A numbering system for binary trees, Communications of ACM 20 (2),
(1977), 113-115.
[25] D. E. Knuth, The Art of Computer Programming. Vol. 1: Fundamental Algorithms,
Addison-Wesley, Reading, MA, 1968.
[26] D. E. Knuth, Sorting and Searching, in: The Art of Computer Programming, Vol. 3,
Addison-Wesley, Reading, MA, 1973.
[27] Z. Kokosi?nski, On parallel generation of t-ary trees in an associative model, in: Proc.
of 4th International Conference on Parallel Processing and Applied Mathematics
(PPAM 2001), LNCS 2328, Springer, 2002, pp. 228–235.
[28] Z. Kokosi?nski, A parallel dynamic programming algorithm for unranking t-ary treesl,
in: Proc. of 5th International Conference on Parallel Processing and Applied Mathematics
(PPAM 2003), LNCS 3019, Springer, 2004, pp. 255–260.
[29] J. F. Korsh, Loopless generation of k-ary tree sequences, Information Processing
Letters 52 (1994) 243–247.
[30] J. F. Korsh and S. Lipschutz, Shifts and loopless generation of k-ary trees, Information
Processing Letters 65 (1998) 235–240.
[31] J. F. Korsh and P. LaFollette, Loopless generation of Gray code for k-ary trees,
Information Processing Letters 70 (1999) 7–11.
[32] J. F. Korsh, Generating t-ary trees in linked representation, The Computer Journal
48 (2005) 488–497.
[33] J.M. Lucas, The rotation graph of binary trees is Hamiltonian, Journal of Algorithms
8 (1987) 503–535.
[34] J. M. Lucas, D. Roelants van Baronaigien, and F. Ruskey, On rotations and the
generation of binary trees, Journal of Algorithms 15 (1993) 343–366.
[35] J. M. Lucas, A direct algorithm for restricted rotation distance, Information Processing
Letters 90 (2004) 129–134.
[36] J. M. Lucas, Untangling binary trees via rotations, The Computer Journal 47 (2004)
259–269.
[37] F. Luccio and L. Pagli, On the upper bound on the rotation distance of binary trees,
Information Processing Letters 31 (1989) 57–60.
[38] E. M?akinen, Left distance binary tree representations, BIT 27 (1987) 163–169.
[39] E. M?akinen, On the rotation distance of binary trees, Information Processing Letters
26 (1987/88) 271–272.
[40] E. M?akinen, Generating random binary trees – A survey, Information Sciences 115
(1999) 123-136.
[41] H. W. Martin and B. J. Orr, A random binary tree generator, in: Proc. of the 17th
conference on ACM Annual Computer Science Conference, Louisville, Kentucky,
February 21-23, 1989, pp. 33-38.
[42] J. Pallo and R. Racca, A note on generating binary trees in A-order and B-order,
Intern. J. Computer Math. 18 (1985) 27–39.
[43] J. Pallo, Enumerating, ranking and unranking binary trees, The Computer Journal
29 (1986) 171–175.
[44] J. Pallo, On the rotation distance in the lattice of binary trees, Information Processing
Letters 25 (1987) 369–373.
[45] J. Pallo, Some properties of the rotation lattice of binary trees, The Computer Journal
31 (1988) 564–565.
[46] J. Pallo, An efficient upper bound of the rotation distance of binary trees, Information
Processing Letters 73 (2000) 87–92.
[47] J. Pallo, Right-arm rotation distance between binary trees, Information Processing
Letters 87 (2003) 173–177.
[48] J. Pallo, Rotational tree structures on binary trees, Proc. 11th International Conference
on Automata and Formal Languages (AFL’05), Dobogoko, Hungary, May 17-20, pp. 263–274.
[49] A. Proskurowski, On the generating of binary trees, Journal of the ACM 27 (1980) 1–2.
[50] A. Proskurowski and F. Ruskey, Binary tree gray codes, Journal of Algorithms 6
(1985) 225–238.
[51] D. Roelants van Baronaigien and F. Ruskey, Generating t-ary trees in A-order,
Information Processing Letters 27 (1988) 205–213.
[52] D. Roelants van Baronaigien, A loopless algorithm for generating binary tree sequences,
Inform. Process. Lett. 39 (1991) 189194.
[53] D. Roelants van Baronaigien, A loopless Gray-code algorithm for listing k-ary trees,
Journal of Algorithms 35 (2000) 100–107.
[54] R. O. Rogers and R. D. Dutton, Properties of the rotation graph of binary trees,
Congressus Numerantium 109 (1995) 51–63.
[55] R. O. Rogers and R. D. Dutton, On distance in the rotation graph of binary trees,
Congressus Numerantium 120 (1996) 103–113.
[56] R. O. Rogers, On finding shortest paths in the rotation graph of binary trees, Congressus
Numerantium 137 (1999) 77–95.
[57] D. Rotem, On a correspondence between binary trees and a certain type of permutation,
Information Processing Letters 4 (1975) 58–61.
[58] F. Ruskey and T. C. Hu, Generating binary trees lexicographically, SIAM Journal
on Computing 6 (1977) 745–758.
[59] F. Ruskey, Generating t-ary trees lexicographically, SIAM Journal on Computing 7
(1978) 424–439.
[60] F. Ruskey and A. Proskurowski, Generating binary trees by transpositions, Journal
of Algorithms 11 (1990) 68–84.
[61] C. D. Savage, A survey of combinatorial Gray codes, SIAM Review 39 (1997) 605–629.
[62] I. Semba, Generation of all the balanced Parenthesis strings in lexicographical order,
Information Processing Letters 12 (1981) 188–192.
[63] D. D. Sleator and R. E. Tarjan, Self-adjusting binary search trees, Journal of the
ACM 32 (1985) 652–686.
[64] D. D. Sleator, R. E. Tarjan, and W. R. Thurston, Rotation distance, triangulations and
hyperbolic geometry, Journal of the American Mathematical Society 1 (1988)647–681.
[65] N. J. A. Sloane, Sequence A009766 in ”The On-Line Encyclopedia of Integer Sequences.”
[66] M. Solomon and R.A. Finkel, A note on enumerating binary trees, J. ACM 27 (1980) 3-5.
[67] R. Sundar, On the deque conjecture for the splay algorithm, Combinatorica 12 (1992) 95–124.
[68] T. Takaoka, O(1) time algorithms for combinatorial generation by tree traversal, The
Computer Journal 42 (1999) 400–408.
[69] A. E. Trojanowaki, Ranking and listing algorithms for k-ary trees, SIAM Journal
on Computing 7 (1978) 492–509.
[70] V. Vajnovszki, C. Phillips, Optimal parallel algorithm for generating k-ary trees, in:
Proc. of the 12th International Conference on Computers and Their Applications,
Tempe, Arizona, (ed. M. C. Woodfill), March 13-15, 1997, pp. 201–204
[71] V. Vajnovszki, On the loopless generation of binary tree sequences, Information
Processing Letters 68 (1998) 113–117.
[72] V. Vajnovszki and C. Phillips, Systolic generation of k-ary trees, Parallel Processing
Letters 9 (1999), 93–101.
[73] V. Vajnovszki, Generating a Gray code for P-sequences, Journal of Mathematical
Modelling and Algorithms 1 (2002) 31–41.
[74] S. G. Williamson, Combinatorics for Computer Science, Computer Science Press,
Rockville, MD, 1985.
[75] L. Xiang, K. Ushijima, and S. G. Akl, Generating regular k-ary trees efficiently, The
Computer Journal 43 (2000) 290–300.
[76] L. Xiang, K. Ushijima, and C. Tang, Efficient loopless generation of Gray codes for
k-ary trees, Information Processing Letters 76 (2000) 169–174.
[77] L. Xiang and K. Ushijima, On O(1) time algorithms for combinatorial generation,
The Computer Journal 44 (2001) 292–302.
[78] L. Xiang, K. Ushijima, and C. Tang, On generating k-ary trees in computer representation,
Information Processing Letters 77 (2001) 231–238.
[79] L. Xiang, K. Ushijima, and Y. Asahiro, Coding k-ary trees for efficient loopless generation
in lexicographic order, in: Proc. of International conference on Information
Technology: Coding and Computing (ITCC’02), IEEE Computer Society Press, Las
Vegas, April 8-10, 2002, pp. 396–401.
[80] Ro-Yu Wu, Jou-Ming Chang, Yue-Li Wang, A linear time algorithm for binary
tree sequences transformation using left-arm and right-arm rotations, Theoretical
Computer Science 355(3) (2006) 303-314.
[81] S. Zaks, Lexicographic generation of ordered trees, Theoretical Computer Science 10
(1980) 63–82.
[82] S. Zaks, Generation and ranking of k-ary trees, Information Processing Letters 14 (1982) 44–48.
[83] D. Zerling, Generating binary trees using rotations, Journal of Association for Computing
Machinery 32 (1985) 694–701.