This HTML5 document contains 53 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dcthttp://purl.org/dc/terms/
template-enhttp://ja.dbpedia.org/resource/Template:
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
dbpedia-wikidatahttp://wikidata.dbpedia.org/resource/
rdfshttp://www.w3.org/2000/01/rdf-schema#
n12http://people.ksp.sk/~kuko/bak/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
n8http://ja.dbpedia.org/resource/Category:
n10http://ja.wikipedia.org/wiki/
n13http://opendatastructures.org/versions/edition-0.1g/ods-python/
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
dbpedia-jahttp://ja.dbpedia.org/resource/
prop-enhttp://ja.dbpedia.org/property/
n4http://publications.csail.mit.edu/lcs/pubs/pdf/

Statements

Subject Item
dbpedia-wikidata:Q3566140
owl:sameAs
dbpedia-ja:スケープゴート木
Subject Item
dbpedia-ja:スケープゴート木
rdfs:label
スケープゴート木
rdfs:comment
スケープゴートツリーは計算機科学における平衡二分探索木の一種である。Arne Anderssonと、Igal Galperinとロナルド・リベストによって発明された。探索、挿入、削除の償却時間計算量がO(log n)であり、探索においては最悪時間計算量もO(log n)である。 探索の最悪時間計算量がO(log n)である他の平衡二分探索木と異なる特徴として、スケープゴート木はノードごとに新たな要素を持たないため、メモリオーバーヘッドがない。つまり、ノードはキーと左右の子を指す2つのポインタのみを保存する。この性質によって、スケープゴート木の実装が容易になる上、データ構造アライメントによりノードのオーバーヘッドを最大3分の1に削減できる。 多くの平衡木は、平衡を維持するために何度も簡単な処理を呼ぶが、スケープゴート木は複雑な処理を低確率で呼ぶという違いがある。スケープゴート木では平衡を維持するために、「スケープゴート」と呼ばれる特定のノードを根とする部分木を完全二分木として再構築する。したがって、スケープゴート木の更新の時間計算量は、最悪の場合O (n)である。
dct:subject
n8:償却データ構造 n8:探索木 n8:二分木
dbo:wikiPageID
4202378
dbo:wikiPageRevisionID
79321833
dbo:wikiPageWikiLink
dbpedia-ja:ランダウの記号 dbpedia-ja:ロナルド・リベスト n8:二分木 dbpedia-ja:聖書 dbpedia-ja:計算機科学 dbpedia-ja:二分木 dbpedia-ja:赤黒木 dbpedia-ja:データ構造アライメント dbpedia-ja:木構造_(データ構造) dbpedia-ja:平衡二分探索木 dbpedia-ja:木の回転 n8:探索木 dbpedia-ja:Massachusetts_Institute_of_Technology dbpedia-ja:参照の局所性 n8:償却データ構造 dbpedia-ja:スプレー木 dbpedia-ja:B木 dbpedia-ja:AVL木
dbo:wikiPageExternalLink
n4:MIT-LCS-TR-700.pdf%7Ctitle=On n12:index.html n13:ods-python-html.html%7Cedition=0.1G n13:8_Scapegoat_Trees.html%7Ctitle=Open
prop-en:wikiPageUsesTemplate
template-en:Cite_thesis template-en:Reflist template-en:Cite_book template-en:Infobox_data_structure
prop-en:deleteAvg
O
prop-en:deleteWorst
償却されたO
prop-en:insertAvg
O
prop-en:insertWorst
償却されたO
prop-en:inventedBy
アルネ・アンダーソン、アイガル・ガリペリン、ロナルド・リベスト
prop-en:searchAvg
O
prop-en:searchWorst
O
prop-en:spaceAvg
O
prop-en:spaceWorst
O
prop-en:name
Scapegoat tree
prop-en:type
木
dbo:abstract
スケープゴートツリーは計算機科学における平衡二分探索木の一種である。Arne Anderssonと、Igal Galperinとロナルド・リベストによって発明された。探索、挿入、削除の償却時間計算量がO(log n)であり、探索においては最悪時間計算量もO(log n)である。 探索の最悪時間計算量がO(log n)である他の平衡二分探索木と異なる特徴として、スケープゴート木はノードごとに新たな要素を持たないため、メモリオーバーヘッドがない。つまり、ノードはキーと左右の子を指す2つのポインタのみを保存する。この性質によって、スケープゴート木の実装が容易になる上、データ構造アライメントによりノードのオーバーヘッドを最大3分の1に削減できる。 多くの平衡木は、平衡を維持するために何度も簡単な処理を呼ぶが、スケープゴート木は複雑な処理を低確率で呼ぶという違いがある。スケープゴート木では平衡を維持するために、「スケープゴート」と呼ばれる特定のノードを根とする部分木を完全二分木として再構築する。したがって、スケープゴート木の更新の時間計算量は、最悪の場合O (n)である。
dbo:wikiPageLength
8119
prov:wasDerivedFrom
n10:スケープゴート木?oldid=79321833&ns=0
foaf:isPrimaryTopicOf
n10:スケープゴート木
Subject Item
dbpedia-ja:二分探索木
dbo:wikiPageWikiLink
dbpedia-ja:スケープゴート木
Subject Item
dbpedia-ja:平衡二分探索木
dbo:wikiPageWikiLink
dbpedia-ja:スケープゴート木
Subject Item
dbpedia-ja:木構造_(データ構造)
dbo:wikiPageWikiLink
dbpedia-ja:スケープゴート木
Subject Item
n10:スケープゴート木
foaf:primaryTopic
dbpedia-ja:スケープゴート木