Breakage and restoration in recursive trees
Uniform sequential tree-building aggregation of n particles is analyzed together with the effect of the avalanche that takes place when a subtree rooted at a uniformly chosen vertex is removed. For large n, the expected subtree size is found to be ≃ log n both for the tree of size n and the tree tha...
Guardado en:
| Publicado: |
2002
|
|---|---|
| Materias: | |
| Acceso en línea: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00219002_v39_n2_p383_Tetzlaff http://hdl.handle.net/20.500.12110/paper_00219002_v39_n2_p383_Tetzlaff |
| Aporte de: |
| Sumario: | Uniform sequential tree-building aggregation of n particles is analyzed together with the effect of the avalanche that takes place when a subtree rooted at a uniformly chosen vertex is removed. For large n, the expected subtree size is found to be ≃ log n both for the tree of size n and the tree that remains after an avalanche. Repeated breakage-restoration cycles are seen to give independent avalanches which attain size k (1 ≤ k ≤ n - 1) with probability (k(k + 1))-1 and restored trees that are recursive. |
|---|