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

Kurt Mehlhorn | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

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

Author(s) -

Kurt Mehlhorn

Publication year - 1977

Publication title -

siam journal on computing

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 1.533

H-Index - 122

eISSN - 1095-7111

pISSN - 0097-5397

DOI - 10.1137/0206017

Subject(s) - combinatorics , mathematics , binary search tree , weight balanced tree , path length , path (computing) , binary tree , upper and lower bounds , binary number , entropy (arrow of time) , random binary tree , bounded function , discrete mathematics , computer science , arithmetic , computer network , mathematical analysis , physics , quantum mechanics , programming language

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

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research