OPTIMAL INSERTION IN 2-DIMENSIONAL ARRAYS

An algorithm for finding binary insertion trees for MxN two-dimensiona l arrays from one-dimensional optimal insertion trees is proposed. New theorems that apply to the one-dimensional optimal insertion trees ar e presented, and a bound on the cost of two-dimensional binary inserti on trees is found. The proposed algorithm uses a fast O(n log n) algor ithm on (M+N+2) one-dimensional arrays and the results of the presente d theorems to determine the root of the two-dimensional insertion tree . The algorithm is repeated successively on each of the two resulting two-dimensional arrays to determine the left and right subtrees. The a lgorithm is easy to implement and yields optimal trees for some specia l two-dimensional arrays and close to optimal trees for arbitrary arra ys. (C) Elsevier Science Inc. 1997.