Re: [PATCH 4/8] Add treap implementation

From: Jonathan Nieder <jrnieder@gmail.com>
Date: Jul 15, 2010, 19:09 UTC
Message-ID: <20100715190902.GB2774@burratino>
In-Reply-To: <1279210984-31604-5-git-send-email-artagnon@gmail.com>

Ramkumar Ramachandra wrote:

Show 6 quoted lines

> Treaps provide a memory-efficient binary search tree structure.
> Insertion/deletion/search are about as about as fast in the average
> case as red-black trees and the chances of worst-case behavior are
> vanishingly small, thanks to (pseudo-)randomness.  The bad worst-case
> behavior is a small price to pay, given that treaps are much simpler
> to implement.

I still haven’t checked this implementation in detail, but it seemed to work in practice and is about to change anyway.

I like the documentation updates. What else changed from the previous round?

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.