Started solving for AVL (Adelson-Velsky and Landis, named after its inventors) trees, 3 week back but now i am finally done. For starters like me, got to understand on how efficiently does stack data structure work. Even while dealing with search operations, had to use stack just to keep track on which set of nodes I traversed on. Of course the node traversal starts from the root node.
All this is done for practice sake and clear my understanding regarding data structures and algorithms. That's why I have used C programming, to get to know the nuts and bolts...
The searching operation is after all the most basic of all in a tree, especially search trees, decreases your traversal effort and stops wasting time, dealing with nodes, where you think "that's not where my key is.."
Built a dedicated files, named as helpers.C where i defined all the possible definitions of stack, right from push, pop and stacktop. Even mentioned definition displaying the nodes from top to bottom for debugging sake. It is easier to manage all the members of stack like top, size and an array into a single entity so I also defined a structure.
However make sure to include the necessary header files and the files, defined by you.
As per an example, i used this.
As per the newnode is concerned, a pointer is pointing to memory address allocated in heap memory is done, whose left and right child are pointing to null pointers and an assignment of the key, the data is also done.
Remember, we used stack to store information on which path did we traversed, at the stack top there exists a memory address pointing to a node belonging to the existing tree where an int value of 49 exists. There is another reason behind that, will be covered shortly.
But what does AVL trees involve ? It involves 3 core steps, calculate the node's height, checkout it balance factor, which is the difference in height of its right branch from its left branch and third if the balance factor's value exceeds a certain threshold, rotation of nodes shall be done. Usually the threshold is beyond -1 (that is more negative than -1, say -2, -3 etc) or +1 (more positive than +1, say 2,3 etc).
There are 4 types of rotations involved: LL (left-left), LR (left-right), RL (right-left) and RR (right-right). Let me show you with a diagram.
The first column shows LL rotation and the second column shows LR rotation.
Similarly, the next diagram, the first column is about RR rotation and the second one is the RL rotation.
I guess it looks a bit messy, I shall attach the github repo at the very bottom.
The main issue i faced is regarding segmentation fault. It is like thorn under my feet. Also during rotation I accidentally connected the leaf node back to the parent, so when in-order or pre-order traversal function are triggered, it used to give stack-overflow, after the flow gets stuck in an unwanted circular loop. Had to sketch diagrams all over again and again.
It is a hard rule AVL trees, also a BST (Binary Search Tree) that while all the nodes from left to right while using in-order traversal, they must appear sorted, because upon dealing with deletion, getting in touch with the successor node is very important as that node where the data is shall be replaced by its successor's data. So structurally not removing the node to be deleted rather a form of replacement, and going down the line where the actual successor node is, we can use free().
Let's say we want to delete the root node, which is having a value of 38. We shall go 1 step rightward and in a loop continue moving to the left until there is a dead end. Even here stack shall be used. So that the left and right child pointers of the parent of the successor node, which is holding a value of 46 can be updated. In this case the left child of the parent shall hold the address of the right child of the successor node.
Now we shall move backwards, popping out address of the nodes stored in stack to check for their balance factor, if balance factor > 1 or < -1, then go for rotation. Of course this shall be done in a loop.
Yeah in the end, there is another thing to mention, about height of node. It is not a hard and fast rule, but i considered leaf nodes to have height of 0, so what i did is increment by 1 as i move from root node to the destination node, giving me a depth, using which i subtract from st.top (the highest index value). In other words, the longest route in that traversal.
Observe in line number 265. Notice that there 'I' mentioned the last parameter of checkForRotation(), denoting check of rotation where I am dealing with insertion operation and 'D' for deletion.
PS
github repo: https://github.com/S-a-t-y-aa-y-t-a-S/DSA/blob/main/avl.C