A Best Possible Bound for The Weighted Path Length of Binary Search Trees

Publisher Website
Google Scholar
Abstract
The weighted path length of optimum binary search trees is bounded above by Y'./3i +2 a.+H whereH is the entropy of the frequency distribution, /3i is the total weight of the internal nodes, and aj is the total weight of the leaves. This bound is best possible. A linear time algorithm for constructing nearly optimal trees is described. One of the popular methods for retrieving information by its "name" is to store the names in a binary tree.We are given n names B1, Be, , Bn and 2n + 1 frequencies 1," ", fin, aO," ", an with /3i +Y aj 1. Here ji is the frequency of encountering name Bi, and aj is the frequency of encountering a name which lies between B and B/I, a0 and an have obvious interpretations (4). A binary search tree T for the names B1, B2, , Bn is a tree with n interior nodes (nodes havingtwo sons), whichwe denote by circles, and n + 1 leaves, which we denote by squares. The interior nodes are labeled with the B in increasing order from left to right and the leaves are labeled with the intervals (Bi, B//I) in increasing order from left to right. Let b be the distance of interior nodeB from the root and let aj be the distance of leaf (Bi, Bi/I) from the root. To retrieve a name X, bi + 1 comparisons are needed ifX B and ai comparisons are required if Bi <X< Bj/a. Therefore we define the weighted path length of tree T as:

This publication has 3 references indexed in Scilit: