Ian Kelly <ian.g.ke...@gmail.com>: > On Fri, Apr 8, 2016 at 10:33 AM, Marko Rauhamaa <ma...@pacujo.net> wrote: >> Ian Kelly <ian.g.ke...@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.
That's all the more reason to tie the order explicitly to < and nothing else. > 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. Well, how do you know how __eq__ and __lt__ are related? Better simply *define* a *match* as not key < node.key and not node.key < key > 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. I'm not sure the OP has a real issue. If *that* is a real issue, I recommend a different programming language. Thing is, I bet method calls are the single most expensive Python operation, yet would anyone suggest avoiding method calls? Marko -- https://mail.python.org/mailman/listinfo/python-list
