More Combinatorial Properties of Certain Trees | Zendy

W. C. Lynch | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

More Combinatorial Properties of Certain Trees

Author(s) -

W. C. Lynch

Publication year - 1965

Publication title -

the computer journal

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.319

H-Index - 64

eISSN - 1460-2067

pISSN - 0010-4620

DOI - 10.1093/comjnl/7.4.299

Subject(s) - mathematics , variance (accounting) , combinatorics , generating function , tree (set theory) , relation (database) , statistics , binary number , function (biology) , binary tree , computer science , arithmetic , data mining , biology , accounting , evolutionary biology , business

A detailed examination of binary search trees reveals that the probability of making precisely i comparisons in placing the (n—l)th item in the tree is related to the (n—i)th symmetric function of the integers 1, . . . , n. A recurrence relation for the moments of this distribution of comparisons is derived, and formulas for the mean number of comparisons and its variance are displayed. These are shown to be in accord with previously published values.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research