COMPARATIVE EXPERIMENTAL ANALYSIS OF METHODS FOR IMPLEMENTING THE AVL TREE

Анотація

The paper presents an experimental proof of the difference between two computational models of AVL trees: the classical online balanced AVL tree and the canonical median tree constructed on the basis of a sorted array of keys. Despite close asymptotic estimates of the complexity of search, insertion, and deletion operations, these implementations of AVL trees demonstrate fundamentally different behavior in practice. The study analyzes the impact of balancing strategy, tree shape, and search operation implementation method on the performance of search, key insertion, and deletion operations, as well as AVL tree creation. It is shown that using binary search on a sorted array of keys in a canonical AVL tree significantly improves the search time, but leads to linear complexity of insertion and deletion operations. The results confirm that the considered implementations are optimal for different load classes and are not interchangeable. The main contribution of this work is the experimental proof that canonical AVL trees and online AVL trees are fundamentally different computational models rather than competing implementations.