Journal Article @Article Artikel in Fachzeitschrift
 Show entries of: this year (2020) | last year (2019) | two years ago (2018) | Notes URL
 Action: login to update Options: Goto entry point

 Author, Editor(s)
 Author(s): Mehlhorn, Kurt dblp
 BibTeX cite key*: Mehlhorn77a

 Title
 Title*: A best possible bound for the weighted path length of binary search trees Attachment(s): Mehlhorn_a_1977_a.pdf (362.75 KB)

 Journal
 Journal Title*: SIAM Journal on Computing Journal's URL: Download URL for the article: http://locus.siam.org/fulltext/SICOMP/volume-06/0206017.pdf http://scitation.aip.org/getpdf/servlet/GetPDFServlet?filetype=pdf&id=SMJCAT000006000002000235000001&idtype=cvips&prog=normal Language: English

 Publisher

 Vol, No, pp, Date
 Volume*: 6 Number: 2 Publishing Date: 1977 Pages*: 235-239 Number of VG Pages: Page Start: Page End: Sequence Number: DOI:

 Note: (LaTeX) Abstract: The weighted path length of optimum binary search trees is bounded above by $\sum \beta_i + 2\sum \alpha_j + H$ where $H$ is the entropy of the frequency distribution, $\sum \beta _i$ is the total weight of the internal nodes, and $\sum \alpha_j$ is the total weight of the leaves. This bound is best possible. A linear time algorithm for constructing nearly optimal trees is described. URL for the Abstract: http://scitation.aip.org/getabs/servlet/GetabsServlet?prog=normal&id=SMJCAT000006000002000235000001&idtype=cvips&gifs=yes Categories, Keywords: binary search tree, complexity, average search time, entropy HyperLinks / References / URLs: Copyright Message: Personal Comments: Download Access Level: Public

 Correlation
 MPG Unit: Max-Planck-Institut für Informatik MPG Subunit: Algorithms and Complexity Group Audience: Expert Appearance: MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:

@ARTICLE{Mehlhorn77a,
AUTHOR = {Mehlhorn, Kurt},
TITLE = {A best possible bound for the weighted path length of binary search trees},
JOURNAL = {SIAM Journal on Computing},
PUBLISHER = {SIAM},
YEAR = {1977},
NUMBER = {2},
VOLUME = {6},
PAGES = {235--239},