2 ms·
That result surprises me. Red-black trees do their work at insertion time, and AVL trees split the work between insertion and selection. This should make red-
by jrockway 15y ago
That result surprises me. Red-black trees do their work at insertion time, and AVL trees split the work between insertion and selection. This should make red-black trees faster at selection and AVL trees faster at insertion, and both should do a set of insertions and selections in the same time.
(A red-black tree is a plain-old binary search tree for everything but modifications.)
- pavpanchekha 15y agoAVL trees give shorter path lengths. So the resulting structure ends up being better, depending on your exact balance of insertion and selection.
- SamReidHughes 15y agoWhaaa? AVL trees don't split the work between insertion and selection. Selections are plain old read-only BST lookups.