Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #45161

Re: Red Black Tree implementation?

Show key headers only | View raw

[Multipart message — attachments visible in raw view] - view raw

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
6 False 3 11
6 False 3 11
6 False 3 11
11 False 6 15
11 False 6 15
11 False 6 15
11 False 6 15
11 False 6 15
11 False 6 15
11 False 6 15
11 False 6 15
11 False 6 15
11 False 6 15
11 False 6 15
11 False 6 15
11 False 6 15

Thoughts?

BTW, printing an empty tree seems to say "sentinel".  'not sure if that was
intended.

Thanks!



On Thu, May 9, 2013 at 6:52 AM, duncan smith <buzzard@invalid.invalid>wrote:

> On 09/05/13 02:40, Dan Stromberg wrote:
>
>> OK, I've got one copy of trees.py with md5
>> 211f80c0fe7fb9cb42feb9645b4b3f**fe.  You seem to be saying I should have
>> two though, but I don't know that I do...
>>
>>
> [snip]
>
> Yes, 211f80c0fe7fb9cb42feb9645b4b3f**fe is the correct checksum for the
> latest version. The previous version had an issue when adding non-distinct
> items (items that compare equal to items already in the tree). Cheers.
>
> Duncan
>
> --
> http://mail.python.org/**mailman/listinfo/python-list<http://mail.python.org/mailman/listinfo/python-list>
>

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Red Black Tree implementation? Dan Stromberg <drsalists@gmail.com> - 2013-05-01 16:11 -0700
  Re: Red Black Tree implementation? duncan smith <buzzard@invalid.invalid> - 2013-05-02 03:06 +0100
    Re: Red Black Tree implementation? Dan Stromberg <drsalists@gmail.com> - 2013-05-02 19:00 -0700
      Re: Red Black Tree implementation? duncan smith <buzzard@invalid.invalid> - 2013-05-07 01:55 +0100
        Re: Red Black Tree implementation? Chris Angelico <rosuav@gmail.com> - 2013-05-07 11:21 +1000
        Re: Red Black Tree implementation? Dan Stromberg <drsalists@gmail.com> - 2013-05-06 18:20 -0700
          Re: Red Black Tree implementation? duncan smith <buzzard@invalid.invalid> - 2013-05-07 14:28 +0100
          Re: Red Black Tree implementation? duncan smith <buzzard@invalid.invalid> - 2013-05-09 00:21 +0100
            Re: Red Black Tree implementation? Dan Stromberg <drsalists@gmail.com> - 2013-05-08 18:40 -0700
              Re: Red Black Tree implementation? duncan smith <buzzard@invalid.invalid> - 2013-05-09 05:31 +0100
              Re: Red Black Tree implementation? duncan smith <buzzard@invalid.invalid> - 2013-05-09 14:52 +0100
                Re: Red Black Tree implementation? Dan Stromberg <drsalists@gmail.com> - 2013-05-11 16:24 -0700
                Re: Red Black Tree implementation? duncan smith <buzzard@invalid.invalid> - 2013-05-12 02:34 +0100
                Re: Red Black Tree implementation? Dan Stromberg <drsalists@gmail.com> - 2013-05-11 18:29 -0700
                Re: Red Black Tree implementation? duncan smith <buzzard@invalid.invalid> - 2013-05-12 03:02 +0100
                Re: Red Black Tree implementation? duncan smith <buzzard@invalid.invalid> - 2013-05-12 19:15 +0100

csiph-web