In computer science, an in-tree or parent pointer tree is an N-ary tree data structure in which each node has a pointer to its parent node, but no pointers to child nodes. When used to implement a set of stacks, the structure is called a spaghetti stack, cactus stack or sahuaro stack (after the sahuaro, a kind of cactus). Parent pointer trees are also used as disjoint-set data structures. The structure can be regarded as a set of singly linked lists that part of their structure, in particular, their tails. From any node, one can traverse to ancestors of the node, but not to any other node.
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - Pile spaghetti (fr)
- スパゲッティスタック (ja)
- Parent pointer tree (en)
|
| rdfs:comment
| - In computer science, an in-tree or parent pointer tree is an N-ary tree data structure in which each node has a pointer to its parent node, but no pointers to child nodes. When used to implement a set of stacks, the structure is called a spaghetti stack, cactus stack or sahuaro stack (after the sahuaro, a kind of cactus). Parent pointer trees are also used as disjoint-set data structures. The structure can be regarded as a set of singly linked lists that part of their structure, in particular, their tails. From any node, one can traverse to ancestors of the node, but not to any other node. (en)
- Une pile spaghetti (ou pile cactus, pile saguaro ou in-tree) en informatique est un arbre enraciné N-aire dans lequel les nœuds fils ont un pointeur vers leur nœud père (mais pas l'inverse). Lors d'un parcours d'un nœud feuille en suivant ses ancêtres vers le nœud racine, la structure est semblable à une pile en liste chaînée. En effet, chaque nœud a un seul pointeur vers le nœud "suivant" (père), et ignore si ce père a d'autres enfants. Ni lui ni le père ne peut explorer les autres enfants, puisqu'il n'y a pas de pointeurs descendants. (fr)
- スパゲッティスタック（spaghetti stack; 他に cactus stack, saguaro stack, in-treeとも）とは、子ノードが親ノードへのポインタを持ち、親ノードは子ノードへのポインタを持たないようなN分木である。ノードのリストが親のポインタをたどって葉から親へ向かうとき、スパゲッティスタックは連結リストのスタックのように振る舞う。リンクがある連結リストと比較して、他のノード唯一の親ノードへのポインタのみをもち、それぞれの親ノードは他の子を無視する（親ノードから子ノードへのポインタが無いためどうやってもアクセスできない）。 スパゲッティスタックは実行過程のようにレコードが動的にプッシュ・ポップされるもののポップされたレコードが使用時に残るという状況で発生する。 類似のデータ構造は素集合森において見られる（素集合データ構造を参照）。 (ja)
|
| foaf:depiction
| |
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| thumbnail
| |
| has abstract
| - Une pile spaghetti (ou pile cactus, pile saguaro ou in-tree) en informatique est un arbre enraciné N-aire dans lequel les nœuds fils ont un pointeur vers leur nœud père (mais pas l'inverse). Lors d'un parcours d'un nœud feuille en suivant ses ancêtres vers le nœud racine, la structure est semblable à une pile en liste chaînée. En effet, chaque nœud a un seul pointeur vers le nœud "suivant" (père), et ignore si ce père a d'autres enfants. Ni lui ni le père ne peut explorer les autres enfants, puisqu'il n'y a pas de pointeurs descendants. Par exemple, le compilateur d'un langage tel que C crée une pile spaghetti lorsqu'il ouvre et referme des tables de symboles représentant la portée de chaque bloc. Quand un nouveau bloc est ouvert, une table de symboles est empilée. À la fin du bloc, la portée est refermée et la table de symbole est dépilée. Toutefois cette table est conservée et non détruite, et son nœud conserve un lien vers celui de la table "parente". Ainsi lorsque le compilateur effectuera la traduction de l'arbre syntaxique abstrait, pour toute expression il pourra obtenir la table de symbole correspondant à l'environnement de l'expression, et résoudre les références des identifiants. Pour une variable X au sein de l'expression, on recherche X dans la table feuille (représentant la portée la plus intérieure), puis dans son parent, puis dans son grand-parent récursivement. (fr)
- In computer science, an in-tree or parent pointer tree is an N-ary tree data structure in which each node has a pointer to its parent node, but no pointers to child nodes. When used to implement a set of stacks, the structure is called a spaghetti stack, cactus stack or sahuaro stack (after the sahuaro, a kind of cactus). Parent pointer trees are also used as disjoint-set data structures. The structure can be regarded as a set of singly linked lists that part of their structure, in particular, their tails. From any node, one can traverse to ancestors of the node, but not to any other node. (en)
- スパゲッティスタック（spaghetti stack; 他に cactus stack, saguaro stack, in-treeとも）とは、子ノードが親ノードへのポインタを持ち、親ノードは子ノードへのポインタを持たないようなN分木である。ノードのリストが親のポインタをたどって葉から親へ向かうとき、スパゲッティスタックは連結リストのスタックのように振る舞う。リンクがある連結リストと比較して、他のノード唯一の親ノードへのポインタのみをもち、それぞれの親ノードは他の子を無視する（親ノードから子ノードへのポインタが無いためどうやってもアクセスできない）。 スパゲッティスタックは実行過程のようにレコードが動的にプッシュ・ポップされるもののポップされたレコードが使用時に残るという状況で発生する。 例えばC言語のようなコンパイラはブロックスコープ表現がシンボルテーブルを開閉するようなスパゲッティスタックを作る。新たなブロックスコープが開かれた時、シンボルテーブルはスタックにプッシュされる。閉じ中括弧が検出されたとき、スコープは閉じられ、シンボルテーブルがポップされる。しかしシンボルテーブルは破壊されるのではなく記憶される。そしてもちろんスタックは親のシンボルテーブルなども記憶している。そのためコンパイラが抽象構文木についてあとで翻訳を行うとき、与えられた任意の表現に対してスパゲッティスタックはその表現の環境で表現するシンボルテーブルを呼び出すことができ、識別子への参照を解決することが出来る。もし表現が変数Xを参照するときは、それは最も内部の静的スコープを表現する葉のシンボルテーブルをまずシークし次にその親のシンボルテーブルをシークしていく。 類似のデータ構造は素集合森において見られる（素集合データ構造を参照）。 (ja)
|
| gold:hypernym
| |
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
| is Wikipage redirect
of | |
| is foaf:primaryTopic
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)
