search

walkccc / CLRS

📚 Solutions to Introduction to Algorithms Third Edition
https://walkccc.me/CLRS
MIT License
4.66k stars 1.26k forks source link

Exercise 12.3-5 running time is not O(h) #320

Closed ywxktc closed 4 years ago

ywxktc commented 4 years ago

The worst-case running time of TREE-PREDECESSOR is O(lg(n) * lg(n)) since the 7th line could be executed O(lg(n)) times and the running time of PARENT is O(lg(n)).

I rewrite the TREE-PREDECESSOR .

TREE-PREDECESSOR(T, x)
    if x.left != NIL
        return TREE-MAXIMUM(x.left)
    y = T.root
    pred = NIL
    while y != NIL and y.key != x.key
        if y.key < x.key
            pred = y
            y = y.left
        else y = y.right
    return pred
walkccc commented 4 years ago

Thanks for pointing out this issue. Yes, we should avoid calling PARENT in TREE-PREDECESSOR and we should aim for a O(lg n) algorithm to find the predecessor since we're given a BST.

It seems that your pseudocode is not correct. I've updated the solution here and provided examples in the .cpp code.

Hope this helps. Thanks.