Missing method: How to delete from Okasaki's red-black trees
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
Purely Functional Left-Leaning Red-Black Trees
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
Red-Black Tree by Java -- これで分かった赤黒木
このページは、マップと呼ばれるデータ構造の実装の１つである赤黒木 (２色木、red-black tree)について解説するページです。赤黒木は、要素の 挿入・削除・検索などの操作が \(O(\log n)\) の計算量で実行出来る平衡木 です(\(n\) は要素数)。赤黒木はやっていることは単純なのですが、とにかく 場合分けがたくさんあって、習得しようとしながらもくじけてしまった人も 多いのではないでしょうか？ しかし、ご安心ください。このページは場合分けを出来るだけ減らし、 挿入操作で４パターン、削除操作で８パターンさえ理解すれば赤黒木が分かる ように書かれています。削除操作に関しては、左右対称のパターンを省けば ４パターン理解すればおおむね OK です。これから赤黒木を勉強しようという人 はもちろん、一度は勉強したが挫折してしまったという人も是非とも読んでみて ください。 【準備】 ま
Common Lispで赤黒木 - 壊れた計算機
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 - 高速パターンマッチライブラリ - Qiita
開発が成熟してきたので、ここらで拙作のパターンマッチライブラリ、optimaを日本語で解説したいと思う。ただし解説とは言っても、詳細な仕様をだらだらと解説するようなことはしない。むしろ「なぜパターンマッチなのか」を踏まえた上で、簡単な入門と使用例を示すことで、パターンマッチの重要性を認識してもらうのが狙いだ。なお、詳細な仕様についてはマニュアルを参照されたい。 なぜパターンマッチなのか Common Lispにはパターンマッチライブラリが多数存在するが、その大半は単にパターンマッチが便利だからという視点しか持っていない。たしかにパターンマッチは便利であるが、便利なだけでは人々はそれを使おうとはしない。より本質的な視点を与える必要があるだろう。 OCamlやHaskellなどの関数型言語では、あらゆるデータは、代数的データ型として定義され、それにともなうデータコンストラクタによって構成される
Left-Leaning Red-Black Trees Considered Harmful
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
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
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Data.Tree.RBTree
Google
Deletion in Left Leaning Red Black Trees
Google
Left-Leaning Red-Black Tree by Java
サービス終了のお知らせ
http://www.sampou.org/cgi-bin/haskell.cgi?Programming%3A%B6%CC%BC%EA%C8%A2%3A%A4%BD%A4%CE%C2%BE
rb.h -- Red-black tree implementation
http://algs4.cs.princeton.edu/32bst/
Red Black Tree using optima in Common Lisp
https://www.cs.kent.ac.uk/people/staff/smk/redblack/
Red Black Tree for Common Lisp.
Balanced Trees, Part 5: Performance