{
    "info": {
        "author": "Peter Hillerstr\u00f6m",
        "author_email": "peter.hillerstrom@gmail.com",
        "bugtrack_url": null,
        "classifiers": [
            "Development Status :: 4 - Beta",
            "Environment :: Other Environment",
            "Intended Audience :: Developers",
            "Intended Audience :: Information Technology",
            "Intended Audience :: Science/Research",
            "License :: OSI Approved",
            "License :: OSI Approved :: GNU Lesser General Public License v3 or later (LGPLv3+)",
            "Operating System :: OS Independent",
            "Programming Language :: Python",
            "Programming Language :: Python :: 2",
            "Programming Language :: Python :: 3",
            "Topic :: Other/Nonlisted Topic",
            "Topic :: Scientific/Engineering",
            "Topic :: Software Development",
            "Topic :: Software Development :: Libraries :: Python Modules"
        ],
        "description": "# Leftrb/LLRB\r\n\r\nLeftrb is a Left-Leaning Red-Black (LLRB) implementation of 2\u20133 balanced binary\r\nsearch trees in Python.\r\n\r\nThis is a straightforward port of the Java code presented by Robert Sedgewick in\r\n[his paper]((http://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf) and in the\r\nbook [Algorithms, 4th Edition](http://algs4.cs.princeton.edu/home/), which is written\r\nby Robert Sedgewick and Kevin Wayne. By their permission, the [original GPL v3 licensed Java\r\ncode](http://www.cs.princeton.edu/~rs/talks/LLRB/Java/RedBlackBST.java)\r\nis licensed as LGPL v3, and ported to Python.\r\n\r\n## Overview\r\n\r\nA balanced binary search tree (BBST) maintains elements in sorted order under dynamic \r\nupdates (inserts and deletes) and can support various order-specific queries.\r\n\r\nRed-black trees are the de facto standard BBST algorithms, and are the underlying\r\ndata structure for symbol-table implementations within C++, Java, Python, BSD Unix,\r\nLinux and many other modern systems.\r\n\r\nAll red\u2013black trees are based on implementing 2-3 or 2-3-4 trees within a binary tree,\r\nusing  red links to bind together internal nodes into 3-nodes or 4-nodes. Search, insert\r\nand delete operations are O(log n) and space requirements are O(n).\r\n\r\nHowever, many traditional implementations have lots of repetitive code on the symmetric\r\nbranches of rotation and deletion operations. So they are not easy to reason about and \r\naugment with other properties, which is what BBST's are often used for: They are used\r\nto implement other common data structures like Priority Queues and Interval Trees.\r\n\r\nThe LLRB method of implementing 2-3 trees is a recent improvement over the traditional\r\nimplementation \u2014 it maintains an additional invariant that all red links must lean left\r\nexcept during inserts and deletes. Because of this, they can be implemented by adding\r\njust a few lines of code to standard BST algorithms.\r\n\r\nThe LLRB tree is based on combining three ideas:\r\n\r\n- Use a recursive implementation.\r\n- Require that all 3-nodes lean left.\r\n- Perform rotations on the way up the tree (after the recursive calls).\r\n\r\nThe LLRB approach was discovered relatively recently (in 2008) by Robert Sedgewick\r\nof Princeton University. For original code and more information read the paper *\"Left-leaning Red-Black Trees\"* at [http://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf](http://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf)\r\n\r\n## Installation\r\n\r\nFrom Python package index:  \r\n\r\n    pip install leftrb\r\n\r\nor from Github source:  \r\n\r\n    git clone https://github.com/peterhil/leftrb.git  \r\n    cd leftrb  \r\n    python setup.py install\r\n\r\n## About\r\n\r\nLeftrb/LLRB was written by [Peter Hillerstr\u00f6m](http://composed.nu/peterhil/).  \r\nFollow me on Twitter [@peterhil](http://www.twitter.com/peterhil)!",
        "description_content_type": null,
        "docs_url": null,
        "download_url": "UNKNOWN",
        "downloads": {
            "last_day": -1,
            "last_month": -1,
            "last_week": -1
        },
        "home_page": "https://github.com/peterhil/leftrb",
        "keywords": "",
        "license": "GNU Lesser General Public License v3 or later (LGPLv3+)",
        "maintainer": "",
        "maintainer_email": "",
        "name": "leftrb",
        "package_url": "https://pypi.org/project/leftrb/",
        "platform": "UNKNOWN",
        "project_url": "https://pypi.org/project/leftrb/",
        "project_urls": {
            "Download": "UNKNOWN",
            "Homepage": "https://github.com/peterhil/leftrb"
        },
        "release_url": "https://pypi.org/project/leftrb/0.1.3/",
        "requires_dist": null,
        "requires_python": null,
        "summary": "Leftrb is a Left-Leaning Red-Black (LLRB) implementation of 2\u20133 balanced binary",
        "version": "0.1.3"
    },
    "last_serial": 1425274,
    "releases": {
        "0.1": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "e4cd4912d4f9a65bd9c597f7a19bf394",
                    "sha256": "9dccf5f7099aec8beeba1f6d27996a3b8d7f29dba3d6ed1c879b7b8991f19d92"
                },
                "downloads": -1,
                "filename": "leftrb-0.1.tar.gz",
                "has_sig": false,
                "md5_digest": "e4cd4912d4f9a65bd9c597f7a19bf394",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": null,
                "size": 4216,
                "upload_time": "2013-01-22T03:10:33",
                "url": "https://files.pythonhosted.org/packages/e6/02/bdb593625a94da936af90e8afd477dd729e158c83207823f0f0610ec5e53/leftrb-0.1.tar.gz"
            }
        ],
        "0.1.1": [],
        "0.1.2": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "6bc0c63475415f68ac5714ffab16a1d1",
                    "sha256": "54959aa96348d62dd49f109f2aa6fe91806f3b96b5d7fe50f62254d9935074ab"
                },
                "downloads": -1,
                "filename": "leftrb-0.1.2.tar.gz",
                "has_sig": false,
                "md5_digest": "6bc0c63475415f68ac5714ffab16a1d1",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": null,
                "size": 165162,
                "upload_time": "2013-04-05T23:14:35",
                "url": "https://files.pythonhosted.org/packages/38/18/50cc638e6d7348ed4d1c348d7a41d8f3f31d6c6e2d82b6ac6665d161ba79/leftrb-0.1.2.tar.gz"
            }
        ],
        "0.1.3": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "8f58ea55ef19fe3b1c01b6071861e7cb",
                    "sha256": "c6cdabcfa4b640372827b52acef875644659402373e1fb6342b8784dde3aeb0e"
                },
                "downloads": -1,
                "filename": "leftrb-0.1.3.tar.gz",
                "has_sig": false,
                "md5_digest": "8f58ea55ef19fe3b1c01b6071861e7cb",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": null,
                "size": 177550,
                "upload_time": "2013-07-28T18:21:53",
                "url": "https://files.pythonhosted.org/packages/28/f8/e4a1afc14be34538a5226147eababfa12f093e3ed1da51754687d29c7004/leftrb-0.1.3.tar.gz"
            }
        ]
    },
    "urls": [
        {
            "comment_text": "",
            "digests": {
                "md5": "8f58ea55ef19fe3b1c01b6071861e7cb",
                "sha256": "c6cdabcfa4b640372827b52acef875644659402373e1fb6342b8784dde3aeb0e"
            },
            "downloads": -1,
            "filename": "leftrb-0.1.3.tar.gz",
            "has_sig": false,
            "md5_digest": "8f58ea55ef19fe3b1c01b6071861e7cb",
            "packagetype": "sdist",
            "python_version": "source",
            "requires_python": null,
            "size": 177550,
            "upload_time": "2013-07-28T18:21:53",
            "url": "https://files.pythonhosted.org/packages/28/f8/e4a1afc14be34538a5226147eababfa12f093e3ed1da51754687d29c7004/leftrb-0.1.3.tar.gz"
        }
    ]
}