Red Black Tree implementation?

[duncan smith]

On 12/05/13 02:29, Dan Stromberg wrote:
>
> On Sat, May 11, 2013 at 4:24 PM, Dan Stromberg <drsalists at gmail.com
> <mailto: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().

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