Limit laws for sums of functions of subtrees of random binary search trees. (English) Zbl 1029.68076
Summary: We consider sums of functions of subtrees of a random binary search tree and obtain general laws of large numbers and central limit theorems. These sums correspond to random recurrences of the quicksort type, \(X_n {\overset{\mathcal L} =} X_{I_n} + X'_{n-1-I_n} + Y_n\), \(n \geq 1\), where \(I_{n}\) is uniformly distributed on \(\{0,1,..., n-1\}\), \(Y_{n}\) is a given random variable, \(X_k {\overset {\mathcal L}{=}} X'_k\) for all \(k\), and, given \(I_{n}\), \(X_{I_{n}}\) and \(X'_{n-1-I_{n}}\) are independent. Conditions are derived such that \((X_n - \mu n)/\sigma \sqrt{n} {\overset{\mathcal L} {\rightarrow}} {\mathcal N}(0,1)\), the normal distribution, for some finite constants \(\mu\) and \(\sigma\).
MSC:
68Q25 | Analysis of algorithms and problem complexity |
68P05 | Data structures |
60F05 | Central limit and other weak theorems |