LOWER BOUNDS TO THE EXTERNAL PATHLENGTH OF A LOPSIDED BINARY TREE

Binary search trees with costs α and β on the left and right edges (lopsided binary search trees) are important in the construction of optimum prefix codes. In this paper we derive lower bounds for the external pathlengths of lopsided binary trees. It is found that the lower bound is tight if the cost difference (the difference in maximum cost and the minimum cost) is small but quite sharp when the cost difference is large. We suggest alternative ways to construct the lopsided binary tree when the cost difference is high to improve the lower bound.