I'm learning AVL Tree and got TLE in recursive code. My tutor suggests to iterative solution. I searched and found a solution which saves parent node in child. I wonder this one could get problem in memory, doesn't it? And is there another way to insert, delete in AVL Tree what doesn't need to save parent in child ones? Please give me a hint.
2 Answers
There are several choices when implementing AVL trees: - recursion or iterative - store balance factor (height of right minus height of left) or height - store parent reference or not
Recursive with height tends to give the most elegant solution but iterative may perform better in some cases so it is worth considering. You can read about the choices: http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_avl.aspx and view an iterative implementation in Java: https://github.com/dmcmanam/bbst-showdown
Parent reference is required in iterative (non-recursive) approach, because it is necessary to retrace after insertion/deletion, we could retrace with stack in recursive approach, while we could only retrace with parent reference in iterative approach. See https://en.wikipedia.org/wiki/AVL_tree#Insert and https://en.wikipedia.org/wiki/AVL_tree#Delete.
After this insertion it is necessary to check each of the node’s ancestors for consistency with the invariants of AVL trees: this is called "retracing".
Here is an iterative BalanceFactor-based AVL tree implementation in C: https://github.com/xieqing/avl-tree
Related