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

Some Combinatorial Properties of Certain Trees With Applications to Searching and Sorting   (Citations: 65)
BibTex | RIS | RefWorks Download
Journal: Journal of The ACM - JACM , vol. 9, no. 1, pp. 13-28, 1962
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.
    • ...The binary search tree (BST) [16] is one of the most fundamental sequential data structures, but comparatively little has been done towards providing non-blocking implementations of it. In the documentation for the ConcurrentSkipListMap class of the Java standard library [18], Lea wrote, “you might wonder why this [non-blocking dictionary implementation using skiplists] doesn’t use some kind of search tree instead, which...

    Faith Ellenet al. Non-blocking 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 Legayet 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]...

    Hua-huai Chernet al. Partial Match Queries in Random k-d Trees

    • ...To derive an upper bound on·.n/, we use a famous result of Hibbard [15] (see [22])...

    Micha Hofriet 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 Rouraet al. Randomization of Search Trees by Subtree Size

Sort by: