Some Combinatorial Properties of Certain Trees With Applications to Searching and Sorting

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Some Combinatorial Properties of Certain Trees With Applications to Searching and Sorting

Full text

Pdf (1.09 MB)

Source

Journal of the ACM (JACM) archive
Volume 9 , Issue 1 (January 1962) table of contents

Pages: 13 - 28

Year of Publication: 1962

ISSN:0004-5411

Author

Thomas N. Hibbard

System Development Corporation, Santa Monica, California

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 46, Citation Count: 34

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/321105.321108 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	HUFFMAN, D.A. A method for the construction of minimum redundancy codes. Proc. I.R.E. 40 (1952), 1098-1101.
	2	BURGh, W.H. Sorting, trees and measures of order. Informat. Contr. i (1958), 181-197.
	3	John W. Carr, III, Recursive subscripting compilers and list-type memories, Communications of the ACM, v.2 n.2, p.4-6, Feb. 1959 [doi>10.1145/368280.368281]
	4	NEWELL, A., AND SttAW, J.C. Programming the logic theory machine. Proc. Western Joint Comput. Conf. (1957), 230-240.
	5	D. L. Shell, A high-speed sorting procedure, Communications of the ACM, v.2 n.7, p.30-32, July 1959 [doi>10.1145/368370.368387]
	6	R. M. Frank , R. B. Lazarus, A high-speed sorting procedure, Communications of the ACM, v.3 n.1, p.20-22, Jan. 1960 [doi>10.1145/366947.366957]
	7	Paul Hildebrandt , Harold Isbitz, Radix Exchange—An Internal Sorting Method for Digital Computers, Journal of the ACM (JACM), v.6 n.2, p.156-163, April 1959 [doi>10.1145/320964.320972]
	8	Peter Naur , J. W. Backus , F. L. Bauer , J. Green , C. Katz , J. McCarthy , A. J. Perlis , H. Rutishauser , K. Samelson , B. Vauquois , J. H. Wegstein , A. van Wijngaarden , M. Woodger, Report on the algorithmic language ALGOL 60, Communications of the ACM, v.3 n.5, p.299-314, May 1960 [doi>10.1145/367236.367262]
	9	HOARE, C. A.R. Algorithms 63 and 64. Comm. ACM 4 (1961), 321.

CITED BY 34

	E. G. Coffman, Jr. , J. Eve, File structures using hashing functions, Communications of the ACM, v.13 n.7, p.427-432, July 1970
	W. D. Frazer , A. C. McKellar, Samplesort: A Sampling Approach to Minimal Storage Tree Sorting, Journal of the ACM (JACM), v.17 n.3, p.496-507, July 1970
	W. A. Walker , C. C. Gotlieb, Hybrid trees: A data structure for lists of keys, Proceedings of 1972 ACM-SIGFIDET workshop on Data description, access and control, p.189-211, January 1972
	William E. Wright, An empirical evaluation of algorithms for dynamically maintaining binary search trees, Proceedings of the ACM 1980 annual conference, p.505-515, January 1980
	G. Salton, Information science in a Ph.D. computer science program, Communications of the ACM, v.12 n.2, p.111-117, Feb. 1969
	Thomas N. Hibbard, An empirical study of minimal storage sorting, Communications of the ACM, v.6 n.5, p.206-213, May 1963
	R. S. Scowen, Algorithm 271: quickersort, Communications of the ACM, v.8 n.11, p.669-670, Nov. 1965
	Richard C. Singleton, Algorithm 347: an efficient algorithm for sorting with minimal storage [M1], Communications of the ACM, v.12 n.3, p.185-186, March 1969
	W. A. Martin, Sorting, ACM Computing Surveys (CSUR), v.3 n.4, p.147-174, Dec. 1971
	William E. Wright, Dynamic Binary Search Trees, Proceedings of the 1978 annual conference, p.370-374, December 04-06, 1978, Washington, D.C., United States
	J. Nievergelt , E. M. Reingold, Binary search trees of bounded balance, Proceedings of the fourth annual ACM symposium on Theory of computing, p.137-142, May 01-03, 1972, Denver, Colorado, United States
	Thomas N. Hibbard, A Simple Sorting Algorithm, Journal of the ACM (JACM), v.10 n.2, p.142-150, April 1963
	W. M. McKeeman, Algorithm 268: ALGOL 60 reference language editor [R2], Communications of the ACM, v.8 n.11, p.667-668, Nov. 1965
	C. K. Wong , J. Nievergelt, Upper Bounds for the Total Path Length of Binary Trees, Journal of the ACM (JACM), v.20 n.1, p.1-6, Jan. 1973
	H. Hurwitz, Jr., On the probability distribution of the values of binary trees, Communications of the ACM, v.14 n.2, p.99-102, Feb. 1971
	J. Nievergelt, Binary search trees and file organization, Proceedings of 1972 ACM-SIGFIDET workshop on Data description, access and control, p.165-187, January 1972
	P. Flajolet , J. Françon , J. Vuillemin, Computing integrated costs of sequences of operations with application to dictionaries, Proceedings of the eleventh annual ACM symposium on Theory of computing, p.49-61, April 30-May 02, 1979, Atlanta, Georgia, United States
	K. Hwang , S. B. Yao, Optimal Batched Searching of Tree Structured Files in Multiprocessor Computer Systems, Journal of the ACM (JACM), v.24 n.3, p.441-454, July 1977
	J. Morris, ACM Algorithm 346: F-Test Probabilities, Communications of the ACM, v.12 n.3, p.184-185, March 1969
	Jeffrey L. Eppinger, An empirical study of insertion and deletion in binary search trees, Communications of the ACM, v.26 n.9, p.663-669, Sept. 1983
	J C Culberson, The effect of updates in binary search trees, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.205-212, May 06-08, 1985, Providence, Rhode Island, United States
	Gary D. Knott, A balanced tree storage and retrieval algorithm, Proceedings of the 1971 international ACM SIGIR conference on Information storage and retrieval, April 01-02, 1971, College Park, Maryland
	H. Lynn Beus, The Use of Information in Sorting, Journal of the ACM (JACM), v.17 n.3, p.482-495, July 1970
	E. M. Palmer , M. A. Rahimi , R. W. Robinson, Efficiency of a Binary Comparison Storage Technique, Journal of the ACM (JACM), v.21 n.3, p.376-384, July 1974
	Dennis G. Severance, Identifier Search Mechanisms: A Survey and Generalized Model, ACM Computing Surveys (CSUR), v.6 n.3, p.175-194, Sept. 1974
	Stephen Taylor , Marianne Durand, Emerging behavior as binary search trees are symmetrically updated, Theoretical Computer Science, v.297 n.1-3, p.425-445, 17 March 2003
	J. Nievergelt, Binary Search Trees and File Organization, ACM Computing Surveys (CSUR), v.6 n.3, p.195-207, Sept. 1974
	Jaroslav Pfann , Josef Straka, Algorithm 269: determinant evaluation [F3], Communications of the ACM, v.8 n.11, p.668, Nov. 1965
	Conrado Martínez , Salvador Roura, Randomized binary search trees, Journal of the ACM (JACM), v.45 n.2, p.288-323, March 1998
	Amr Elmasry, Deterministic jumplists, Nordic Journal of Computing, v.12 n.1, p.27-39, March 2005
	Jing-Chao Chen, Efficient sample sort and the average case analysis or PEsort, Theoretical Computer Science, v.369 n.1, p.44-66, 15 December 2006
	Arnold F. Goodman, Measurement of computer systems: an introduction, Proceedings of the December 5-7, 1972, fall joint computer conference, part II, December 05-07, 1972, Anaheim, California
	Michaela Heyer, Randomness Preserving Deletions on Special Binary Search Trees, Electronic Notes in Theoretical Computer Science (ENTCS), 225, p.99-113, January, 2009
	W. D. Frazer, Analysis of combinatory algorithms: a sample of current methodology, Proceedings of the November 16-18, 1971, fall joint computer conference, November 16-18, 1971, Las Vegas, Nevada