Red Black Tree implementation?

[Dan Stromberg]

On Sat, May 11, 2013 at 4:24 PM, Dan Stromberg <drsalists at 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().

I've also changed around the comparisons a bit, to use a __cmp__ method but
still provide __eq__, __neq__ and a new __lt__.

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?

Thanks!

PS: Is it about time we moved this discussion off python-list?
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/20130511/cc6ef1dd/attachment.html>