untitled
概要 探索 • 逐次探索 • ２分探索 • 探索とデータ管理 – ２分探索木 – 平衡木 (Balanced tree) ここ 探索木と効率 ２分探索木 探索、挿入、削除の効率は木の形状に依存する 平衡木 最悪の場合が生じないように木を構成する バランスのとれた木構造 – – – – 平衡2分木 ( AVL木 ) 2-3木 2-3-4木 ( トップダウン2-3-4木 ) Red-Black 木( 2色木、赤黒木 ) ＊AVL木 : Adel‘son-VelskiiとLandis が提案した木 平衡２分木、 2-3 木 平衡２分木 ( AVL 木 ) バランスのほぼとれた２分木 – 子の個数が１以下のノードのレベルの差が１以下 レコードの挿入、削除時にバランスをチェック バランスがとれていなければ、木の形状を修正 2-3-4木、Red-Black木 2-3-4木 子ノードの個数が４個
Red–black tree - Wikipedia
Example of a red-black tree In computer science, a red–black tree is a self-balancing binary search tree data structure noted for fast storage and retrieval of ordered information. The nodes in a red-black tree hold an extra "color" bit, often drawn as red and black, which help ensure that the tree is always approximately balanced.[1] When the tree is modified, the new tree is rearranged and "repa
赤黒木 - Wikipedia
赤黒木（あかくろぎ）は、コンピュータ科学のデータ構造である平衡二分木の一種で、主に連想配列の実装に用いられている。2色木、レッド・ブラック・ツリーともいう。 このデータ構造は1972年のルドルフ・ベイヤー (en:Rudolf Bayer) の発明である"symmetric binary B-trees"が元となっており、赤黒木という名前自体は 1978年にレオニダス・ギッバス (en:Leonidas J. Guibas) とロバート・セジウィック (en:Robert Sedgewick) によって発表された論文による。 赤黒木は、探索、挿入、削除などの操作における最悪時間計算量がO(log n)（nは木の要素数）と短く、複雑ではあるが実用的なデータ構造として知られている。 この日本語版は概要のみの解説であり、具体的なアルゴリズムはwikipedia英語版(Red-black_tree
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
サービス終了のお知らせ
