Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.python > #44988
| References | (1 earlier) <5181ca0e$0$13974$862e30e2@ngroups.net> <mailman.1260.1367546417.3114.python-list@python.org> <518850f8$0$8157$862e30e2@ngroups.net> <mailman.1393.1367889616.3114.python-list@python.org> <518ade0f$1$60230$862e30e2@ngroups.net> |
|---|---|
| Date | 2013-05-08 18:40 -0700 |
| Subject | Re: Red Black Tree implementation? |
| From | Dan Stromberg <drsalists@gmail.com> |
| Newsgroups | comp.lang.python |
| Message-ID | <mailman.1473.1368063609.3114.python-list@python.org> (permalink) |
OK, I've got one copy of trees.py with md5 211f80c0fe7fb9cb42feb9645b4b3ffe. You seem to be saying I should have two though, but I don't know that I do... On 5/8/13, duncan smith <buzzard@invalid.invalid> wrote: > On 07/05/13 02:20, Dan Stromberg wrote: >> >> On Mon, May 6, 2013 at 5:55 PM, duncan smith <buzzard@invalid.invalid >> <mailto:buzzard@invalid.invalid>> wrote: >> >> > > [snip] > >> >> I'd prefer Apache or MIT or BSD 3-clause, but I could probably work with >> this. >> http://joinup.ec.europa.eu/community/eupl/news/licence-proliferation-way-out >> >> I'm eager to see the code, and would love it if you sorted out the >> deletion rebalance issue. >> >> I just plunked some time into >> https://github.com/headius/redblack/blob/master/red_black_tree.py , only >> to find that it didn't appear to be doing deletions correctly - the tree >> would become unprintable after deleting one element. It's possible I >> introduced the bug, but right now I don't particularly suspect so, >> having not changed the __del__ method. >> >> I'm starting to think Red Black Trees are pretty complex. >> >> > > Mine is fixed now (sent to your gmail address). Restoring the tree > properties after deletion is awkward to get right, and doesn't affect > the performance noticeably for smallish trees if you get it wrong. > > I realised my code was buggy when I tried adding, then removing a > million items and ran into the recursion limit. It now passes a test > where I check the tree properties after each addition / deletion. > > Duncan > -- > 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
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