AVL和红黑树性能对比

AVL和红黑树性能对比，有详细的测试数据。AVL和红黑树都是平衡树。
Binary search tree (BST) based data structures, such
as AVL trees, red-black trees, and splay trees, are often
used in system software, such as operating system
kernels. Choosing the right kind of tree can impact
performance significantly, but the literature offers few
empirical studies for guidance. We compare 20 BST
variants using three experiments in real-world scenarios
with real and artificial workloads. The results indicate
that when input is expected to be randomly ordered
with occasional runs of sorted order, red-black
trees are preferred; when insertions often occur in
sorted order, AVL trees excel for later random access,
whereas splay trees perform best for later sequential
or clustered access. For node representations, use of
parent pointers is shown to be the fastest choice, with
threaded nodes a close second choice that saves memory;
nodes without parent pointers or threads suffer
when traversal and modification are combined; maintaining
a in-order doubly linked list is advantageous
when traversal is very common; and right-threaded
nodes perform poorly.