1
$\begingroup$

It seems that in a full AVL tree, the left edge is always the minimum-cost path. For example, take the following full AVL tree:

full avl tree

The min-cost path would be 8-6-5. However this is not the case with other AVL trees. Take the previous tree with an additional 4 inserted:

avl tree

Here the min-cost path would be 8-6-7 rather than 8-6-5-4.

What is the most efficient algorithm to find the min-cost path in any AVL tree? Given the characteristics of AVL trees, is this algorithm faster than it would be for a standard BST?

$\endgroup$
  • 2
    $\begingroup$ I'd prefer an explicit definition of minimum-cost path over what I glean from the examples (sum of node labels on a path between root an leaf). The node labels are in strictly ascending order - 1) is that guaranteed? 2) any additional conditions? $\endgroup$ – greybeard Mar 4 '20 at 6:11
1
$\begingroup$

Searching in an AVL tree is anyways only at most O(log n) (see on @Wikipedia: https://en.wikipedia.org/wiki/AVL_tree?wprov=sfta1). If you do not care about the higher cost of rebalancing AVL tree instead of BSTree, this tree will have even the advantage of always maintaining the AVL-min-cost path on the left edge. Search the left edge has also O(log n) so no cheaper than other trees. Balancing a tree is only nesessary if building a tree can cause massive imbalance, only than AVL has a marginal advantage above BST.

To your counter example on AVL tree with a not-left-edge min-cost: This is to my quick grasp the furthest imbalance one can find before need of rebalancing of AVL is needed. Hence no need to worry about finding the minimum cost path in AVL tree may be more difficult due to tree depth. So searching the minimum path within the left and not totally left path is O(log n +1) equaling O(log n). So it is basically not harder to find the actual minimum path than finding the obvious left edge.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.