・二分探索木 (binary search tree) ・AVL tree ・B-tree ・B+ tree について順を追いながら説明。 流れを細かく書いたので、わかりやすいと思います。
これでわかるB-treeアルゴリズム / B-tree algorithm
・二分探索木 (binary search tree) ・AVL tree ・B-tree ・B+ tree について順を追いながら説明。 流れを細かく書いたので、わかりやすいと思います。
回転をサボるAVL木を落とす - Qiita
この記事では$N$を二分探索木中の要素数(ノード数)として以後断りなく用います。 今回はAVL木をsetのような平衡二分探索木として扱いますが、配列型(平衡二分木)として使ってもほとんど同じことがいえます。 前提知識 二分探索木について (分かってると嬉しい) : AVL木の平衡方法 正しい平衡 ノードの平衡係数は(左の子の高さ) $-$ (右の子の高さです)。 説明によっては一重回転をやるケースと二重回転をやるケースとを完全に別のものとして区別していますが、二重回転は一重回転を2回やってるだけで、かつその2回目が一重回転をやるケースの一重回転と一致するので以下のように実装することができます。 ノード$x$の平衡係数が2の場合 $x$の左の子の平衡係数が-1なら左の子を左回転 $x$を右回転 ノード$x$の平衡係数が-2の場合(上の全く左右対称) $x$の右の子の平衡係数が1なら右の子を右
Centroid Path Decompositionを使ったトライでダブル配列と勝負してみた - Preferred Networks Research & Development
釣りタイトルを付けたかったのですがさっぱり思いつかないのでもう諦めました。徳永です。 今回はCentroid Path Decomposition（以下CPD）についての話を書きます。直訳すると重心パス分解となるでしょうか。Trieを実現するためのテクニック（普通のツリーにも使えるのかな？なかなか難しそうですが…）の一つです。CPDは一年前の弊社岡野原の記事に出てきますが、私のような素人にはあれだけでは理解できない部分があったので、今回はちょっと論文を読んでみました。 Trieの実装によくある問題 Trieを実現するためのデータ構造というとダブル配列とかが挙げられますが、こういった高速なデータ構造にも、ランダムアクセスが多いという弱点があります。メモリはHDDなどと比べるとランダムアクセスに耐えうる記憶媒体ですが、とは言えランダムアクセスは避けられるに越したことはありません。CPDを使うこ
最近のDoubleArrayの性能 - 射撃しつつ前転 改
DoubleArrayの性能に関して、最近は少し改善されているかも知れませんとあるので、具体的にどれぐらい改善されているのか、少し書いてみます。もちろん、現実逃避です。 まず、DoubleArrayがなんなのかというところから説明をします。DoubleArrayは、簡単に言うとTrieを実現するためのデータ構造の一種です。日本語ではダブル配列と呼ばれているようです。Trieに関しては横着プログラミング 第6回: chatty: 小うるさい端末あたりを読めば良いでしょうか。要するにTreeを表現するためのデータ構造です。使い道はいろいろありますが、辞書的なものに使われることが多いでしょうか。 Trieを単純に実現しようとすると、すごくたくさんメモリを使ってすごく速い実装をするか、速度を多少犠牲にしてメモリ消費量を削減するかの選択を迫られます。多くの場合はメモリを節約しないと使いものにならない
簡潔データ構造 LOUDS の解説（全12回、練習問題付き）
「日本語入力を支える技術」（通称「徳永本」）や「高速文字列解析の世界」（通称「岡野原本」）で紹介されている LOUDS というデータ構造を、12回に分けて解説しました。 友達に教える時に使ったもので、練習問題付きです。 実際に紙に書いてやってみるとわかりやすいと思います。 詳解 LOUDS (1) LOUDS とは 詳解 LOUDS (2) ビット列を作ってみる 詳解 LOUDS (3) 0番ノード 詳解 LOUDS (4) ビットの意味 詳解 LOUDS (5) 木構造の復元 詳解 LOUDS (6) インデックスでノードを表す 詳解 LOUDS (7) ノード番号からインデックスを得る 詳解 LOUDS (8) インデックスからノード番号を得る 詳解 LOUDS (9) 子ノードから親ノード 詳解 LOUDS (10) 親ノードから子ノード 詳解 LOUDS (11) 木の検索 詳解
LOUDS(Level-Order Unary Degree Sequence)を調べたのでメモ - EchizenBlog-Zwei
最近よく目にするLOUDS(Level-Order Unary Degree Sequence)というのが気になっていたので調べた。実は最初に提案されたのは1989年。結構昔からあったと知ってびっくり。 Space-efficient Static Trees and Graphs G. Jacobson, 1989 LOUDSというのは木構造を表現するデータ構造をひとつ。単純に考えると木構造を実装するにはノードを表すオブジェクトに子ノードへのポインタを持たせる、というものが思いつく。この実装はノードへのアクセスは効率的にできるけれどメモリをたくさん使ってしまう(O(NlogN))。 そこでノードへのアクセス効率をあまり悪くせずに、省メモリな木構造が欲しい。これを実現したのがLOUDS。LOUDSはノードの追加や削除が起きないstaticな木構造にしか使えないが、必要なメモリはO(N)で済
情報系修士にもわかるLOUDS - アスペ日記
一回でわかりやすく書くのは難しいので、簡潔データ構造 LOUDS の解説（全12回、練習問題付き）というシリーズにまとめました。 (2014/01/26) 古い内容を削除しました。
An Implementation of Double-Array Trie
Contents What is Trie? What Does It Take to Implement a Trie? Tripple-Array Trie Double-Array Trie Suffix Compression Key Insertion Key Deletion Double-Array Pool Allocation An Implementation Download Other Implementations References What is Trie? Trie is a kind of digital search tree. (See [Knuth1972] for the detail of digital search tree.) [Fredkin1960] introduced the trie terminology, which is
SegmentTreeの練習として良さそうなやつ - tozangezan's diary
id:kyuridenamidaに便乗してSegmentTreeで出来る問題たちをここに挙げておきます。 「良さそうなやつ」とか書いていますが単にSegmentTreeで解いた問題たちを並べておくだけです。残念。(解けないけどSegmentTreeと聞いているものも入れてあります) BITでかけるものもあるので、そういう問題はどっちで解いても良いと思います(多分BITのほうが定数が小さいです) あと、多分SegmentTree(もしくはBIT)を使わなくても解ける問題が入っているかもしれませんが、それはしかたがないです。少なくとも僕はこれらの問題をSegmentTreeかBITで解いています。 PKU 1631 Bridging signals 1986 Distance Queries 2019 Cornfields 2104 K-th Number 2373 Dividing the
セグメント木 問題集 - hogloidのブログ
https://twitter.com/hogloid/status/284225774142251008 こんなことを言ったので 書きます 問題は、セグメント木を使う解法がおそらく楽で、セグメント木が問題の重要な部分で、JOIとかPCKでない問題、とします（JOIの問題とかみんな知ってる&解いてるだろうし） あと、明確に悪問と分かる問題は載せません。 解説が欲しい場合は、(一応僕は全部解いたので)僕になにか言ってくれると解説ページを開設すると思います。下のコメント欄とかにどうぞ。 記事を出してからも、ボチボチ更新していく予定です。 ☆の数は、主観的な難易度です。 書き終わって気づきましたがかなりグロイ問題ばかりなのでやばいですが頑張ってください 似たような記事 http://d.hatena.ne.jp/tozangezan/20111111/1320993464 (こっちのほうが、おそ
Segment Trees
Motivational Problems: http://www.spoj.pl/problems/BRCKTS/ http://www.spoj.com/problems/GSS3/ http://www.spoj.com/problems/HORRIBLE http://www.spoj.pl/problems/IOPC1207/ https://www.spoj.com/problems/GSS2/ http://www.spoj.com/problems/SEGSQRSS/ http://www.spoj.com/problems/ORDERSET/ http://www.spoj.com/problems/HELPR2D2/ http://www.spoj.com/problems/TEMPLEQ Segment trees (shortened as segtrees), a
Introduction to Segment Tree - Lilliput Steps
こんにちは, kagamiz(@kagamiz) です! この記事は, Competitive Programming Advent Calendar Div2012 18日目の記事として書かれました. この記事では, ぼくが気に入っているデータ構造であるセグメント木について, 説明と問題演習・問題紹介を交えながら紹介していきたいと思います. RMQ(Range Minimum Query)を処理するセグメント木はわかるけど, そこから応用するのが難しい...という方向けに書いていきます. 説明の章の先頭には, 水色の★もしくは黄色の★をつけています. ★は「プログラミングコンテストチャレンジブック」などでも触れられている事項で, ★はそうでない事項を指します. 演習問題の先頭には★マークをつけていますが, ★は基本的な問題, ★はやや難しい問題として示しています. 概要についてですが,
問題 I : 乱択平衡二分探索木
東京大学プログラミングコンテスト 2011 問題 L : 𝐿 番目の数字 東京大学大学院情報理工学系研究科 秋葉 拓哉 2011/05/14 東京大学駒場キャンパス 問題概要 • 各ノードに数字が決まってるツリーがある • 以下のタイプのクエリを大量に処理: ある頂点 𝒗 から 𝒘 への経路上の数字で， 𝒍 番目に小さい物を求めよ 頂点番号 頂点 1 に決ま っている数字 例: 頂点 1 から頂点 6 への経路での，3 番目 → 2, 5, 8, 7 の 3 番目 → 7 が答え 問題を変形 • 頂点 1 を根にして，向き付きの木にする • 以下を効率的に計算できるか？ 頂点 𝒗 から根までで 𝒙 以下が何個あるか？ 例: 頂点 4 から根に 6 以下は何個あるか？ → 8, 5, 2 に 6 以下は何個あるか？ → 2 個 それができると？ • それができると，任意の 2 頂
僕のセグメントツリーの使い方 - kyuridenamidaのチラ裏
セグメントツリーは、"できるだけ大きい区間で取って誤魔化す"のも大切ですが、それに加えて"遅延評価"をかなり意識すればいろんな木が簡単に特に思考なしでかけるイメージがあります。ちなみにここから説明するセグメントツリーは少し弄るだけで色んな変形が出来るのですきですが、冗長なので定数倍遅いです。ごめんなさい。 #include using namespace std; #define N (117) // update(l,r,v) := [l,r]の区間に対してvを一様に足す. k,a,bは飾り struct NODE{ int sum;//更新された値. この値を参照する時は評価が完全に完了しているようにする. int lazy; //遅延されている値を保存している NODE(){ sum = lazy = 0; } }; NODE seg[2*N]; // inlineつけないと大変
RMQ, LCAいろいろ - komiyamの日記
こことか蟻本を参考にして、色々実装を試してみた。 RMQ まず、インターフェースをはっきりさせよう。とりあえずD言語で書くけど、そこまで言語依存な書き方はしていないのですぐにC++なりJavaなりに移せるはず。D言語とかコンテストでは大抵使えないし言語仕様がまた変わるかもしれないのでそのうち自分でC++に書き直すと思う。それと全部未検証なことに注意。簡単なケースでしか試してない。 追記 いくつかバグを発見したのでそのうち修正する //気分的にはこんな感じ。 class RangeMinimumQuery(T, alias less = "a < b"){ this(); //RMQをビルドする this(in T[] xs); build(in T[] xs); //半開区間 [from, to)において最小値を与えるindexを返す //複数ある場合はもっとも若いindexを返す int
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
ダブル配列の実装方法
Google Code Archive - Long-term storage for Google Code Project Hosting.
http://wwwisg.cs.uni-magdeburg.de/ag/lehre/SS2009/GDS/slides/S11.pdf
Segment Tree - Codeforces