Empirical Performance Analysis of BST and AVL Tree on Modern Computing Architectures: A Stress Test Study Under Varying Data Distributions

Abstract

Binary Search Tree (BST) and AVL Tree are fundamental data structures widely used for dynamic data management in performance-critical systems. Although both structures offer efficient theoretical complexity, their practical performance on modern systems is highly influenced by data distribution and workload characteristics. This study presents an empirical performance evaluation of BST and AVL Tree using a stress-test approach based on a game leaderboard system as a representative case study. Multiple workload patterns were simulated, including random, sequential (ascending and descending), and clustered data distributions, to reflect realistic high-frequency updates commonly observed in modern applications. Experimental results show that BST achieves slightly better performance under random data distributions due to the absence of balancing overhead. However, BST experiences severe performance degradation under sequential inputs, where it degenerates into an unbalanced structure. In contrast, the AVL Tree consistently maintains logarithmic height, achieving speedups of up to 32x compared to BST in worst-case scenarios.These findings indicate that while BST can be effective under controlled average-case conditions, AVL Tree provides superior robustness and predictable performance under non-uniform and adversarial workloads. For modern high-load systems such as game leaderboards, the balancing overhead of AVL Tree represents a minimal trade-off compared to the substantial stability and performance guarantees it offers.