How come an AVL tree can be a skewed tree as at any node, the max difference of height can be one.
" In the case of Skewed Trees , the complexity becomes O(n)O(n), where “n” is the number of nodes in the tree. Now to improve time complexity, We have to manage the height of the tree to improve time complexity, such that we can bring the time down to O(logn)O(logn) for performing these basic operations."
Can someone help me understand this?
Hi @Manikandan_R,
This is Fatimah Abdullah from Educative. Thank you for reaching out to us!
You are right, the AVL trees are not skewed trees.
This passage that seems to be the cause of your confusion is actually explaining why do we need AVL trees in the first place. As you know a simple BST can easily become skewed. In that case, the complexity in O(n). Therefore, it is not an ideal approach.
AVL trees are the solution to this problem as the maximum difference of hight between left and right subtree can only be 1. This is a constant difference, hence negligible.
The context of the above-mentioned passage is not AVL, it is a simple BST tree. I hope this clears up your confusion.
If you have any further queries, feel free to get in touch with me.
Best Regards,
Fatimah Abdullah | Developer Advocate
Educative Inc.