Question

can someone tell me if using an AVL is preferred over using a 2-3 tree or vice-versa and why so?

Thx

Pas de solution correcte

Autres conseils

My own preference among the various flavors of balanced binary trees is AVL trees. They are simpler to program than any of the alternatives (see my implementation here and here, and note that even deletion isn't particularly complicated) because there are less cases to consider, they provide very-slightly faster lookup (because they are more strictly balanced than the alternatives), and there are no hidden worst cases or amortized time-bounds.

I also generally prefer AVL trees to hash tables. I know that the expected-time complexity of hash tables beats the guaranteed-time complexity of AVL trees, but in practice constant factors make the two data structures generally competitive, and there are no niggling worries about some unexpected data that evokes bad behavior. Also, I often find that sometime during the maintenance life of a program, in a situation not foreseen when the initial choice of a hash table seemed right, that I need the data in sorted order, so I end up rewriting the program to use an AVL tree instead of a hash table; do that enough times, and you learn that you may as well just start with AVL trees.

If your keys are strings, ternary search tries offer a reasonable alternative to AVL trees.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top