Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Related Publications
(5)
On the Average Internal Path Length of m ary Search Trees
73] sorting and searching
Analysis of range search for random kd trees
Randomized Search Trees
Internal sorting methods illustrated with pl/1 programs
Subscribe
Academic
Publications
Some Combinatorial Properties of Certain Trees With Applications to Searching and Sorting
Some Combinatorial Properties of Certain Trees With Applications to Searching and Sorting,10.1145/321105.321108,Journal of The ACM,Thomas N. Hibbard
Edit
Some Combinatorial Properties of Certain Trees With Applications to Searching and Sorting
(
Citations: 65
)
BibTex

RIS

RefWorks
Download
Thomas N. Hibbard
Journal:
Journal of The ACM  JACM
, vol. 9, no. 1, pp. 1328, 1962
DOI:
10.1145/321105.321108
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
portal.acm.org
)
(
www.informatik.unitrier.de
)
(
portal.acm.org
)
(
portal.acm.org
)
(
doi.acm.org
)
More »
Citation Context
(25)
...The binary search tree (BST) [
16
] is one of the most fundamental sequential data structures, but comparatively little has been done towards providing nonblocking implementations of it. In the documentation for the ConcurrentSkipListMap class of the Java standard library [18], Lea wrote, “you might wonder why this [nonblocking dictionary implementation using skiplists] doesn’t use some kind of search tree instead, which...
Faith Ellen
,
et al.
Nonblocking binary search trees
...In 1962, Hibbard proposed a simple algorithm to dynamically delete an element from a binary tree [
10
]...
...Interestingly, for more than a decade it was subsequently believed that Hibbard’s theorem in fact proved that trees obtained through arbitrary sequences of random insertions and deletions are automatically random, i.e., have shapes whose distribution is the same as if the trees had been generated directly using random insertions only; see [
10
, 15]...
Axel Legay
,
et al.
On Automated Verification of Probabilistic Programs
...The solution is invariant in k. This is nothing but the expected number of comparisons used for an unsuccessful search in random binary search trees; see [6,
23
]...
Huahuai Chern
,
et al.
Partial Match Queries in Random kd Trees
...To derive an upper bound on·.n/, we use a famous result of Hibbard [
15
] (see [22])...
Micha Hofri
,
et al.
Efficient Reorganization of Binary Search Trees
...does not deal with deletions, and neither Hibbard's deletion algorithm [
4
] nor its multiple variants preserve randomness, a surprising fact that was first noticed by Knott [5]...
Salvador Roura
,
et al.
Randomization of Search Trees by Subtree Size
References
(9)
A highspeed sorting procedure
(
Citations: 14
)
R. M. Frank
,
R. B. Lazarus
Journal:
Communications of The ACM  CACM
, vol. 3, no. 1, pp. 2022, 1960
A highspeed sorting procedure
(
Citations: 71
)
Donald L. Shell
Journal:
Communications of The ACM  CACM
, vol. 2, no. 7, pp. 3032, 1959
Recursive Subscripting Compilers and ListTypes Memories
(
Citations: 3
)
John W. Carr III
Journal:
Communications of The ACM  CACM
, vol. 2, no. 2, pp. 46, 1959
Report on the algorithmic language ALGOL 60
(
Citations: 242
)
J. W. Backus
,
F. L. Bauer
,
J. Green
,
C. Katz
,
A. J. Perlis
,
H. Rutishauser
,
K. Samelson
,
B. Vauquois
,
J. H. Wegstein
,
A. van Wijngaarden
,
M. Woodger
Journal:
Communications of The ACM  CACM
, vol. 3, no. 5, pp. 299314, 1960
Radix Exchange—An Internal Sorting Method for Digital Computers
(
Citations: 10
)
Paul Hildebrandt
,
Harold Isbitz
Journal:
Journal of The ACM  JACM
, vol. 6, no. 2, pp. 156163, 1959
Sort by:
Citations
(65)
The total path length of split trees
Nicolas Broutin
,
Cecilia Holmgren
Journal:
Computing Research Repository  CORR
, vol. abs/1102.2, 2011
Nonblocking binary search trees
Faith Ellen
,
Panagiota Fatourou
,
Eric Ruppert
,
Franck van Breugel
Conference:
Symposium on Principles of Distributed Computing  PODC
, pp. 131140, 2010
Deletions in random binary search trees: A story of errors
Wolfgang Panny
Journal:
Journal of Statistical Planning and Inference  J STATIST PLAN INFER
, vol. 140, no. 8, pp. 23352345, 2010
Randomness Preserving Deletions on Special Binary Search Trees
(
Citations: 1
)
Michaela Heyer
Journal:
Electronic Notes in Theoretical Computer Science  ENTCS
, vol. 225, pp. 99113, 2009
On Automated Verification of Probabilistic Programs
(
Citations: 8
)
Axel Legay
,
Andrzej S. Murawski
,
Joël Ouaknine
,
James Worrell
Conference:
Tools and Algorithms for Construction and Analysis of Systems  TACAS
, pp. 173187, 2008