On 12/05/13 02:29, Dan Stromberg wrote:
On Sat, May 11, 2013 at 4:24 PM, Dan Stromberg <drsali...@gmail.com <mailto:drsali...@gmail.com>> wrote: I'm afraid I'm having some trouble with the module. I've checked it into my SVN at http://stromberg.dnsalias.org/svn/red-black-tree-mod/trunk/duncan I have two versions of your tests in there now - "t" is minimally changed, and test-red_black_tree_mod is pretty restructured to facilitate adding more tests later. I get the same problem with either version of the tests. The problem I'm seeing is that the tree, when built from items, isn't looking quite right. I inserted a print(tree) into the for loop, and I'm getting the following, where I expected the tree to grow by one element on each iteration: $ python t 6 False None None 6 False 3 None 6 False 3 15 6 False 3 15 I figured out that this was printing a single node and some of its attributes, not an entire tree. I changed it to print an entire tree using self.in_order().
Yes, I've just posted regarding that.
I've also changed around the comparisons a bit, to use a __cmp__ method but still provide __eq__, __neq__ and a new __lt__.
I have implemented a lot (maybe all?) of the set methods in a subclass. I should probably root that out and have a think about what should be in the RedBlackTree class and what subclasses might look like.
I'm up against a new problem now that it'd be nice if you could look at: In BinaryTree.find(), it sometimes compares the item being searched for against None. In 2.x, this gives strange results, but may be benign in this code. In 3.x, this raises an exception. I've added a comment about this in the SVN repo I mentioned above. You can see the traceback yourself with python3 test-red_black_tree_mod . What should BinaryTree.find() do if it finds a data.node that is None?
A call to "find(data)" should find and return either a node containing "data"; or the sentinel node where "data" should be added. It should not get as far as the left or right child of a sentinel node (which would equal None). I'll look at this tomorrow. I did have the truth value of a node depending on it's data value (None implying False). Then I considered the possibility of actually wanting None as a value in the tree and changed it, so I could have introduced a bug here.
Thanks! PS: Is it about time we moved this discussion off python-list?
Maybe. You have my official e-mail address. Cheers. Duncan -- http://mail.python.org/mailman/listinfo/python-list
