A Random Binary Trees Generation Method

Abstract

There are two widely used random distributions on binary trees, namely the binary search tree distribution and the uniform distribution. By analyzing the performance of algorithms that manipulate binary trees generated at random, it is possible to assess the average case performance of the algorithm. This average case performance is often a more useful reflection of the algorithm's suitability than the worst-case performance. An algorithm may have a worst-case run time that is of exponential time complexity, but an average-case run time that is of polynomial time complexity. In such cases, one wishes to assess the performance of an algorithm on a 'typical' range of tree structures and thus relate properties of randomly generated trees, such as depth, to aspects affecting the algorithm's run-time. The purpose of this paper is to design and implement a random binary trees generation algorithm that considers the average case performance. The algorithm is differ from both the uniform distribution and the binary search tree distribution. Analysis of the behaviour of the algorithm is given.