taratam's blog

AVL Tree with duplicates
By taratam, 10 years ago, In English

I implemented avl tree and works correctly, if keys are different or duplicates are not so much. When i try to insert or delete 10000 times random keys in range [0;5] in some moment tree becomes not avl. Is there any reason that rotations broke avl tree constraints if keys duplicates?

  • Vote: I like it
  • -9
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

No,it always should be balanced if you follow rotation rules correctly even when there's duplicates

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there any reason that rotations broke avl tree constraints if keys duplicates?

I think that the only possible reason is that your implementation isn't correct :)

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I solved it!

→ Reply