Parent pointer tree (original) (raw)
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.
| Property | Value |
|---|---|
| dbo: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) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Spaghettistack.svg?width=300 |
| dbo:wikiPageID | 2066241 (xsd:integer) |
| dbo:wikiPageLength | 4203 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1092029872 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Scheme_(programming_language) dbr:Persistent_data_structure dbr:Burroughs_Large_Systems dbc:Metaphors_referring_to_spaghetti dbr:Compiler dbr:Cilk dbr:Closure_(computer_science) dbr:Continuation dbr:Tree_data_structure dbr:Mainframe_computers dbc:Continuations dbr:Smalltalk dbr:Stack_(abstract_data_type) dbr:Stack_frame dbr:Standard_ML_of_New_Jersey dbr:Computer_science dbr:Funarg_problem dbr:Pointer_(computer_programming) dbr:Burroughs_MCP dbr:Burroughs_large_systems dbr:C_(programming_language) dbr:Garbage_collection_(computer_science) dbr:ALGOL_60 dbr:Dynamic_memory_allocation dbr:Parent_node dbr:Abstract_syntax_tree dbc:Trees_(data_structures) dbr:Child_node dbr:Disjoint-set_data_structure dbr:Burroughs_Corporation dbr:Scope_(computer_science) dbr:Programming_language dbr:Symbol_table dbr:Nested_functions dbr:Singly_linked_list dbr:Run-time_stack dbr:Felix_(programming_language) dbr:Sahuaro dbr:File:Spaghettistack.svg dbr:Structure_sharing |
| dbp:wikiPageUsesTemplate | dbt:Mvar dbt:Reflist |
| dct:subject | dbc:Metaphors_referring_to_spaghetti dbc:Continuations dbc:Trees_(data_structures) |
| gold:hypernym | dbr:Structure |
| rdf:type | yago:WikicatContinuations yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Arrangement105726596 yago:Cognition100023271 yago:Communication100033020 yago:Continuance101017987 yago:DataStructure105728493 yago:Event100029378 yago:Graph107000195 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity dbo:Building yago:Structure105726345 yago:VisualCommunication106873252 yago:WikicatDataStructures yago:WikicatDirectedGraphs |
| 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) |
| rdfs:label | Pile spaghetti (fr) スパゲッティスタック (ja) Parent pointer tree (en) |
| owl:sameAs | freebase:Parent pointer tree wikidata:Parent pointer tree dbpedia-fr:Parent pointer tree dbpedia-ja:Parent pointer tree dbpedia-sr:Parent pointer tree https://global.dbpedia.org/id/U1X3 yago-res:Parent pointer tree |
| prov:wasDerivedFrom | wikipedia-en:Parent_pointer_tree?oldid=1092029872&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Spaghettistack.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Parent_pointer_tree |
| is dbo:wikiPageRedirects of | dbr:Spaghetti_stack dbr:Cactus_stack dbr:Saguaro_stack |
| is dbo:wikiPageWikiLink of | dbr:Alice_K._Hartley dbr:Link/cut_tree dbr:Stack_machine dbr:Disjoint-set_data_structure dbr:Burroughs_B6x00-7x00_instruction_set dbr:Spaghetti_stack dbr:Cactus_stack dbr:Saguaro_stack |
| is foaf:primaryTopic of | wikipedia-en:Parent_pointer_tree |
