Balanced-tree-based maps are a workhorse in functional programming. Because of their disarming simplicity, Chris Okasaki's purely functional red-black trees are a popular means for implementing such maps. In his book, self-balancing binary search trees are less than a page of code. Except that delete is left as an exercise to the reader. Unfortunately, deletion is tricky. Stefan Kahrs devised a wi
We show that the idea of left-leaning reduces one pattern matching in the insertion operation of Okasaki's purely functional red-black trees. We proved in Coq that the invariants of left-leaning red-black trees stand for our purely functional algorithm of the insertion operation. Our benchmark shows that our algorithm is slightly faster than Okasaki's algorithm in some cases. History In 1979, Guib
このページは、マップと呼ばれるデータ構造の実装の1つである赤黒木 (2色木、red-black tree)について解説するページです。赤黒木は、要素の 挿入・削除・検索などの操作が \(O(\log n)\) の計算量で実行出来る平衡木 です(\(n\) は要素数)。赤黒木はやっていることは単純なのですが、とにかく 場合分けがたくさんあって、習得しようとしながらもくじけてしまった人も 多いのではないでしょうか? しかし、ご安心ください。このページは場合分けを出来るだけ減らし、 挿入操作で4パターン、削除操作で8パターンさえ理解すれば赤黒木が分かる ように書かれています。削除操作に関しては、左右対称のパターンを省けば 4パターン理解すればおおむね OK です。これから赤黒木を勉強しようという人 はもちろん、一度は勉強したが挫折してしまったという人も是非とも読んでみて ください。 【準備】 ま
Haskellでの赤黒木の実装の美しさに感動した data Color = R | B data RedBlackSet a = E | T Color (RedBlackSet a) a (RedBlackSet a) balance B (T R (T R a x b) y c) z d = T R (T B a x b) y (T B c z d) balance B (T R a x (T R b y c)) z d = T R (T B a x b) y (T B c z d) balance B a x (T R (T R b y c) z d) = T R (T B a x b) y (T B c z d) balance B a x (T R b y (T R c z d)) = T R (T B a x b) y (T B c z d) balance color a x
開発が成熟してきたので、ここらで拙作のパターンマッチライブラリ、optimaを日本語で解説したいと思う。ただし解説とは言っても、詳細な仕様をだらだらと解説するようなことはしない。むしろ「なぜパターンマッチなのか」を踏まえた上で、簡単な入門と使用例を示すことで、パターンマッチの重要性を認識してもらうのが狙いだ。なお、詳細な仕様についてはマニュアルを参照されたい。 なぜパターンマッチなのか Common Lispにはパターンマッチライブラリが多数存在するが、その大半は単にパターンマッチが便利だからという視点しか持っていない。たしかにパターンマッチは便利であるが、便利なだけでは人々はそれを使おうとはしない。より本質的な視点を与える必要があるだろう。 OCamlやHaskellなどの関数型言語では、あらゆるデータは、代数的データ型として定義され、それにともなうデータコンストラクタによって構成される
Left-Leaning Red-Black Trees Considered Harmful Eddie Kohler Robert Sedgewick’s left-leaning red-black trees are supposedly simpler to implement than normal red-black trees: In this paper, we describe a new variant of red-black trees that meets many of the original design goals and leads to substantially simpler code for insert/delete, less than one-fourth as much code as in implementations in com
Balanced Trees, Part 4: Left Leaning Red-Black Trees Overview While searching around for info about balanced trees, I found some new papers by Robert Sedgewick, describing an algorithm called Left Leaning Red-Black (LLRB) trees. Since Sedgewick (along with Guibas back in 1978) helped come up with the abstraction for red-black trees, I assumed this would be a good algorithm to test. However... Ther
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く