Grandchildren-weight-balanced binary search trees
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908432934633472 |
|---|---|
| author | Jugé, Vincent |
| author_facet | Jugé, Vincent |
| contents | We revisit weight-balanced trees, also known as trees of bounded balance. This class of binary search trees was invented by Nievergelt and Reingold in 1972. Such trees are obtained by assigning a weight to each node and requesting that the weight of each node should be quite larger than the weights of its children, the precise meaning of ``quite larger'' depending on a real-valued parameter~$γ$. Blum and Mehlhorn then showed how to maintain these trees in a recursive (bottom-up) fashion when~$2/11 \leqslant γ\leqslant 1-1/\sqrt{2}$, their algorithm requiring only an amortised constant number of tree rebalancing operations per update (insertion or deletion). Later, in 1993, Lai and Wood proposed a top-down procedure for updating these trees when~$2/11 \leqslant γ\leqslant 1/4$.
Our contribution is two-fold. First, we strengthen the requirements of Nievergelt and Reingold, by also requesting that each node should have a substantially larger weight than its grand-children, thereby obtaining what we call grand-children balanced trees. Grand-children balanced trees are not harder to maintain than weight-balanced trees, but enjoy a smaller node depth, both in the worst case (with a 6~\% decrease) and on average (with a 1.6~\% decrease). In particular, unlike standard weight-balanced trees, all grand-children balanced trees with $n$ nodes are of height less than $2 \log_2(n)$.
Second, we adapt the algorithm of Lai and Wood to all weight-balanced trees, i.e., to all parameter values~$γ$ such that~$2/11 \leqslant γ\leqslant 1-1/\sqrt{2}$. More precisely, we adapt it to all grand-children balanced trees for which~$1/4 < γ\leqslant 1 - 1/\sqrt{2}$. Finally, we show that, except in critical cases, all these algorithms result in making a constant amortised number of tree rebalancing operations per tree update. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_08825 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Grandchildren-weight-balanced binary search trees Jugé, Vincent Data Structures and Algorithms We revisit weight-balanced trees, also known as trees of bounded balance. This class of binary search trees was invented by Nievergelt and Reingold in 1972. Such trees are obtained by assigning a weight to each node and requesting that the weight of each node should be quite larger than the weights of its children, the precise meaning of ``quite larger'' depending on a real-valued parameter~$γ$. Blum and Mehlhorn then showed how to maintain these trees in a recursive (bottom-up) fashion when~$2/11 \leqslant γ\leqslant 1-1/\sqrt{2}$, their algorithm requiring only an amortised constant number of tree rebalancing operations per update (insertion or deletion). Later, in 1993, Lai and Wood proposed a top-down procedure for updating these trees when~$2/11 \leqslant γ\leqslant 1/4$. Our contribution is two-fold. First, we strengthen the requirements of Nievergelt and Reingold, by also requesting that each node should have a substantially larger weight than its grand-children, thereby obtaining what we call grand-children balanced trees. Grand-children balanced trees are not harder to maintain than weight-balanced trees, but enjoy a smaller node depth, both in the worst case (with a 6~\% decrease) and on average (with a 1.6~\% decrease). In particular, unlike standard weight-balanced trees, all grand-children balanced trees with $n$ nodes are of height less than $2 \log_2(n)$. Second, we adapt the algorithm of Lai and Wood to all weight-balanced trees, i.e., to all parameter values~$γ$ such that~$2/11 \leqslant γ\leqslant 1-1/\sqrt{2}$. More precisely, we adapt it to all grand-children balanced trees for which~$1/4 < γ\leqslant 1 - 1/\sqrt{2}$. Finally, we show that, except in critical cases, all these algorithms result in making a constant amortised number of tree rebalancing operations per tree update. |
| title | Grandchildren-weight-balanced binary search trees |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2410.08825 |