Red Black Tree implementation?
duncan smith
buzzard at invalid.invalid
Sat May 11 22:02:33 EDT 2013
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
More information about the Python-list
mailing list