Name
Abstract | ||
|---|---|---|
In this paper some properties of (a,b)-trees are studied. Such trees are a generalization of B-trees and therefore their performances are dependent upon their height. Hence it is important to be able to enumerate the (a,b)-trees of a given height. To this purpose, a recurrence relation is defined which cannot be solved by the usual techniques. Therefore some limitations are established to the number of (a,b)-trees of a given height and an approximate formula is given which shows that the sequence of such numbers is a doubly exponential one. As a consequence of this fact, some properties, as for instance the probability that the height grows by the effects of an insertion, are studied using profiles. The proofs are given of how profiles are generated and how from a profile one can get the number of corresponding (a,b)-trees. |
Year | DOI | Venue |
|---|---|---|
1989 | 10.1007/3-540-51859-2_13 | Optimal Algorithms |
Keywords | Field | DocType |
recurrence relation | Discrete mathematics,Exponential function,Computer science,Recurrence relation,Mathematical proof | Conference |
Volume | ISSN | ISBN |
401 | 0302-9743 | 3-540-51859-2 |
Citations | PageRank | References |
0 | 0.34 | 5 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Renzo Sprugnoli | 1 | 295 | 128.45 |
| Elena Barcucci | 2 | 306 | 59.66 |
| Alessandra Chiuderi | 3 | 17 | 20.50 |
| Renzo Pinzani | 4 | 341 | 67.45 |