Path: csiph.com!news.swapon.de!fu-berlin.de!uni-berlin.de!not-for-mail
From: Ian Kelly <ian.g.kelly@gmail.com>
Newsgroups: comp.lang.python
Subject: Re: how to convert code that uses cmp to python3
Date: Fri, 8 Apr 2016 11:05:43 -0600
Lines: 27
Message-ID: <mailman.93.1460135185.2253.python-list@python.org>
References: <57064D0D.1030701@rece.vub.ac.be> <mailman.21.1460030738.2253.python-list@python.org> <87r3egfqiv.fsf@elektro.pacujo.net> <570778ad$0$1587$c3e8da3$5496439d@news.astraweb.com> <CALwzidn7p8z7AE-HjZRuaZiFPQ1Je793_OHA5H7VYc8DVCu74A@mail.gmail.com> <mailman.85.1460125085.2253.python-list@python.org> <87d1q0giwd.fsf@elektro.pacujo.net> <CALwzid=Bz6Xsz_G3NGJSYNuSYRyDB9JiM7KXAshg-LPcwGckvA@mail.gmail.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8
In-Reply-To: <87d1q0giwd.fsf@elektro.pacujo.net>
Precedence: list
Xref: csiph.com comp.lang.python:106693

On Fri, Apr 8, 2016 at 10:33 AM, Marko Rauhamaa <marko@pacujo.net> wrote:
> Ian Kelly <ian.g.kelly@gmail.com>:
>
>> 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__?
>
> Not needed:
>
> ========================================================================
> if key < node.key:
>     look_right()
> elif node.key < key:
>     look_left()
> else:
>     found_it()
> ========================================================================

That makes me a little nervous since it assumes that the keys are
totally ordered and could return an incorrect node if they aren't.
Granted, the keys *should* be totally ordered if the data structure is
being used properly, but an explicit equality check ensures that the
worst that could happen is the node simply isn't found despite being
present.

More to the contextual point, this is still doing two comparisons,
even if both of them are less than, so it doesn't really solve the
OP's issue.