MPI-INF D1 Publications: Journal Article: A best possible bound for the weighted path length of binary search trees

Journal Article
@Article
Artikel in Fachzeitschrift

Show entries of:

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

Action:

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

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:	Theweighted path length of optimum binary search trees is boundedabove 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 forconstructing 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

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

Attachment Section

View attachments here:

Mehlhorn_a_1977_a.pdf