Tree (data structure) (original) (raw)
V informatice je strom široce využívanou datovou strukturou, která představuje stromovou strukturu s propojenými uzly.
.svg?width=300)
| Property | Value |
|---|---|
| dbo:abstract | En informàtica, un arbre és una estructura de dades jeràrquica que conté una col·lecció d'elements distribuïts en nodes enllaçats. Tots els nodes tenen almenys un únic node anomenat pare o ascendent, excepte un únic node que no té node pare que anomenen arrel i que és el punt de partida de tot l'arbre. Al seu torn, cada node pot tenir zero o més nodes anomenats fills o descendents. A més, els nodes fills d'un determinat node tenen un ordre determinat entre ells. Tots els nodes han de poder-se abastar des del node arrel seguint els enllaços dels nodes fills. A les implementacions, els nodes sempre tenen referències als seus nodes fills, però no sempre al seu únic node pare. Matemàticament es tracta d'un graf acíclic (sense cicles) i connex (tots els nodes són connectats). Per convenció es parla de: * El node arrel és l'únic node que no té pare. * Un node terminal o node fulla és un que no té cap fill. * Un node intern o node branca és un qualsevol que no sigui ni arrel ni fulla, és a dir, que té pare i que almenys té un fill. * La fondària o nivell d'un node és el nombre d'enllaços que cal passar des del node arrel fins a aquest node. Per convenció -1 és la fondària d'un arbre buit, i 0 és la fondària d'un arbre amb un únic node arrel sol. * Un subarbre és la part d'un arbre que penja d'un node determinat si el prenguéssim com a node arrel, és a dir l'arbre format pel node i tots els seus descendents recursivament. Com a cas especial, el subarbre del node arrel és el mateix arbre sencer. L'acció de recórrer els nodes de l'arbre (walking the tree) es pot fer aplicant diferent criteris: * Pre-ordre o en ordre anterior, o primer en fondària (en anglès depth-first-search o DFS): per cada node primer tractar el node i després recórrer cada un dels subarbres fills. * Post-ordre o en ordre posterior: per cada node primer recórrer cada un dels subarbres fills i després tractar el node. * En ordre de nivell, o primer en amplada (en anglès breadth-first-search o BFS): es recorren successivament tots els nodes de cada nivell, i a continuació es passa al nivell següent. La majoria d'operacions que es fan sobre un arbre comencen pel node arrel, especialment en implementacions d'algorismes recursius. Les operacions habituals que ha d'implementar un arbre són: Les habituals dels contenidors (vegeu l'article contenidor): * Una operació per comprovar quan un arbre està buit * Una operació per obtenir el nombre d'elements de l'arbre Les específiques d'un arbre: * Un constructor que crea un nou arbre buit * Una operació per obtenir el nombre de nivells de l'arbre * Una operació per trobar el node arrel de l'arbre * Algun mètode recursiu per recórrer tots els nodes de l'arbre, sigui pre-ordre, post-ordre, o en ordre de nivell * Una operació per trobar el nivell d'un node determinat * Una operació per trobar cada un dels nodes ascendents d'un node determinat * Una operació per cercar un element d'un valor determinat * Una operació per afegir un nou element en una posició concreta de l'arbre, potser rebalancejant l'arbre * Una operació per eliminar un nou element, potser rebalancejant l'arbre * Una operació per eliminar un subarbre, operació també anomenada podar (pruning) * Una operació per afegir tot un subarbre en una posició concreta de l'arbre, operació també anomenada empeltar (grafting) (ca) V informatice je strom široce využívanou datovou strukturou, která představuje stromovou strukturu s propojenými uzly. (cs) في علم الحاسوب, الشجرة هي هيكل بيانات واسع الاستخدام يحاكي شكل شجرة هرمية مع مجموعة من الرؤوس المرتبطة. في علم رياضيات، هي شجرة متصلة متجهة: متصل عديم الحلقات حيث لكل رأس يوجد صفر أو أكثر من الرؤوس الأبناء وأب واحد على الأكثر. أيضا، لأبناء رأس ما يوجد ترتيبا محددا. (ar) En informadiko, arbo estas vaste uzata abstrakta datumtipo (ADT) aŭ datumstrukturo, kiu realigas tiun datumtipon, kiu simulas hierarkian arbon, kun radika valoro kaj subarboj de infanoj kun poa patra nodo, reprezentata kiel aro de ligitaj nodoj. Arba datumstrukturo povas esti difinita rikure kiel kolekto de nodoj (komenciĝantaj el radika nodo), kie ĉiu nodo estas datumstrukturo konsistanta el valoro kaj listo de referencoj al nodoj (la "infanoj"), kun la limoj, ke neniu referenco estas duplikatita kaj neniu indikas la radikan nodon. Alternative, arbo povas esti difinita abstrakte kiel ordigita arbo kun valoro asignita al ĉiu nodo. Ambaŭ ĉi tiuj perspektivoj estas utilaj: dum arbo povas esti analizita matematike kiel tuto, kiam efektive reprezentita kiel datumstrukturo ĝi estas kutime reprezentata kaj prilaborata kiel apartaj nodoj. Ekzemple, rigardante arbon kiel tuton, oni povas paroli pri "la patra nodo" de ajna nodo, sed ĝenerale kiel datumstrukturo, ajna nodo nur enhavas la liston de siaj infanoj, sen referenco al sia patro. (eo) In der Informatik ist ein Baum (engl. tree) eine Datenstruktur und ein abstrakter Datentyp, mit dem sich hierarchische Strukturen abbilden lassen. Dadurch, dass einerseits viele kombinatorische Probleme auf Bäume zurückgeführt werden können oder (im Fall von Spannbäumen) die Ergebnisse von Graphenalgorithmen (wie der Breiten- oder Tiefensuche) sind, spielen Bäume in der Informatik eine besondere Rolle. Dabei können ausgehend von der Wurzel mehrere gleichartige Objekte miteinander verkettet werden, sodass die lineare Struktur der Liste aufgebrochen wird und eine Verzweigung stattfindet. Da Bäume zu den meist verwendeten Datenstrukturen in der Informatik gehören, gibt es viele Spezialisierungen. (de) En ciencias de la computación y en informática, un árbol es un tipo abstracto de datos (TAD) ampliamente usado que imita la estructura jerárquica de un árbol, con un valor en la raíz y subárboles con un nodo padre, representado como un conjunto de nodos enlazados. Una estructura de datos de árbol se puede definir de forma recursiva (localmente) como una colección de nodos (a partir de un nodo raíz), donde cada nodo es una estructura de datos con un valor, junto con una lista de referencias a los nodos (los hijos), con la condición de que ninguna referencia esté duplicada ni que ningún nodo apunte a la raíz. Alternativamente, un árbol se puede definir de manera abstracta en su conjunto como un árbol ordenado, con un valor asignado a cada nodo. Ambas perspectivas son útiles: mientras que un árbol puede ser analizado matemáticamente, realmente es representado como una estructura de datos en la que se trabaja con cada nodo por separado (en lugar de como una lista de nodos y una lista de adyacencia entre nodos, como un grafo). Mirando a un árbol como conjunto, se puede hablar de el nodo padre de un nodo dado, pero en general se habla de una estructura de datos de un nodo dado que sólo contiene la lista de sus hijos sin referencia a su padre (si lo hay). (es) En théorie des graphes, un arbre enraciné ou une arborescence est un graphe acyclique orienté possédant une unique racine, et tel que tous les nœuds sauf la racine ont un unique parent. En informatique, c'est également une structure de données récursive utilisée pour représenter ce type de graphes. (fr) Dalam ilmu komputer, sebuah Pohon adalah suatu struktur data yang digunakan secara luas yang menyerupai struktur pohon dengan sejumlah simpul yang terhubung. (in) In computer science, a tree is a widely used abstract data type that represents a hierarchical tree structure with a set of connected nodes. Each node in the tree can be connected to many children (depending on the type of tree), but must be connected to exactly one parent, except for the root node, which has no parent. These constraints mean there are no cycles or "loops" (no node can be its own ancestor), and also that each child can be treated like the root node of its own subtree, making recursion a useful technique for tree traversal. In contrast to linear data structures, many trees cannot be represented by relationships between neighboring nodes in a single straight line. Binary trees are a commonly used type, which constrain the number of children for each parent to exactly two. When the order of the children is specified, this data structure corresponds to an ordered tree in graph theory. A value or pointer to other data may be associated with every node in the tree, or sometimes only with the leaf nodes, which have no children. The abstract data type can be represented in a number of ways, including a list of parents with pointers to children, a list of children with pointers to parents, or a list of nodes and a separate list of parent-child relations (a specific type of adjacency list). Representations might also be more complicated, for example using indexes or ancestor lists for performance. Trees as used in computing are similar to but can be different from mathematical constructs of trees in graph theory, trees in set theory, and trees in descriptive set theory. (en) 트리 구조(tree 構造, 문화어: 나무구조)란 그래프의 일종으로, 한 노드에서 시작해서 다른 정점들을 순회하여 자기 자신에게 돌아오는 순환이 없는 연결 그래프이다. 트리에서 최상위 노드를 루트 노드(root node 뿌리 노드[*])라고 한다. 또한 노드 A가 노드 B를 가리킬 때 A를 B의 부모 노드(parent node), B를 A의 자식 노드(child node)라고 한다. 자식 노드가 없는 노드를 잎 노드(leaf node 리프 노드[*]) 또는 말단 노드 (terminal node)라고 한다. 잎 노드가 아닌 노드를 내부 노드(internal node)라고 한다. (ko) 木構造（きこうぞう）とは、グラフ理論の木の構造をしたデータ構造のこと。 数字的な木の扱いについては「木 (数学)」を参照 (ja) In informatica, un albero o struttura ad albero (tree in inglese) è la struttura dati che si riconduce al concetto di albero con radice presente nella teoria dei grafi. Un albero si compone di due tipi di sottostrutture fondamentali: il nodo, che in genere contiene informazioni, e l'arco, che stabilisce un collegamento gerarchico fra due nodi: si parla allora di un nodo padre dal quale esce un arco orientato che lo collega ad un nodo figlio. Si chiede inoltre che ogni nodo possa avere al massimo un unico arco entrante, mentre dai diversi nodi possono uscire diversi numeri di archi uscenti. Si chiede infine che l'albero possegga un unico nodo privo di arco entrante: questo nodo viene detto radice (root) dell'albero. Ogni nodo che non presenta archi uscenti è detto foglia (leaf node) e in ogni albero finito, cioè con un numero finito di nodi, si trova almeno un nodo foglia. Ovviamente, un nodo può essere contemporaneamente padre (se ha archi uscenti) e figlio (se ha un arco entrante, ovvero se è diverso dalla radice). Solitamente ogni nodo porta con sé delle informazioni e molto spesso anche una chiave con cui è possibile identificarlo univocamente all'interno dell'albero. L'altezza o profondità dell'albero è il massimo delle lunghezze dei suoi cammini massimali, cammini che vanno dalla radice alle sue foglie. (it) Een boom of boomstructuur is een datastructuur in de informatica die een bijzonder geval van een graaf is. Een boom bestaat uit een knoop(punt) of vertex die de stam (ook wel wortel) genoemd wordt en die het ingangspunt is voor de in de boom opgeslagen informatie. In deze wortelknoop zitten nul of meer pointers die naar andere knooppunten verwijzen. Ieder knooppunt behalve de wortel heeft precies een ouder en nul of meer kinderen. Verwijzingen gaan dus nooit tussen de kinderen onderling maar alleen van ouder naar kind; in een wat uitgebreidere versie eventueel ook van kind naar ouder (bidirectionele graaf). In een boom bestaan geen cirkelpaden en is er altijd precies 1 pad van de wortel naar een willekeurige knoop. Een knoop die zelf geen kinderen heeft noemt men een blad. (nl) Árvore, no contexto da programação, engenharia de software e ciência da computação, é uma das mais importantes estruturas de dados não lineares. Herda as características das topologia em árvore. Conceptualmente diferente das listas, em que os dados se encontram numa sequência, nas árvores os dados estão dispostos de forma hierárquica, seus elementos se encontram "acima" ou "abaixo" de outros elementos da árvore. São estruturas eficientes e simples em relação ao tratamento computacional, diferentemente dos grafos. Há inúmeros problemas no mundo real que podem ser modelados e resolvidos através das árvores. Estruturas de pastas de um sistema operacional, interfaces gráficas, bancos de dados e sites da Internet são exemplos de aplicações de árvores. Uma árvore é formada por um conjunto de elementos que armazenam informações chamados nodos ou nós. Toda a árvore possui o elemento chamado raiz, que possui ligações para outros elementos denominados ramos ou filhos. Estes ramos podem estar ligados a outros elementos que também podem possuir outros ramos. O elemento que não possui ramos é conhecido como nó folha, nó terminal ou nó externo. Uma terminologia muito utilizada nas estruturas de árvores tem origem das árvores genealógicas. O relacionamento entre nodos é descrito com os termos "pai" (ou "mãe") para os antecessores diretos de um nodo, "filhos" (ou "filhas") para os descendentes diretos e "irmãos" (ou "irmãs") para todos os nodos com mesmo pai. (pt) Drzewo – struktura danych reprezentująca drzewo matematyczne. W naturalny sposób reprezentuje hierarchię danych (obiektów fizycznych i abstrakcyjnych, pojęć, itp.) jest więc stosowane głównie do tego celu. Drzewa ułatwiają i przyspieszają wyszukiwanie, a także pozwalają w łatwy sposób operować na posortowanych danych. Znaczenie tych struktur jest bardzo duże i ze względu na swoje własności drzewa są stosowane praktycznie w każdej dziedzinie informatyki (np. bazy danych, grafika komputerowa, przetwarzanie tekstu, telekomunikacja, serwery). (pl) Inom datavetenskap är träd en vanlig datastruktur som ordnar en mängd element hierarkiskt i ett riktat träd där varje nod bara kan ha en båge som leder in till noden. Rotnoden är den första noden i trädet, den enda nod som inte har några grenar som leder in. Från rotnoden finns det exakt en väg till varje annan nod i trädet. (sv) Дерево — одна из наиболее широко распространённых структур данных в информатике, эмулирующая древовидную структуру в виде набора связанных узлов. Является связным графом, не содержащим циклы. Большинство источников также добавляют условие на то, что рёбра графа не должны быть ориентированными. В дополнение к этим трём ограничениям, в некоторых источниках указывается, что рёбра графа не должны быть взвешенными. (ru) 在計算機科學中，樹（英語：tree）是一种抽象数据类型（ADT）或是實作這種抽象数据类型的数据结构，用來模擬具有樹狀結構性質的数据集合。它是由n（n>0）个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点： * 每个节点都只有有限个子节点或無子節點； * 没有父节点的节点称为根节点； * 每一个非根节点有且只有一个父节点； * 除了根节点外，每个子节点可以分为多个不相交的子树； * 樹裡面沒有環路(cycle) (zh) Де́рево (англ. tree) — в інформатиці та програмуванні одна з найпоширеніших структур даних.Формально дерево визначається як скінченна множина Т з однією або більше вершин (вузлів, nodes), яка задовольняє наступним вимогам: 1. * існує один відокремлений вузол — корінь (root) дерева; 2. * інші вузли (за винятком кореня) розподілені серед m ≥ 0 непересічних множин T1…Tm і кожна з цих множин, в свою чергу, є деревом. Дерева T1…Tm мають назву піддерев (subtrees) даного кореня. (uk) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Tree_(computer_science).svg?width=300 |
| dbo:wikiPageExternalLink | http://wormweb.org/celllineage https://xlinux.nist.gov/dads/HTML/tree.html http://www.allisons.org/ll/AlgDS/Tree/ https://cran.r-project.org/web/packages/data.tree/ http://www.community-of-knowledge.de/beitrag/data-trees-as-a-means-of-presenting-complex-data-analysis/ |
| dbo:wikiPageID | 30806 (xsd:integer) |
| dbo:wikiPageInterLanguageLink | dbpedia-de:Baum_(Graphentheorie) |
| dbo:wikiPageLength | 17395 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1116543446 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Rooted_tree dbr:Multigraph dbr:Namespace dbr:Natural_language_processing dbr:Binary_heap dbr:Binary_search_tree dbr:Binary_tree dbr:Dewey_Decimal_Classification dbr:Arborescence_(graph_theory) dbr:Undirected_graph dbr:Introduction_to_Algorithms dbr:Thomas_H._Cormen dbr:Computer-generated_imagery dbr:Connectivity_(graph_theory) dbr:Generative_grammar dbr:Genetic_programming dbr:Node_(computer_science) dbr:Object-oriented_programming dbr:Class_(computer_programming) dbr:Clifford_Stein dbr:Graph_(discrete_mathematics) dbr:Branching_factor dbr:Lowest_common_ancestor dbr:Computer_science dbr:Superior_(hierarchy) dbr:Tree_(descriptive_set_theory) dbr:Tree_(graph_theory) dbr:Tree_(set_theory) dbr:Tree_traversal dbr:Trie dbr:Type_theory dbr:Database_index dbr:Heap_(data_structure) dbr:List_(abstract_data_type) dbr:Abstract_data_type dbr:Adjacency_list dbc:Data_types dbr:Dynamic_memory_allocation dbr:Evolution dbr:Barnes–Hut_simulation dbr:Breadth-first_search dbr:Dialogue_tree dbr:Directed_graph dbr:Directory_structure dbr:Graph_theory dbr:Hard_link dbr:Tree_structure dbr:S-expression dbr:Recursion dbr:Relational_database dbr:HTML dbr:Hierarchical dbr:Hierarchical_temporal_memory dbr:JSON dbr:Taxonomy_(general) dbr:Array_data_structure dbc:Knowledge_representation dbr:Abstract_syntax_tree dbc:Abstract_data_types dbc:Trees_(data_structures) dbr:Charles_E._Leiserson dbr:Binary_space_partitioning dbr:Symbolic_link dbr:Hierarchical_clustering dbr:Hierarchy_(mathematics) dbr:Parse_tree dbr:Recursive_data_type dbr:Dictionary_of_Algorithms_and_Data_Structures dbr:Digital_compositing dbr:Document_Object_Model dbr:Donald_Knuth dbr:Associative_array dbr:Sorting_algorithm dbr:Class_hierarchy dbr:Ordered_tree dbr:Search_algorithm dbr:XML dbr:YAML dbr:Multiple_inheritance dbr:Nested_set dbr:Outdegree dbr:Exploded-view_drawing dbr:The_Art_of_Computer_Programming dbr:Linear_data_structure dbr:Space_partitioning dbr:Grafting_(algorithm) dbr:Search_tree dbr:Pruning_(algorithm) dbr:File_systems dbr:Ronald_L._Rivest dbr:Subroutine_call dbr:File:Tree_(computer_science).svg dbr:File:Linux_Distribution_Timeline_Dec._2020.svg |
| dbp:align | center (en) |
| dbp:caption | : cycle B→C→E→D→B. B has more than one parent . (en) Each linear list is trivially (en) : two non-connected parts, A→B and C→D→E. There is more than one root. (en) : undirected cycle 1-2-4-3. 4 has more than one parent . (en) : cycle A→A. A is the root but it also has a parent. (en) |
| dbp:image | Directed Graph Edge.svg (en) Directed graph with branching SVG.svg (en) Directed graph, cyclic.svg (en) Directed graph, disjoint.svg (en) Graph single node.svg (en) |
| dbp:width | 92 (xsd:integer) 101 (xsd:integer) 130 (xsd:integer) 173 (xsd:integer) 211 (xsd:integer) |
| dbp:wikiPageUsesTemplate | dbt:Defn dbt:Graph_search_algorithm dbt:CS-Trees dbt:Color dbt:Commons_category dbt:Distinguish dbt:Efn dbt:Huh dbt:ISBN dbt:Main_article dbt:Math dbt:Multiple_image dbt:Mvar dbt:Notelist dbt:Refbegin dbt:Refend dbt:Reflist dbt:Short_description dbt:Unreferenced_section dbt:Glossary dbt:Glossary_end dbt:Term dbt:Data_structures |
| dct:subject | dbc:Data_types dbc:Knowledge_representation dbc:Abstract_data_types dbc:Trees_(data_structures) |
| gold:hypernym | dbr:Structure |
| rdf:type | owl:Thing yago:Abstraction100002137 yago:Arrangement105726596 yago:Cognition100023271 yago:DataStructure105728493 yago:PsychologicalFeature100023100 dbo:Building yago:Structure105726345 yago:WikicatDataStructures |
| rdfs:comment | V informatice je strom široce využívanou datovou strukturou, která představuje stromovou strukturu s propojenými uzly. (cs) في علم الحاسوب, الشجرة هي هيكل بيانات واسع الاستخدام يحاكي شكل شجرة هرمية مع مجموعة من الرؤوس المرتبطة. في علم رياضيات، هي شجرة متصلة متجهة: متصل عديم الحلقات حيث لكل رأس يوجد صفر أو أكثر من الرؤوس الأبناء وأب واحد على الأكثر. أيضا، لأبناء رأس ما يوجد ترتيبا محددا. (ar) In der Informatik ist ein Baum (engl. tree) eine Datenstruktur und ein abstrakter Datentyp, mit dem sich hierarchische Strukturen abbilden lassen. Dadurch, dass einerseits viele kombinatorische Probleme auf Bäume zurückgeführt werden können oder (im Fall von Spannbäumen) die Ergebnisse von Graphenalgorithmen (wie der Breiten- oder Tiefensuche) sind, spielen Bäume in der Informatik eine besondere Rolle. Dabei können ausgehend von der Wurzel mehrere gleichartige Objekte miteinander verkettet werden, sodass die lineare Struktur der Liste aufgebrochen wird und eine Verzweigung stattfindet. Da Bäume zu den meist verwendeten Datenstrukturen in der Informatik gehören, gibt es viele Spezialisierungen. (de) En théorie des graphes, un arbre enraciné ou une arborescence est un graphe acyclique orienté possédant une unique racine, et tel que tous les nœuds sauf la racine ont un unique parent. En informatique, c'est également une structure de données récursive utilisée pour représenter ce type de graphes. (fr) Dalam ilmu komputer, sebuah Pohon adalah suatu struktur data yang digunakan secara luas yang menyerupai struktur pohon dengan sejumlah simpul yang terhubung. (in) 트리 구조(tree 構造, 문화어: 나무구조)란 그래프의 일종으로, 한 노드에서 시작해서 다른 정점들을 순회하여 자기 자신에게 돌아오는 순환이 없는 연결 그래프이다. 트리에서 최상위 노드를 루트 노드(root node 뿌리 노드[*])라고 한다. 또한 노드 A가 노드 B를 가리킬 때 A를 B의 부모 노드(parent node), B를 A의 자식 노드(child node)라고 한다. 자식 노드가 없는 노드를 잎 노드(leaf node 리프 노드[*]) 또는 말단 노드 (terminal node)라고 한다. 잎 노드가 아닌 노드를 내부 노드(internal node)라고 한다. (ko) 木構造（きこうぞう）とは、グラフ理論の木の構造をしたデータ構造のこと。 数字的な木の扱いについては「木 (数学)」を参照 (ja) Een boom of boomstructuur is een datastructuur in de informatica die een bijzonder geval van een graaf is. Een boom bestaat uit een knoop(punt) of vertex die de stam (ook wel wortel) genoemd wordt en die het ingangspunt is voor de in de boom opgeslagen informatie. In deze wortelknoop zitten nul of meer pointers die naar andere knooppunten verwijzen. Ieder knooppunt behalve de wortel heeft precies een ouder en nul of meer kinderen. Verwijzingen gaan dus nooit tussen de kinderen onderling maar alleen van ouder naar kind; in een wat uitgebreidere versie eventueel ook van kind naar ouder (bidirectionele graaf). In een boom bestaan geen cirkelpaden en is er altijd precies 1 pad van de wortel naar een willekeurige knoop. Een knoop die zelf geen kinderen heeft noemt men een blad. (nl) Drzewo – struktura danych reprezentująca drzewo matematyczne. W naturalny sposób reprezentuje hierarchię danych (obiektów fizycznych i abstrakcyjnych, pojęć, itp.) jest więc stosowane głównie do tego celu. Drzewa ułatwiają i przyspieszają wyszukiwanie, a także pozwalają w łatwy sposób operować na posortowanych danych. Znaczenie tych struktur jest bardzo duże i ze względu na swoje własności drzewa są stosowane praktycznie w każdej dziedzinie informatyki (np. bazy danych, grafika komputerowa, przetwarzanie tekstu, telekomunikacja, serwery). (pl) Inom datavetenskap är träd en vanlig datastruktur som ordnar en mängd element hierarkiskt i ett riktat träd där varje nod bara kan ha en båge som leder in till noden. Rotnoden är den första noden i trädet, den enda nod som inte har några grenar som leder in. Från rotnoden finns det exakt en väg till varje annan nod i trädet. (sv) Дерево — одна из наиболее широко распространённых структур данных в информатике, эмулирующая древовидную структуру в виде набора связанных узлов. Является связным графом, не содержащим циклы. Большинство источников также добавляют условие на то, что рёбра графа не должны быть ориентированными. В дополнение к этим трём ограничениям, в некоторых источниках указывается, что рёбра графа не должны быть взвешенными. (ru) 在計算機科學中，樹（英語：tree）是一种抽象数据类型（ADT）或是實作這種抽象数据类型的数据结构，用來模擬具有樹狀結構性質的数据集合。它是由n（n>0）个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点： * 每个节点都只有有限个子节点或無子節點； * 没有父节点的节点称为根节点； * 每一个非根节点有且只有一个父节点； * 除了根节点外，每个子节点可以分为多个不相交的子树； * 樹裡面沒有環路(cycle) (zh) Де́рево (англ. tree) — в інформатиці та програмуванні одна з найпоширеніших структур даних.Формально дерево визначається як скінченна множина Т з однією або більше вершин (вузлів, nodes), яка задовольняє наступним вимогам: 1. * існує один відокремлений вузол — корінь (root) дерева; 2. * інші вузли (за винятком кореня) розподілені серед m ≥ 0 непересічних множин T1…Tm і кожна з цих множин, в свою чергу, є деревом. Дерева T1…Tm мають назву піддерев (subtrees) даного кореня. (uk) En informàtica, un arbre és una estructura de dades jeràrquica que conté una col·lecció d'elements distribuïts en nodes enllaçats. Tots els nodes tenen almenys un únic node anomenat pare o ascendent, excepte un únic node que no té node pare que anomenen arrel i que és el punt de partida de tot l'arbre. Al seu torn, cada node pot tenir zero o més nodes anomenats fills o descendents. A més, els nodes fills d'un determinat node tenen un ordre determinat entre ells. Tots els nodes han de poder-se abastar des del node arrel seguint els enllaços dels nodes fills. Per convenció es parla de: (ca) En informadiko, arbo estas vaste uzata abstrakta datumtipo (ADT) aŭ datumstrukturo, kiu realigas tiun datumtipon, kiu simulas hierarkian arbon, kun radika valoro kaj subarboj de infanoj kun poa patra nodo, reprezentata kiel aro de ligitaj nodoj. Arba datumstrukturo povas esti difinita rikure kiel kolekto de nodoj (komenciĝantaj el radika nodo), kie ĉiu nodo estas datumstrukturo konsistanta el valoro kaj listo de referencoj al nodoj (la "infanoj"), kun la limoj, ke neniu referenco estas duplikatita kaj neniu indikas la radikan nodon. (eo) En ciencias de la computación y en informática, un árbol es un tipo abstracto de datos (TAD) ampliamente usado que imita la estructura jerárquica de un árbol, con un valor en la raíz y subárboles con un nodo padre, representado como un conjunto de nodos enlazados. (es) In computer science, a tree is a widely used abstract data type that represents a hierarchical tree structure with a set of connected nodes. Each node in the tree can be connected to many children (depending on the type of tree), but must be connected to exactly one parent, except for the root node, which has no parent. These constraints mean there are no cycles or "loops" (no node can be its own ancestor), and also that each child can be treated like the root node of its own subtree, making recursion a useful technique for tree traversal. In contrast to linear data structures, many trees cannot be represented by relationships between neighboring nodes in a single straight line. (en) In informatica, un albero o struttura ad albero (tree in inglese) è la struttura dati che si riconduce al concetto di albero con radice presente nella teoria dei grafi. Un albero si compone di due tipi di sottostrutture fondamentali: il nodo, che in genere contiene informazioni, e l'arco, che stabilisce un collegamento gerarchico fra due nodi: si parla allora di un nodo padre dal quale esce un arco orientato che lo collega ad un nodo figlio. (it) Árvore, no contexto da programação, engenharia de software e ciência da computação, é uma das mais importantes estruturas de dados não lineares. Herda as características das topologia em árvore. Conceptualmente diferente das listas, em que os dados se encontram numa sequência, nas árvores os dados estão dispostos de forma hierárquica, seus elementos se encontram "acima" ou "abaixo" de outros elementos da árvore. (pt) |
| rdfs:label | شجرة (بنية بيانات) (ar) Arbre (estructura de dades) (ca) Strom (datová struktura) (cs) Baum (Datenstruktur) (de) Arbo (datumstrukturo) (eo) Árbol (informática) (es) Arbre enraciné (fr) Pohon (struktur data) (in) Albero (informatica) (it) 木構造 (データ構造) (ja) 트리 구조 (ko) Drzewo (informatyka) (pl) Boom (datastructuur) (nl) Árvore (estrutura de dados) (pt) Tree (data structure) (en) Дерево (структура данных) (ru) Träd (datastruktur) (sv) 树 (数据结构) (zh) Дерево (структура даних) (uk) |
| owl:sameAs | dbpedia-de:Tree (data structure) dbpedia-ja:Tree (data structure) freebase:Tree (data structure) yago-res:Tree (data structure) wikidata:Tree (data structure) dbpedia-ar:Tree (data structure) dbpedia-bg:Tree (data structure) dbpedia-ca:Tree (data structure) dbpedia-cs:Tree (data structure) http://cv.dbpedia.org/resource/Йывăç_(панăлăхсен_тытăмĕ) dbpedia-da:Tree (data structure) dbpedia-eo:Tree (data structure) dbpedia-es:Tree (data structure) dbpedia-et:Tree (data structure) dbpedia-fa:Tree (data structure) dbpedia-fi:Tree (data structure) dbpedia-fr:Tree (data structure) dbpedia-hu:Tree (data structure) dbpedia-id:Tree (data structure) dbpedia-is:Tree (data structure) dbpedia-it:Tree (data structure) dbpedia-ko:Tree (data structure) http://lt.dbpedia.org/resource/Medis_(duomenų_struktūra) http://lv.dbpedia.org/resource/Koks_(datu_struktūra) dbpedia-mk:Tree (data structure) http://ml.dbpedia.org/resource/ട്രീ_(ഡാറ്റാ_സ്ട്രക്ചർ) http://mn.dbpedia.org/resource/Мод_(өгөгдлийн_бүтэц) dbpedia-nl:Tree (data structure) dbpedia-no:Tree (data structure) dbpedia-pl:Tree (data structure) dbpedia-pt:Tree (data structure) dbpedia-ru:Tree (data structure) dbpedia-sh:Tree (data structure) dbpedia-simple:Tree (data structure) dbpedia-sl:Tree (data structure) dbpedia-sr:Tree (data structure) dbpedia-sv:Tree (data structure) http://ta.dbpedia.org/resource/மரம்_(தரவுக்_கட்டமைப்பு) dbpedia-th:Tree (data structure) http://tl.dbpedia.org/resource/Puno_(estruktura_ng_datos) dbpedia-tr:Tree (data structure) dbpedia-uk:Tree (data structure) dbpedia-vi:Tree (data structure) dbpedia-zh:Tree (data structure) https://global.dbpedia.org/id/27d6U |
| prov:wasDerivedFrom | wikipedia-en:Tree_(data_structure)?oldid=1116543446&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Tree_(computer_science).svg wiki-commons:Special:FilePath/Directed_Graph_Edge.svg wiki-commons:Special:FilePath/Directed_graph,_cyclic.svg wiki-commons:Special:FilePath/Directed_graph,_disjoint.svg wiki-commons:Special:FilePath/Directed_graph_with_branching_SVG.svg wiki-commons:Special:FilePath/Graph_single_node.svg wiki-commons:Special:FilePath/Linux_Distribution_Timeline_Dec._2020.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Tree_(data_structure) |
| is dbo:wikiPageDisambiguates of | dbr:Tree_(disambiguation) |
| is dbo:wikiPageRedirects of | dbr:Root_node dbr:Non-leaf_node dbr:Tree_data_structure dbr:Tree_leaf dbr:Tree_path dbr:Applications_of_tree_data_structures dbr:Subtree dbr:Tree_(computing) dbr:Leaf_node dbr:Parent_node dbr:Child_node dbr:Child_nodes dbr:Internal_node dbr:Leaf_object dbr:Inverted_tree dbr:Tree_(computer_science) dbr:Ordered_tree_data_structure dbr:Parent_node_(in_a_tree) dbr:Ancestor_node dbr:Sibling_node dbr:Leaf_nodes dbr:Inner_node dbr:Interior_node dbr:Internal_vertices dbr:External_node dbr:Root_Node dbr:Sub-child dbr:Subchild dbr:Subtrees |
| is dbo:wikiPageWikiLink of | dbr:Protein_design dbr:Root_node dbr:Rose_tree dbr:Enfilade_(Xanadu) dbr:List_of_data_structures dbr:Merkle_tree dbr:Modal_window dbr:Namespace dbr:Metric_tree dbr:Reactive_planning dbr:Non-leaf_node dbr:Binary_search_tree dbr:Binary_tree dbr:Binomial_options_pricing_model dbr:Boehm_garbage_collector dbr:Declarative_programming dbr:Argumentation_framework dbr:Betrayal_at_Krondor dbr:List_of_educational_programming_languages dbr:Persistent_data_structure dbr:Relational_algebra dbr:Repertory_grid dbr:Resolution_(logic) dbr:Robert_Lee_Grossman dbr:DWARF dbr:Vantage-point_tree dbr:Degree_(graph_theory) dbr:Dependency_grammar dbr:Depth-first_search dbr:Doubly_logarithmic_tree dbr:Dynamic_HTML dbr:Inclusion_order dbr:Induction_of_regular_languages dbr:Infinite_loop dbr:Information_fuzzy_networks dbr:Initial_algebra dbr:Input_enhancement_(computer_science) dbr:Interval_tree dbr:JGRASP dbr:Tree_accumulation dbr:Level_ancestor_problem dbr:Level_of_detail_(computer_graphics) dbr:List_of_people_from_Holyoke,_Massachusetts dbr:Prefuse dbr:Comparison_of_file_managers dbr:Ancestral_reconstruction dbr:Genetic_programming dbr:Node_(computer_science) dbr:TreeLine_(outliner) dbr:Radial_tree dbr:Ehud_Shapiro dbr:Enyo_(software) dbr:Genetic_algorithm dbr:Genetic_editing dbr:Glossary_of_artificial_intelligence dbr:Glossary_of_computer_science dbr:Grammar_induction dbr:Graph_database dbr:Monad_(functional_programming) dbr:Multiclass_classification dbr:Container_(type_theory) dbr:Control_table dbr:Control_theory dbr:Critical_section dbr:Crossover_(genetic_algorithm) dbr:Range_query_(data_structures) dbr:Miller_columns dbr:Tree_data_structure dbr:Tree_leaf dbr:Tree_path dbr:Apache_ZooKeeper dbr:Applications_of_tree_data_structures dbr:Legends_of_Valour dbr:Leo_(text_editor) dbr:Lisp_(programming_language) dbr:Sister_group dbr:Subtree dbr:Comparison_of_document_markup_languages dbr:Comparison_of_programming_languages dbr:Compiler-compiler dbr:Computer_chess dbr:Computer_program dbr:Feature_structure dbr:Fully_qualified_name dbr:Functional_programming dbr:Child_(disambiguation) dbr:Personal_knowledge_base dbr:Pointer_(computer_programming) dbr:Polythematic_structured-subject_heading_system dbr:Principal_variation_search dbr:Protocol_Independent_Multicast dbr:Pointer_swizzling dbr:Structure dbr:Succinct_data_structure dbr:Suffix_tree dbr:Tree-adjoining_grammar dbr:Standard_library dbr:Mutual_recursion dbr:Axiom_(computer_algebra_system) dbr:B+_tree dbr:B-tree dbr:C_(programming_language) dbr:Adaptive_k-d_tree dbr:Tree_(computing) dbr:Tree_(graph_theory) dbr:Tree_traversal dbr:Trie dbr:Data_(computer_science) dbr:Data_structure dbr:Database_model dbr:Distributed_tree_search dbr:Domain_Name_System dbr:HTree dbr:Heap_(data_structure) dbr:K-d_tree dbr:Layer_(object-oriented_design) dbr:Leaf_node dbr:Linguistic_sequence_complexity dbr:Log-structured_merge-tree dbr:Patent_visualisation dbr:Pstree dbr:2–3–4_tree dbr:A*_search_algorithm dbr:AIDA_(computing) dbr:ALTQ dbr:Abstract_data_type dbr:2–3_tree dbr:Data_type dbr:Datalight dbr:Ext4 dbr:Fenwick_tree dbr:File_format dbr:Breadth-first_search dbr:Broadcast_encryption dbr:Null_graph dbr:Parent_node dbr:Partially_ordered_set dbr:Pascal_(programming_language) dbr:Dijkstra–Scholten_algorithm dbr:Directory-based_cache_coherence dbr:Discrete_calculus dbr:Fat_tree dbr:Gorn_address dbr:Graph_theory dbr:Iterative_deepening_A* dbr:Kinetic_hanger dbr:Kinetic_tournament dbr:Tree_structure dbr:Object_composition dbr:S-expression dbr:Proof_theory dbr:Read-copy-update dbr:Wreath_product dbr:Hierarchical_RBF dbr:Hierarchical_temporal_memory dbr:Iterative_deepening_depth-first_search dbr:Term_(logic) dbr:Test_Template_Framework dbr:Hyperbolic_tree dbr:Straight-line_grammar dbr:AVL_tree dbr:Abstract_syntax_tree dbr:Child_node dbr:Child_nodes dbr:Keynote_(notetaking_software) dbr:Binary_space_partitioning dbr:SuperPascal dbr:Sweble dbr:Collection_(abstract_data_type) dbr:Hierarchical_control_system dbr:Hierarchy_(mathematics) dbr:Hierarchy_Open_Service_Interface_Definition dbr:Parse_tree dbr:Tree_(disambiguation) dbr:Tributary dbr:Zipper_(data_structure) dbr:Recursive_data_type dbr:Red–black_tree dbr:BIRCH dbr:CAR_and_CDR dbr:Phylogenetic_tree dbr:Find_(Unix) dbr:Incompatible_Timesharing_System dbr:Internal_node dbr:Kontact dbr:Method_of_analytic_tableaux dbr:Radix_sort dbr:Recursion_(computer_science) dbr:Seaside_(software) dbr:Segment_tree dbr:Work_breakdown_structure dbr:Height_(disambiguation) dbr:MCS_algorithm dbr:Memory_management_unit dbr:Monadic_second-order_logic dbr:Multiple_granularity_locking dbr:Pattern_matching dbr:Root_directory dbr:Sedna_(database) dbr:Sentinel_node dbr:Sentinel_value dbr:Set_(abstract_data_type) dbr:Two-phase_commit_protocol dbr:Infinite_tree dbr:Nested_set dbr:Nested_set_model dbr:Nested_word dbr:XMF dbr:Top_tree dbr:TIME-ITEM dbr:WorkPLAN dbr:F-algebra dbr:ID/LP_grammar dbr:Forest_(disambiguation) dbr:List_of_web_directories dbr:List_of_wiki_software dbr:Leaf_object dbr:Tango_tree dbr:The_Art_of_Computer_Programming dbr:Planted_motif_search dbr:Treemapping dbr:NTFS_links dbr:Scene_graph dbr:Tree_of_primitive_Pythagorean_triples dbr:Multiton_pattern dbr:Semantic_resolution_tree dbr:X-tree dbr:Parent_and_child dbr:Page_table dbr:Pairing_heap dbr:Pairwise_compatibility_graph dbr:Palindrome_tree dbr:Persistent_array dbr:TreeDL dbr:Outline_of_computer_science dbr:RotateRight_Zoom dbr:Zero-suppressed_decision_diagram dbr:Search_tree dbr:Skip_graph dbr:Inverted_tree dbr:Tree_(computer_science) dbr:Ordered_tree_data_structure dbr:Parent_node_(in_a_tree) dbr:Ancestor_node dbr:Sibling_node dbr:Leaf_nodes dbr:Inner_node dbr:Interior_node dbr:Internal_vertices dbr:External_node dbr:Root_Node dbr:Sub-child dbr:Subchild dbr:Subtrees |
| is dbp:data of | dbr:Iterative_deepening_A* dbr:Iterative_deepening_depth-first_search |
| is dbp:type of | dbr:B+_tree dbr:B-tree dbr:AVL_tree dbr:Red–black_tree |
| is owl:differentFrom of | dbr:Tree_network |
| is foaf:primaryTopic of | wikipedia-en:Tree_(data_structure) |
