Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








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


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

Publisher's
Name:

SIAM

Publisher's URL:


Publisher's
Address:

Philadelphie, PA, USA

ISSN:


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, Abstract, ©

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},
ADDRESS = {Philadelphie, PA, USA},
}


Entry last modified by Anja Becker, 03/06/2008
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Christine Kiesel
Created
03/30/2006 03:10:54 PM
Revisions
4.
3.
2.
1.
0.
Editor(s)
Anja Becker
Christine Kiesel
Christine Kiesel
Christine Kiesel
Christine Kiesel
Edit Dates
06.03.2008 09:07:52
04.01.2007 15:16:09
04.01.2007 15:13:50
08.08.2006 14:25:42
30.03.2006 15:12:29
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section
Mehlhorn_a_1977_a.pdf
View attachments here: