Path: csiph.com!newsfeed.hal-mli.net!feeder3.hal-mli.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!newsfeed.xs4all.nl!newsfeed1.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail
To: python-list@python.org
From: Mark Lawrence <breamoreboy@yahoo.co.uk>
Subject: Re: Balanced trees
Date: Sat, 08 Mar 2014 20:37:58 +0000
References: <lennh4$kpm$1@cabale.usenet-fr.net> <CAPTjJmomgZSFj7TanBn8_qXP4ULhCm85abJ5=2PcikXJkrH6GQ@mail.gmail.com> <CAN1F8qU8AJ+Z-Rb4+wGsYWd_bS5aOA3bsjd5NjF46MUvnecSeQ@mail.gmail.com> <mailman.7473.1393598638.18130.python-list@python.org> <XnsA2E95FA1E1EB6duncanbooth@127.0.0.1> <bnvctpF5vanU1@mid.individual.net> <mailman.7920.1394252278.18130.python-list@python.org> <87eh2d3x8h.fsf_-_@elektro.pacujo.net> <CAGGBd_qU3Zp3A4pymnDQfWynWZwFVrdHJpG=U0WZTap4HiymdA@mail.gmail.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
User-Agent: Mozilla/5.0 (Windows NT 6.1; rv:24.0) Gecko/20100101 Thunderbird/24.3.0
In-Reply-To: <CAGGBd_qU3Zp3A4pymnDQfWynWZwFVrdHJpG=U0WZTap4HiymdA@mail.gmail.com>
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.7937.1394311101.18130.python-list@python.org>
Lines: 43
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:68051

On 08/03/2014 19:58, Dan Stromberg wrote:
> On Sat, Mar 8, 2014 at 12:34 AM, Marko Rauhamaa <marko@pacujo.net> wrote:
>> Ian Kelly <ian.g.kelly@gmail.com>:
>>
>>> I already mentioned this earlier in the thread, but a balanced binary
>>> tree might implement += as node insertion and then return a different
>>> object if the balancing causes the root node to change.
>>
>> True.
>>
>> Speaking of which, are there plans to add a balanced tree to the
>> "batteries" of Python? Timers, cache aging and the like need it. I'm
>> using my own AVL tree implementation, but I'm wondering why Python
>> still doesn't have one.
>
> I think it'd probably be a good idea to add one or more balanced
> binary trees to the standard library.  But I suspect it's been tried
> before, and didn't happen.  It might be good to add an _un_balanced
> tree too, since they do quite well with random keys.
>
> Here's a performance comparison I did of a bunch of tree types in Python:
> http://stromberg.dnsalias.org/~strombrg/python-tree-and-heap-comparison/2014-01/
>

I've found this link useful http://kmike.ru/python-data-structures/

I also don't want all sorts of data structures added to the Python 
library.  I believe that there are advantages to leaving specialist data 
structures on pypi or other sites, plus it means Python in a Nutshell 
can still fit in your pocket and not a 40 ton articulated lorry, unlike 
the Java equivalent.

-- 
My fellow Pythonistas, ask not what our language can do for you, ask 
what you can do for our language.

Mark Lawrence

---
This email is free from viruses and malware because avast! Antivirus protection is active.
http://www.avast.com