| 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)
|
| 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)
|
.svg?width=300)
.svg){kind=link}
.svg){kind=link}
