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

This paper presents an empirical comparison of Binary Search Trees, AVL Trees, and Red-Black Trees across adversarial, random, and real-world input conditions at 25 logarithmically-spaced sizes from N=100 to N=100,000. All results are from executed Python 3.11 implementations with directly measured rotation counts. Central finding: AVL R/N stabilizes at 0.698 ± 0.003 and RBT R/N at 0.582 ± 0.003 under random input, validated by 30 independent trials. Three real-world datasets (NYC Taxi, Bitcoin OHLCV, Apache logs) confirm semi-structured inputs mirror the random baseline, while strictly ascending time-series data reproduces the adversarial case.