Comparative Empirical Analysis of Binary Search Trees, AVL Trees, and Red-Black Trees Under Varying Input Distributions

Key Points

• The aim is to empirically compare the performance of binary search trees, AVL trees, and red-black trees under different input conditions.
• Conducted empirical analysis with Python 3.11 implementations
• Assessed performance using rotation counts across various input distributions
• Tested with three datasets: NYC Taxi, Bitcoin OHLCV, and Apache logs
• Variations in input conditions included adversarial, random, and real-world scenarios
• Evaluated performance metrics at sizes ranging from N=100 to N=100,000
• AVL trees stabilized at a relative performance measure of 0.698 ± 0.003 under random input
• Red-black trees achieved a relative performance of 0.582 ± 0.003 under random input
• Real-world datasets demonstrated that semi-structured inputs align with random inputs
• Strictly ascending time-series data showcased characteristics of the adversarial case

Abstract