A note on growing binary trees

The class ? of binary search trees is studied. A leaf is a vertex of degree 0; ?_n is the subset of ? consisting of trees with n leaves. We grow trees in ?_n from ?_n ? 1 thereby inducing a probability measure on ?_n. We will show that the expected value of the average leaf distance of t ∈ ?_n is asymptotic to log₂n as n → ∞.     

A note on the stack size of regularly distributed binary trees

Assume that in one unit of time a node is stored in the stack or is removed from the top of the stack during postorder-traversing of a binary tree. If all binary trees are equally likely the average stack size aftert units of time and the variance is computed as a function of the proportion=t/n.Part of this paper was presented at the 6th Colloquium on Automata, Languages and Programming, ICALP' 79, July 1979.     

A note on traversal algorithms for triply linked binary trees

Concise well-structured non-recursive algorithms for traversing triply linked binary trees in the three principal orders are presented and shown to be closely related.     

A note on circular dimension

In [1] Feinberg conjectures that the maximum circular dimension of all graphs having n vertices is attained by a complete partite graph. In this note we show that this is not so.     

A note on characteristic classes

This paper studies the relationship between the sections and the Chern or Pontrjagin classes of a vector bundle by the theory of connection. Our results are natural generalizations of the Gauss-Bonnet Theorem.     

A note on the dimension of a poset

It is shown that the dimension of a poset is the smallest cardinal number such that there is an embedding of the poset into a strict product of linear orders.     

A new genetic approach to construct near-optimal binary search trees

Many definitive and approximate methods have been so far proposed for the construction of an optimal binary search tree. One such method is the use of evolutionary algorithms with satisfactorily improved cost efficiencies. This paper will propose a new genetic algorithm for making a near-optimal binary search tree. In this algorithm, a new greedy method is used for the crossover of chromosomes while a new way is also developed for inducing mutation in them. Practical results show a rapid and desirable convergence towards the near-optimal solution. The use of a heuristic to create not so costly chromosomes as the first offspring, the greediness of the crossover, and the application of elitism in the selection of future generation chromosomes are the most important factors leading to near-optimal solutions by the algorithm at desirably high speeds. Due to the practical results, increasing problem size does not cause any considerable difference between the solution obtained from the algorithm and exact solution.     

A note on the Brouwer dimension of chainable spaces

A general method produces from a compact Hausdorff space S a compact Hausdorff space T with IndT=IndS+1. We show that if S is chainable, then T is also chainable while DgT<IndT, where Dg denotes dimensionsgrad, the dimension in the original sense of Brouwer. This leads to a chainable, first countable, separable space Xn with DgXn<IndXn=n for each integer n>1.     

A note on the dimension of an orbital subspace

This note contains a dimension formula for an orbital subspace in a symmetry class of tensors corresponding to an irreducible character λ of a subgroup G of S_m. An algorithm for choosing a basis is also described.