O(n)-时间有序树生成算法

O(n) -TIME GENERATION ALGORITHMS FOR N -NODE ORDERED TREE

以平面上长2π—2的简单、封闭随机行走为编码,构造了n结点有序树的顺序生成和随机生成算法.并证明顺序生成或随机生成任意一棵n结点有序树均是O(n)-时间的。对于有序树的生成来说,简单、封闭的随机行走是最有效的编码.

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.