| O（n）—时间有序树生成算法 |
| |
| 引用本文： | 姜学东.O（n）—时间有序树生成算法[J].四川大学学报(自然科学版),1993,30(2):176-183. |
| |
| 作者姓名： | 姜学东 |
| |
| 作者单位： | 四川大学国民经济管理系 |
| |
| 摘 要： | 以平面上长2π—2的简单、封闭随机行走为编码,构造了n结点有序树的顺序生成和随机生成算法.并证明顺序生成或随机生成任意一棵n结点有序树均是O(n)-时间的。对于有序树的生成来说,简单、封闭的随机行走是最有效的编码.
|
| 关 键 词： | 有序树 随机行走 随机生成 |
O(n) -TIME GENERATION ALGORITHMS FOR N -NODE ORDERED TREE |
| |
| Jiang Xuedong.O(n) -TIME GENERATION ALGORITHMS FOR N -NODE ORDERED TREE[J].Journal of Sichuan University (Natural Science Edition),1993,30(2):176-183. |
| |
| Authors: | Jiang Xuedong |
| |
| Institution: | Department of Management and Economy |
| |
| Abstract: | The simple closed random walks of length 2N - 2 are vised as codewords for the sequential and random generation of N -node trees. The sequential generation procedure generates each codeword in 0(1)- time average. Ranking and Unranking procedures are proved to be O(n)- time, 0(n)- space. It is clear that the random walk is one of the most efficient and practical kind of codewords. |
| |
| Keywords: | ordered trees random walks random generation |
| 本文献已被 CNKI 维普 等数据库收录！ |
