Scapegoat tree
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.
Wikipage disambiguates
primaryTopic
Scapegoat tree
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.
has abstract
En informatique, plus précisém ...... e une structure satisfaisante.
@fr
Scapegoat strom (z angl. slova ...... ve vrcholech informace navíc.
@cs
スケープゴートツリーは計算機科学における平衡二分探索木の一種 ...... プゴート木の更新の時間計算量は、最悪の場合O (n)である。
@ja
替罪羊树是電腦科學中，一种基于部分重建的自平衡二叉搜索树。在 ...... 的子树直接重构成完全二叉树。因此，替罪羊树的最坏时间复杂度为
@zh
Link from a Wikipage to an external page
Wikipage page ID
page length (characters) of wiki page
Wikipage revision ID
1,011,744,463
Link from a Wikipage to another Wikipage
delete avg
O
@en
delete worst
amortized O
@en
insert avg
O
@en
insert worst
amortized O
@en
name
Scapegoat tree
@en
search avg
O
@en
search worst
O
@en
space avg
O
@en
space worst
O
@en
type
tree
@en
wikiPageUsesTemplate
hypernym
type
comment
En informatique, plus précisém ...... e une structure satisfaisante.
@fr
Scapegoat strom (z angl. slova ...... ve vrcholech informace navíc.
@cs
スケープゴートツリーは計算機科学における平衡二分探索木の一種 ...... プゴート木の更新の時間計算量は、最悪の場合O (n)である。
@ja
替罪羊树是電腦科學中，一种基于部分重建的自平衡二叉搜索树。在 ...... 的子树直接重构成完全二叉树。因此，替罪羊树的最坏时间复杂度为
@zh
label
Arbre bouc-émissaire
@fr
Scapegoat strom
@cs
Scapegoat tree
@en
スケープゴート木
@ja
替罪羊树
@zh