I searched that question but didn't understand the answer that is: We can traverse the tree in O(n) time and insert each element into an initially empty AVL tree; this will take O(nlogn) time overall. To get O(n) ‘best-case’ performance we can do something that’s a bit of a hack: try to verify that the BST is a valid AVL tree, which we can do in O(n) time; if it is, return it as it is. Otherwise, create a new AVL tree as described. It’s questionable as to whether this is really a ‘bestcase’ result, as we don’t actually do any conversion, only verification.
Fatima Tahir 0 Newbie Poster
deceptikon 1,790 Code Sniper Team Colleague Featured Poster
Technically the best case is the input tree is already AVL balanced, so the solution is legit from a complexity standpoint. The more practical problem with this solution is it adds a verification step regardless of the input tree and slows down the algorithm even when you need to adjust balance.
To properly determine if the solution is worth the cost, you'd need to measure how much of an impact the verification step has and compare against the probability of receiving a valid AVL tree as input. That leaves the realm of complexity theory, but it's something that must be done with actual code.
Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.