5

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

Thx

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
Melvic
  • 51
  • 1
  • 4

1 Answers1

3

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.

user448810
  • 17,381
  • 4
  • 34
  • 59
  • Thx for your answer. This was a question exam which I had last year. It said would you use an AVL tree in preference over a 2-3 tree. I think the answer should be in terms of complexity, balancing and which is the faster between the 2. Could you answer this pls? – Melvic Jan 04 '12 at 16:33
  • If implemented correctly, the two types of balanced trees should have the same asymptotic time complexity, same worst-case time complexity, same average balance and same speed. The question asks for a preference, and I gave mine, and the reasons for it. What else do you want to know? – user448810 Jan 04 '12 at 21:41
  • So do you think that this is a question opinion? – Melvic Jan 04 '12 at 22:17