About DBpedia

About: 赤黒木

An Entity of Type : Thing, from Named Graph : http://ja.dbpedia.org, within Data Space : ja.dbpedia.org

赤黒木（あかくろぎ）は、コンピュータ科学のデータ構造である平衡二分木の一種で、主に連想配列の実装に用いられている。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)に掲載されている。

thumbnail
Property Value
dbo:abstract
  • 赤黒木（あかくろぎ）は、コンピュータ科学のデータ構造である平衡二分木の一種で、主に連想配列の実装に用いられている。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)に掲載されている。 (ja)
  • 赤黒木（あかくろぎ）は、コンピュータ科学のデータ構造である平衡二分木の一種で、主に連想配列の実装に用いられている。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)に掲載されている。 (ja)
dbo:thumbnail
dbo:wikiPageExternalLink
dbo:wikiPageID
  • 551726 (xsd:integer)
dbo:wikiPageLength
  • 30882 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID
  • 92058296 (xsd:integer)
dbo:wikiPageWikiLink
prop-en:align
  • left (ja)
  • right (ja)
  • left (ja)
  • right (ja)
prop-en:caption
  • 図2: 左右の暗黙のドッキングポイントを持つ赤黒木 (ja)
  • (上位の反復) (ja)
  • (最初の反復) (ja)
  • 図1: 明示的な葉を持つ赤黒木 (ja)
  • 図2: 左右の暗黙のドッキングポイントを持つ赤黒木 (ja)
  • (上位の反復) (ja)
  • (最初の反復) (ja)
  • 図1: 明示的な葉を持つ赤黒木 (ja)
prop-en:date
  • 20160501205829 (xsd:decimal)
prop-en:deleteAvg
prop-en:direction
  • vertical (ja)
  • vertical (ja)
prop-en:footer
  • 削除ケース1 (ja)
  • 削除ケース3 (ja)
  • 削除ケース4 (ja)
  • 削除ケース5 (ja)
  • 削除ケース6 (ja)
  • 挿入ケース2 (ja)
  • 挿入ケース5 (ja)
  • 挿入ケース6 (ja)
  • 削除ケース1 (ja)
  • 削除ケース3 (ja)
  • 削除ケース4 (ja)
  • 削除ケース5 (ja)
  • 削除ケース6 (ja)
  • 挿入ケース2 (ja)
  • 挿入ケース5 (ja)
  • 挿入ケース6 (ja)
prop-en:header
  • [[#explan (ja)
  • 赤黒木の例 (ja)
  • [[#explan (ja)
  • 赤黒木の例 (ja)
prop-en:headerAlign
  • center (ja)
  • center (ja)
prop-en:image
  • Red-black tree example with sockets.svg (ja)
  • Red-black tree example.svg (ja)
  • Red-black_tree_delete_case_A0rot.svg (ja)
  • Red-black_tree_delete_case_A1rot.svg (ja)
  • Red-black_tree_delete_case_B0t.svg (ja)
  • Red-black_tree_delete_case_B1t.svg (ja)
  • Red-black_tree_delete_case_C0.svg (ja)
  • Red-black_tree_delete_case_C1.svg (ja)
  • Red-black_tree_delete_case_D0rot.svg (ja)
  • Red-black_tree_delete_case_D1rot.svg (ja)
  • Red-black_tree_delete_case_E0rot.svg (ja)
  • Red-black_tree_delete_case_E1rot.svg (ja)
  • Red-black_tree_insert_case_B0t.svg (ja)
  • Red-black_tree_insert_case_B1t.svg (ja)
  • Red-black_tree_insert_case_C0.svg (ja)
  • Red-black_tree_insert_case_C1.svg (ja)
  • Red-black_tree_insert_case_D0rot.svg (ja)
  • Red-black_tree_insert_case_D1rot.svg (ja)
  • Red-black_tree_perpendic_419_en.svg (ja)
  • Red-black_tree_perpendic_579_en.svg (ja)
  • Red-black_tree_perpendic_639_en.svg (ja)
  • Red-black_tree_perpendic_639era_en.svg (ja)
  • Red-black_tree_perpendic_799_en.svg (ja)
  • Red-black_tree_perpendic_919_en.svg (ja)
  • Red-black tree example with sockets.svg (ja)
  • Red-black tree example.svg (ja)
  • Red-black_tree_delete_case_A0rot.svg (ja)
  • Red-black_tree_delete_case_A1rot.svg (ja)
  • Red-black_tree_delete_case_B0t.svg (ja)
  • Red-black_tree_delete_case_B1t.svg (ja)
  • Red-black_tree_delete_case_C0.svg (ja)
  • Red-black_tree_delete_case_C1.svg (ja)
  • Red-black_tree_delete_case_D0rot.svg (ja)
  • Red-black_tree_delete_case_D1rot.svg (ja)
  • Red-black_tree_delete_case_E0rot.svg (ja)
  • Red-black_tree_delete_case_E1rot.svg (ja)
  • Red-black_tree_insert_case_B0t.svg (ja)
  • Red-black_tree_insert_case_B1t.svg (ja)
  • Red-black_tree_insert_case_C0.svg (ja)
  • Red-black_tree_insert_case_C1.svg (ja)
  • Red-black_tree_insert_case_D0rot.svg (ja)
  • Red-black_tree_insert_case_D1rot.svg (ja)
  • Red-black_tree_perpendic_419_en.svg (ja)
  • Red-black_tree_perpendic_579_en.svg (ja)
  • Red-black_tree_perpendic_639_en.svg (ja)
  • Red-black_tree_perpendic_639era_en.svg (ja)
  • Red-black_tree_perpendic_799_en.svg (ja)
  • Red-black_tree_perpendic_919_en.svg (ja)
prop-en:insertAvg
prop-en:inventedBy
  • :en:Rudolf Bayer (ja)
  • :en:Rudolf Bayer (ja)
prop-en:inventedYear
  • 1972 (xsd:integer)
prop-en:name
  • 赤黒木 (ja)
  • 赤黒木 (ja)
prop-en:state
  • expanded (ja)
  • expanded (ja)
prop-en:title
  • 情報処理概論 (ja)
  • 情報処理概論 (ja)
prop-en:type
prop-en:url
prop-en:width
  • 12 (xsd:integer)
  • 85 (xsd:integer)
  • 95 (xsd:integer)
  • 113 (xsd:integer)
  • 121 (xsd:integer)
  • 128 (xsd:integer)
  • 129 (xsd:integer)
  • 156 (xsd:integer)
  • 500 (xsd:integer)
prop-en:wikiPageUsesTemplate
dct:subject
rdfs:comment
  • 赤黒木（あかくろぎ）は、コンピュータ科学のデータ構造である平衡二分木の一種で、主に連想配列の実装に用いられている。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)に掲載されている。 (ja)
  • 赤黒木（あかくろぎ）は、コンピュータ科学のデータ構造である平衡二分木の一種で、主に連想配列の実装に用いられている。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)に掲載されている。 (ja)
rdfs:label
  • 赤黒木 (ja)
  • 赤黒木 (ja)
owl:sameAs
prov:wasDerivedFrom
foaf:depiction
foaf:isPrimaryTopicOf
is dbo:wikiPageRedirects of
is dbo:wikiPageWikiLink of
is owl:sameAs of
is foaf:primaryTopic of
Powered by OpenLink Virtuoso    This material is Open Knowledge     W3C Semantic Web Technology     This material is Open Knowledge    Valid XHTML + RDFa
This content was extracted from Wikipedia and is licensed under the Creative Commons Attribution-ShareAlike 3.0 Unported License