On Fri, Apr 8, 2016 at 3:23 AM, Steven D'Aprano <st...@pearwood.info> wrote: > On Fri, 8 Apr 2016 06:34 pm, Marko Rauhamaa wrote: > >> Antoon Pardon <antoon.par...@rece.vub.ac.be>: >> >>> In python2 descending the tree would only involve at most one >>> expensive comparison, because using cmp would codify that comparison >>> into an integer which would then be cheap to compare with 0. Now in >>> python3, I may need to do two expensive comparisons, because there is >>> no __cmp__ method, to make such a codefication. >> >> I think you should base your tree implementation on key.__lt__() only. >> Only compare keys using <, nothing else, ever. > > I believe that's how list.sort() and sorted() work: > > py> class Spam(object): > ... def __init__(self, n): > ... self.n = n > ... def __lt__(self, other): > ... return self.n < other.n > ... def __repr__(self): > ... return repr(self.n) > ... > py> L = [Spam(5), Spam(3), Spam(9), Spam(1), Spam(2)] > py> L > [5, 3, 9, 1, 2] > py> sorted(L) > [1, 2, 3, 5, 9] > > > as well as max() and min().
That's fine for those operations and probably insert, but how do you search an AVL tree for a specific key without also using __eq__? -- https://mail.python.org/mailman/listinfo/python-list
