Comparative Performance of the AVL Tree to Three Variants of the Red-Black Tree

Autor:	Brown, Russell A.
Rok vydání:	2024
Předmět:	Computer Science - Data Structures and Algorithms
Druh dokumentu:	Working Paper
Popis:	The AVL and red-black trees are binary search trees that guarantee $ O\left( \log n \right ) $ insertion, deletion, and search. This guarantee requires rebalancing the trees, potentially for each insertion or deletion. Benchmarks demonstrate that, in many cases, the AVL tree is faster than three red-black tree variants for insertion and deletion, and as fast or faster for search. Comment: 17 pages, 9 figures
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2406.05162 Zobrazit plný text záznamu View this record from Arxiv