In computer science, a scapegoat tree is a self-balancing binary search tree, invented by in 1989 and again by and Ronald L. Rivest in 1993. It provides worst-case lookup time (with as the number of entries) and amortized insertion and deletion time. Instead of the small incremental rebalancing operations used by most balanced tree algorithms, scapegoat trees rarely but expensively choose a "scapegoat" and completely rebuild the subtree rooted at the scapegoat into a complete binary tree. Thus, scapegoat trees have worst-case update performance.
| Attributes | Values |
|---|
| type
| |
| label
| - Scapegoat tree
- Arbre bouc-émissaire
- Scapegoat strom
- スケープゴート木
- 替罪羊树
|
| comment
| - En informatique, plus précisément en algorithmique, un arbre bouc-émissaire est un arbre binaire de recherche auto-équilibrant. Ce type d'arbre a été inventé en 1989 par Arne Andersson, puis réinventé en 1993 par Igal Galperin et Ronald L. Rivest. Contrairement à la plupart des autres arbres auto-équilibrants, l'arbre bouc-émissaire se restructure plus rarement. Ainsi, la structure de l'arbre se déséquilibre peu à peu, jusqu'au moment où l'algorithme désigne un nœud bouc-émissaire, désigné comme responsable du déséquilibre. On y effectue alors un rééquilibrage pour que l'arbre retrouve une structure satisfaisante.
- スケープゴートツリーは計算機科学における平衡二分探索木の一種である。Arne Anderssonと、Igal Galperinとロナルド・リベストによって発明された。探索、挿入、削除の償却時間計算量がO(log n)であり、探索においては最悪時間計算量もO(log n)である。 探索の最悪時間計算量がO(log n)である他の平衡二分探索木と異なる特徴として、スケープゴート木はノードごとに新たな要素を持たないため、メモリオーバーヘッドがない。つまり、ノードはキーと左右の子を指す2つのポインタのみを保存する。この性質によって、スケープゴート木の実装が容易になる上、データ構造アライメントによりノードのオーバーヘッドを最大3分の1に削減できる。 多くの平衡木は、平衡を維持するために何度も簡単な処理を呼ぶが、スケープゴート木は複雑な処理を低確率で呼ぶという違いがある。スケープゴート木では平衡を維持するために、「スケープゴート」と呼ばれる特定のノードを根とする部分木を完全二分木として再構築する。したがって、スケープゴート木の更新の時間計算量は、最悪の場合O (n)である。
- 替罪羊树是電腦科學中，一种基于部分重建的自平衡二叉搜索树。在替罪羊树上，插入或删除节点的平攤最壞時間複雜度是，搜索节点的最壞時間複雜度是。 在非平衡的二叉搜索树中，每次操作以后检查操作路径，找到最高的满足的结点，重建整个子树。这样就得到了替罪羊树，而被重建的子树的原来的根就被称为替罪羊节点。常数一般选择为左右。 与大多数平衡树所采用的缓慢调整的方式不同，替罪羊树采用了一种进行次数较少但代价较大的重构操作，即选择一个节点作为“替罪羊”，并将这个节点的子树直接重构成完全二叉树。因此，替罪羊树的最坏时间复杂度为
- Scapegoat strom (z angl. slova scapegoat – obětní beránek) je jeden z binárních vyhledávacích stromů. Nezávisle na sobě ho vymysleli a . Je implementován tak, že používá standardní algoritmy pro vkládání záznamů do nevyváženého stromu a v případě, že je to třeba, je strom při poslední operaci znovu vyvážen. Složitost při vyhledávání je v nejhorším případě a amortizovaná složitost vkládání a mazání je také . Jeho největší výhodou je paměťová nenáročnost, na rozdíl od většiny vyvažovaných vyhledávacích stromů nepotřebuje ve vrcholech informace navíc.
- In computer science, a scapegoat tree is a self-balancing binary search tree, invented by in 1989 and again by and Ronald L. Rivest in 1993. It provides worst-case lookup time (with as the number of entries) and amortized insertion and deletion time. Instead of the small incremental rebalancing operations used by most balanced tree algorithms, scapegoat trees rarely but expensively choose a "scapegoat" and completely rebuild the subtree rooted at the scapegoat into a complete binary tree. Thus, scapegoat trees have worst-case update performance.
|
| sameAs
| |
| name
| |
| topic
| |
| described by
| |
| Subject
| |
| dbo:wikiPageID
| |
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbo:wikiPageExternalLink
| |
| is primary topic of
| |
| dbp:inventedBy
| |
| dbp:inventedYear
| |
| wasDerivedFrom
| |
| http://purl.org/li...ics/gold/hypernym
| |
| dbo:abstract
| - En informatique, plus précisément en algorithmique, un arbre bouc-émissaire est un arbre binaire de recherche auto-équilibrant. Ce type d'arbre a été inventé en 1989 par Arne Andersson, puis réinventé en 1993 par Igal Galperin et Ronald L. Rivest. Contrairement à la plupart des autres arbres auto-équilibrants, l'arbre bouc-émissaire se restructure plus rarement. Ainsi, la structure de l'arbre se déséquilibre peu à peu, jusqu'au moment où l'algorithme désigne un nœud bouc-émissaire, désigné comme responsable du déséquilibre. On y effectue alors un rééquilibrage pour que l'arbre retrouve une structure satisfaisante.
- In computer science, a scapegoat tree is a self-balancing binary search tree, invented by in 1989 and again by and Ronald L. Rivest in 1993. It provides worst-case lookup time (with as the number of entries) and amortized insertion and deletion time. Unlike most other self-balancing binary search trees which also provide worst case lookup time, scapegoat trees have no additional per-node memory overhead compared to a regular binary search tree: besides key and value, a node stores only two pointers to the child nodes. This makes scapegoat trees easier to implement and, due to data structure alignment, can reduce node overhead by up to one-third. Instead of the small incremental rebalancing operations used by most balanced tree algorithms, scapegoat trees rarely but expensively choose a "scapegoat" and completely rebuild the subtree rooted at the scapegoat into a complete binary tree. Thus, scapegoat trees have worst-case update performance.
- スケープゴートツリーは計算機科学における平衡二分探索木の一種である。Arne Anderssonと、Igal Galperinとロナルド・リベストによって発明された。探索、挿入、削除の償却時間計算量がO(log n)であり、探索においては最悪時間計算量もO(log n)である。 探索の最悪時間計算量がO(log n)である他の平衡二分探索木と異なる特徴として、スケープゴート木はノードごとに新たな要素を持たないため、メモリオーバーヘッドがない。つまり、ノードはキーと左右の子を指す2つのポインタのみを保存する。この性質によって、スケープゴート木の実装が容易になる上、データ構造アライメントによりノードのオーバーヘッドを最大3分の1に削減できる。 多くの平衡木は、平衡を維持するために何度も簡単な処理を呼ぶが、スケープゴート木は複雑な処理を低確率で呼ぶという違いがある。スケープゴート木では平衡を維持するために、「スケープゴート」と呼ばれる特定のノードを根とする部分木を完全二分木として再構築する。したがって、スケープゴート木の更新の時間計算量は、最悪の場合O (n)である。
- 替罪羊树是電腦科學中，一种基于部分重建的自平衡二叉搜索树。在替罪羊树上，插入或删除节点的平攤最壞時間複雜度是，搜索节点的最壞時間複雜度是。 在非平衡的二叉搜索树中，每次操作以后检查操作路径，找到最高的满足的结点，重建整个子树。这样就得到了替罪羊树，而被重建的子树的原来的根就被称为替罪羊节点。常数一般选择为左右。 与大多数平衡树所采用的缓慢调整的方式不同，替罪羊树采用了一种进行次数较少但代价较大的重构操作，即选择一个节点作为“替罪羊”，并将这个节点的子树直接重构成完全二叉树。因此，替罪羊树的最坏时间复杂度为
- Scapegoat strom (z angl. slova scapegoat – obětní beránek) je jeden z binárních vyhledávacích stromů. Nezávisle na sobě ho vymysleli a . Je implementován tak, že používá standardní algoritmy pro vkládání záznamů do nevyváženého stromu a v případě, že je to třeba, je strom při poslední operaci znovu vyvážen. Složitost při vyhledávání je v nejhorším případě a amortizovaná složitost vkládání a mazání je také . Jeho největší výhodou je paměťová nenáročnost, na rozdíl od většiny vyvažovaných vyhledávacích stromů nepotřebuje ve vrcholech informace navíc.
|
| dbp:type
| |
| dbo:wikiPageLength
| |
| dbp:wikiPageUsesTemplate
| |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
