On optimal trees

Eades P. and Staples J. (1981) On optimal trees. Journal of Algorithms, 2 4: 369-384. doi:10.1016/0196-6774(81)90035-3

Author Eades P.
Staples J.
Title On optimal trees
Journal name Journal of Algorithms   Check publisher's open access policy
ISSN 0196-6774
Publication date 1981-01-01
Sub-type Article (original research)
DOI 10.1016/0196-6774(81)90035-3
Volume 2
Issue 4
Start page 369
End page 384
Total pages 16
Language eng
Subject 1703 Computational Theory and Mathematics
2605 Computational Mathematics
Abstract The merits of different shapes of trees as data storage structures are compared. Given a tree data structure, the worst-case cost of searching the tree is studied, under weak assumptions about the cost of searches. In particular, it is assumed that the cost of a search path is the sum of the costs of the nodes on it, and that the cost of a node depends only on the outdegree of that node. The main results of the paper are that there are regular trees (as defined in the paper) which are nearly optimal among trees with a given number of nodes, and that minimal-cost trees are often nearly regular.
Q-Index Code C1
Institutional Status Unknown

Document type: Journal Article
Sub-type: Article (original research)
Collection: Scopus Import
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 1 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 1 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Tue, 06 Sep 2016, 10:59:32 EST by System User