I'm looking for a pythonic red-black tree...

Discussion in 'Python' started by Just Another Victim of the Ambient Morality, Dec 15, 2006.

  1. I need a red-black tree in Python and I was wondering if there was one
    built in or if there's a good implementation out there. Something that,
    lets face it, does whatever the C++ std::map<> allows you to do...
    Thank you...
    Just Another Victim of the Ambient Morality, Dec 15, 2006
    #1
    1. Advertising

  2. At Thursday 14/12/2006 22:20, Just Another Victim of the Ambient
    Morality wrote:

    > I need a red-black tree in Python and I was wondering if there was one
    >built in or if there's a good implementation out there. Something that,
    >lets face it, does whatever the C++ std::map<> allows you to do...


    There are several implementations, try google...


    --
    Gabriel Genellina
    Softlab SRL

    __________________________________________________
    Correo Yahoo!
    Espacio para todos tus mensajes, antivirus y antispam ¡gratis!
    ¡Abrí tu cuenta ya! - http://correo.yahoo.com.ar
    Gabriel Genellina, Dec 15, 2006
    #2
    1. Advertising

  3. Just Another Victim of the Ambient Morality

    placid Guest

    Just Another Victim of the Ambient Morality wrote:
    > I need a red-black tree in Python and I was wondering if there was one
    > built in or if there's a good implementation out there. Something that,
    > lets face it, does whatever the C++ std::map<> allows you to do...
    > Thank you...



    try,

    http://py.vaults.ca/apyllo2.py/211227974


    Cheers
    placid, Dec 15, 2006
    #3
  4. Just Another Victim of the Ambient Morality

    Jorgen Grahn Guest

    On Fri, 15 Dec 2006 01:20:34 GMT, Just Another Victim of the Ambient Morality <> wrote:
    > I need a red-black tree in Python and I was wondering if there was one
    > built in or if there's a good implementation out there. Something that,
    > lets face it, does whatever the C++ std::map<> allows you to do...


    Nitpick: std::map is implemented using RB-trees, but it isn't one,
    interface-wise.

    /Jorgen

    --
    // Jorgen Grahn <grahn@ Ph'nglui mglw'nafh Cthulhu
    \X/ snipabacken.dyndns.org> R'lyeh wgah'nagl fhtagn!
    Jorgen Grahn, Dec 15, 2006
    #4
  5. Just Another Victim of the Ambient Morality

    Guest

    You could try and wrap the C/C++ code at
    http://web.mit.edu/~emin/www/source_code/index.html and make a python
    extension...

    On Dec 14, 8:20 pm, "Just Another Victim of the Ambient Morality"
    <> wrote:
    > I need a red-black tree in Python and I was wondering if there was one
    > built in or if there's a good implementation out there. Something that,
    > lets face it, does whatever the C++ std::map<> allows you to do...
    > Thank you...
    , Dec 15, 2006
    #5
  6. On Fri, 15 Dec 2006 01:20:34 +0000, Just Another Victim of the Ambient
    Morality wrote:

    > I need a red-black tree in Python and I was wondering if there was one
    > built in or if there's a good implementation out there. Something that,
    > lets face it, does whatever the C++ std::map<> allows you to do...


    Are you really looking specifically for a red-black tree, or do you want a
    container where iterators return values in sorted order? For instance, my
    favorite sorted container is the skip-list:

    * inherently thread safe even during container updates
    * updates as fast as searches - significantly faster than red-black tree
    * search as fast as trees on average - but probablistic (like hashtable)
    * sequential access as fast as a linked list
    * Uses 33% less memory than binary trees (like red-black tree)
    * in general, performs like a hashtable, but sorted

    Java example: http://bmsi.com/java/SkipList.java

    In Python, the performance of a pure Python container will be
    disappointing unless it leverages a native container. For many
    applications, you can use a dict and sort when iterating (using heapq to
    amortize the sorting).

    If I ever get the time, I would seriously consider trying to modify Python
    to replace the built-in dict with a skip-list algorithm and compare the
    performance. Failing that, an extension module implementing a sorted
    container of some description would be useful.

    --
    Stuart D. Gathman <>
    Business Management Systems Inc. Phone: 703 591-0911 Fax: 703 591-6154
    "Confutatis maledictis, flamis acribus addictis" - background song for
    a Microsoft sponsored "Where do you want to go from here?" commercial.
    Stuart D. Gathman, Dec 16, 2006
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. moondaddy
    Replies:
    3
    Views:
    907
    Steven Cheng[MSFT]
    Jul 16, 2004
  2. Thomas

    Red Black Tree!!!

    Thomas, Feb 20, 2004, in forum: C++
    Replies:
    6
    Views:
    6,306
    Claudio Puviani
    Feb 20, 2004
  3. Fei Liu
    Replies:
    11
    Views:
    3,045
    Fei Liu
    Jun 29, 2007
  4. Willow Schlanger
    Replies:
    3
    Views:
    1,699
    Willow Schlanger
    Dec 28, 2010
  5. Dan Stromberg

    Red Black Tree implementation?

    Dan Stromberg, May 2, 2013, in forum: Python
    Replies:
    14
    Views:
    273
    duncan smith
    May 12, 2013
Loading...

Share This Page