Simon Forman <sajmik...@gmail.com> writes: > This code is part of a delete() method for a binary tree > implementation. "None" is used to simulate a NULL pointer. In the case > where both children are non-None the code goes on to handle that. > > None is a "unitary" or "singleton" value, so "is" is the right > comparison operator to use with it, at least in this "imitation > pointer" usage.
Yes, but the concept of null pointers is considered kludgy these days. One alternative is to represent an empty node as an empty list [], and a node with value x as the 1-element list [x]. That incurs some storage overhead, but all the case by case checking in your comparison function goes away: return (self.higher + self.lower)[:1] > I've never used dis.dis() to check the bytecodes, but I wouldn't be > surprised to find that the compiler generated the same bytecode > whether you explicitly state the return or comment it out.) I really wouldn't worry about this. Python is so slow no matter what you do, that 1 more no-op bytecode won't matter. > Last but not least, the logic may seem backwards but it's actually > correct. If you check for non-None (NULL) -ness and return the thing > you checked, rather than checking for None-ness and returning the > other, the case where both are non-None is not handled correctly. The code you posted didn't return anything if both values were non-None. As for checking for None-ness vs. non-None-ness, sure, the two are logically equivalent, but I think checking for non-None expresses the algorithm more clearly. > FWIW, here's the BinaryTree class, ... > A Binary Tree implementation. Provides: > get(key) - Return item for key or None. I'm sorry but I find that class rather ugly. The code would be a lot smaller and have fewer corner cases with a different data representation. -- http://mail.python.org/mailman/listinfo/python-list