Premium
On the joint distribution of the nodes in uniform multidimensional binary trees
Author(s) -
Kemp Rainer
Publication year - 1998
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/(sici)1098-2418(199810/12)13:3/4<261::aid-rsa5>3.0.co;2-t
Subject(s) - binary number , binary tree , dimension (graph theory) , distribution (mathematics) , tree (set theory) , joint probability distribution , mathematics , random binary tree , set (abstract data type) , joint (building) , combinatorics , struct , uniform distribution (continuous) , computer science , discrete mathematics , statistics , mathematical analysis , arithmetic , architectural engineering , engineering , programming language
Multidimensional binary trees represent a symbiosis of trees and tries, and they essentially arise in the construction of search trees for multidimensional keys. The set of nodes in a d ‐dimensional binary tree can be partitioned into layers according to the nodes appearing in the ith dimension. We determine the exact distribution of the number of nodes with zero, one, and two sons in a specified layer and show that jointly the three types of nodes asymptotically have a trivariate normal distribution in each layer. That trivariate normal distribution is completely characterized. © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 13: 261–283, 1998