Random Split Trees
Devroye & Kruszewski (1996) generate random binary trees with n nodes by generating a real-valued random variable x in the unit interval (0,1), assigning the first xn nodes (rounded down to an integer number of nodes) to the left subtree, the next node to the root, and the remaining nodes to the right subtree, and continuing recursively in each subtree. If x is chosen uniformly at random in the interval, the result is the same as the random binary search tree generated by a random permutation of the nodes, as any node is equally likely to be chosen as root; however, this formulation allows other distributions to be used instead. For instance, in the uniformly random binary tree model, once a root is fixed each of its two subtrees must also be uniformly random, so the uniformly random model may also be generated by a different choice of distribution for x. As Devroye and Kruszewski show, by choosing a beta distribution on x and by using an appropriate choice of shape to draw each of the branches, the mathematical trees generated by this process can be used to create realistic-looking botanical trees.
Read more about this topic: Random Binary Tree
Famous quotes containing the words random, split and/or trees:
“It is a secret from nobody that the famous random event is most likely to arise from those parts of the world where the old adage “There is no alternative to victory” retains a high degree of plausibility.”
—Hannah Arendt (1906–1975)
“Pleasure is the rock which most young people split upon; they launch out with crowded sails in quest of it, but without a compass to direct their course, or reason sufficient to steer the vessel; for want of which, pain and shame, instead of pleasure, are the returns of their voyage.”
—Philip Dormer Stanhope, 4th Earl Chesterfield (1694–1773)
“Why are there trees I never walk under but large and melodious thoughts descend upon me?”
—Walt Whitman (1819–1892)