search

ossner / TUMGAD

Exercise generator and helpful materials for the Introduction to Algorithms and Data Structures 📚
https://ossner.github.io/TUMGAD/src/routes
MIT License
43 stars 4 forks source link

Wrong answer in AVL-Tree exercise #2

Closed HardMax71 closed 3 years ago

HardMax71 commented 3 years ago

Describe the bug The type of rotation after specific action in solutions.pdf is false, although the tree is correct.

To Reproduce

  1. Seed = 4.
  2. Go to "AVL-Trees", part with delete(17).
  3. Execute all inserts/deletes before delete(17).
  4. Execute delete(17).
  5. Open solutions.pdf, there will be "l-r rotation" instead of "no rotation".

Expected behavior "No rotation" is expected.

Screenshots Task itself : image

AVL-Tree before delete(17) : image

Solution (after delete(17)) in solutions.pdf : image

Solution path (used https://www.cs.usfca.edu/~galles/visualization/AVLtree.html) : https://gyazo.com/e05859c74b19c312d042c142966c4fb8

Desktop (please complete the following information):

Additional context Add any other context about the problem here.

ossner commented 3 years ago

The algorithm seems to switch 17 with 24 instead of the correct 12. Because of that, the balance difference is 2/-1. After the l/r rotation is carried out, the tree is correct again.

Technically, there was nothing wrong and it was a simple issue of which node to replace the deleted node with if it has two children. Since GAD standardizes it to be the predecessor, our implementation is wrong and this will be fixed after some more testing.

This would also mean that the arrival at that position was incorrect since delete(16) should have resulted in 16 being replaced by 12 (predecessor). This is also the way it works in the simulator by David Galles (USFCA).

Side note: It's 2:30 am and I have no idea why I just did this for 30 minutes instead of going to sleep