Bounds and Algorithms for Alphabetic Codes and Binary Search Trees
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866917730988326912 |
|---|---|
| author | Bruno, Roberto De Prisco, Roberto De Santis, Alfredo Vaccaro, Ugo |
| author_facet | Bruno, Roberto De Prisco, Roberto De Santis, Alfredo Vaccaro, Ugo |
| contents | Alphabetic codes and binary search trees are combinatorial structures that abstract search procedures in ordered sets endowed with probability distributions. In this paper, we design new linear-time algorithms to construct alphabetic codes, and we show that the obtained codes are not too far from being optimal. Moreover, we exploit our results on alphabetic codes to provide new bounds on the average cost of optimal binary search trees. Our results improve on the best-known bounds on the average cost of optimal binary search trees present in the literature. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_16443 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Bounds and Algorithms for Alphabetic Codes and Binary Search Trees Bruno, Roberto De Prisco, Roberto De Santis, Alfredo Vaccaro, Ugo Information Theory Data Structures and Algorithms Alphabetic codes and binary search trees are combinatorial structures that abstract search procedures in ordered sets endowed with probability distributions. In this paper, we design new linear-time algorithms to construct alphabetic codes, and we show that the obtained codes are not too far from being optimal. Moreover, we exploit our results on alphabetic codes to provide new bounds on the average cost of optimal binary search trees. Our results improve on the best-known bounds on the average cost of optimal binary search trees present in the literature. |
| title | Bounds and Algorithms for Alphabetic Codes and Binary Search Trees |
| topic | Information Theory Data Structures and Algorithms |
| url | https://arxiv.org/abs/2407.16443 |