Mathematical analysis of the average behavior of the AVL balanced tree insertion algorithm has not ever been done completely. As the first step toward this analysis, we have proposed an approximate analysis based on the assumption that all AVL balanced trees with a given number of nodes and height are constructed with equal probability. In this paper, we propose a new analysis of the AVL balanced tree insertion algorithm in conformity with that all n! permutations of n keys occur with equal probability. First we derive the formulae to enumerate the number of permutations constructing the AVL balanced trees with a given number of nodes and height. Then, we propose the formulae to evaluate the average behavior of the AVL balanced tree insertion algorithm and show some results from the proposed formulae.

We consider the optimal average cost of variable length source code averaged with a given probability distribution over source messages. The problem was argued in Csiszar and Korner's book. In a special case of binary alphabet, we find an upper bound to the optimal cost minus an ideal cost, where the ideal cost is the entropy of the source divided by a unique scalar that makes negative costs logarithmic probabilities. Our bound is better than the one given in the book.

Let U denote a set comprising elements called "keys." The goal of the nearest point problem is to search quickly for a key among some keys x1 , xn that is the nearest to a reference key x under a partial order relation defined as (x, y) (x, z) for x, y, zU if d(x, y)d(x, z) given a wide-sense distance measure d. This article proposes a method of rearranging x1 , xn into a binary perfectly-balanced tree for solving quickly the nearest point problems. Further, computational performances of the proposed method are evaluated experimentally.