AVL tree: Difference between revisions

Caution: AVL trees are not cache friendly. Linear search is significantly faster (roughly six times faster for a list of 1e8 numbers on current machines and arbitrary data), and using small cached copies of recent updates allows time for updates to be inserted into a fresh copy of the larger list (on a different thread, or failover machine -- search the current "hot copy" before searching the larger "cold copy"). Use [[wikipediawp:AoS_and_SoA#Structure_of_arrays|structure of arrays]] for best performance with that approach. (Typical avl implementation also uses memory equivalent to several copies of a flat list.)