Aspects of insertion in random trees

Arunabha Bagchi, E.M. Reingold

    Research output: Contribution to journalArticleAcademic

    1 Citation (Scopus)
    78 Downloads (Pure)

    Abstract

    A method formulated by Yao and used by Brown has yielded bounds on the fraction of nodes with specified properties in trees bult by a sequence of random internal nodes in a random tree built by binary search and insertion, and show that in such a tree about bounds better than those now known. We then apply these methods to weight-balanced trees and to a type of “weakly balanced” trees. We determine the distribution of the weight-balance factors of the internal nodes in a random tree built by binary search and insertion and show that in such a tree about 72% of all internal nodes have weight balance factors lying between 1−2√/2 and 2√/2.
    Original languageUndefined
    Pages (from-to)11-29
    JournalComputing
    Volume29
    Issue number1
    DOIs
    Publication statusPublished - 1982

    Keywords

    • weight-balanced trees
    • height-balanced trees
    • IR-85717
    • 68E99
    • Binary search trees
    • 68C25
    • AVL trees

    Cite this