Comparative Performance of the AVL Tree and Three Variants of the Red-Black Tree
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915427364372480 |
|---|---|
| author | Brown, Russell A. |
| author_facet | Brown, Russell A. |
| contents | This article compares the performance of the AVL tree to the performance of the bottom-up, top-down, and left-leaning red-black trees. The bottom-up red-black tree is faster than the AVL tree for insertion and deletion of randomly ordered keys. The AVL tree is faster than the bottom-up red-black tree for insertion but slower for deletion of consecutively ordered keys. The top-down red-black tree is faster than the bottom-up red-black tree for insertion but slower for deletion of randomly ordered keys, and slower for insertion and deletion of consecutively ordered keys. The left-leaning red-black tree is slower than the three other trees for insertion and deletion of randomly and consecutively ordered keys. An alternative deletion algorithm, which reduces the number of rebalancing operations required by deletion, is analyzed. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_05162 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Comparative Performance of the AVL Tree and Three Variants of the Red-Black Tree Brown, Russell A. Data Structures and Algorithms This article compares the performance of the AVL tree to the performance of the bottom-up, top-down, and left-leaning red-black trees. The bottom-up red-black tree is faster than the AVL tree for insertion and deletion of randomly ordered keys. The AVL tree is faster than the bottom-up red-black tree for insertion but slower for deletion of consecutively ordered keys. The top-down red-black tree is faster than the bottom-up red-black tree for insertion but slower for deletion of randomly ordered keys, and slower for insertion and deletion of consecutively ordered keys. The left-leaning red-black tree is slower than the three other trees for insertion and deletion of randomly and consecutively ordered keys. An alternative deletion algorithm, which reduces the number of rebalancing operations required by deletion, is analyzed. |
| title | Comparative Performance of the AVL Tree and Three Variants of the Red-Black Tree |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2406.05162 |