[B! red-black tree][index] yassのブックマーク

yass id:yass

red-black treeとindexに関するyassのブックマーク (2)

Left-leaning Red-Black Trees - やた＠はてな日記
いろいろなところで引用されています．実装が楽な赤黒木で，以下のスライドを見れば（むしろ，ほとんどコピーする感じで），簡単に実装できます．論文 http://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf スライド http://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.pdf 以下は，少し普通じゃない感じで，とりあえず追加のみを実装してみたものです．64 ビット環境だとポインタに割り当てられる領域も無視できないことがあったりなかったり，という思いが反映されています．ただし，試作品なので少しだけ…． template <typename ValueType, typename IndexType = unsigned, typename LessThanType = less<ValueType>,
yass 2013/04/28
red-black tree

index

tree
リンク
DO++: 左傾赤黒木
漢字で書くと仰々しいが、赤黒木 (wikipedia) red-black tree (english wikipedia)という平衡二分木で最も多くつかわれているデータ構造の、改善版が出てたそうだ。 left-leaning red-black tree (pdf) 日本語に訳すと左傾赤黒木かな。簡単な漢字を並べている感じがしてしまう赤黒木の詳細については、wikipediaなどをよんでもらうとして、これは更新時間が定数で更新箇所が局所的（これはマルチスレッドとかでロックする箇所をかなり細かい単位で、できるという強い利点もある）のだが、実装が結構面倒くさい。例えばC++ stl のmapとかの赤黒木の実装のstl_tree.h(google code search)は大変なことになっている（特にRb_tree_rebalance_for_eraseとか）赤黒木というのは動的データ構造
yass 2013/04/21
algorithm

btree

red-black tree

skip list

index
リンク
1