| dbo:abstract
|
- En algorithmique, un arbre cousu, ou threaded tree en anglais, est une structure de données, basée sur un arbre binaire. (fr)
- In computing, a threaded binary tree is a binary tree variant that facilitates traversal in a particular order (often the same order already defined for the tree). An entire binary search tree can be easily traversed in order of the main key, but given only a pointer to a node, finding the node which comes next may be slow or impossible. For example, leaf nodes by definition have no descendants, so given only a pointer to a leaf node no other node can be reached. A threaded tree adds extra information in some or all nodes, so that for any given single node the "next" node can be found quickly, allowing tree traversal without recursion and the extra storage (proportional to the tree's depth) that recursion requires. (en)
- 스레드 이진 트리(Threaded binary tree)는 이진 트리의 한 종류로, 가리키는 곳이 없는 모든 오른쪽 널 포인터(null pointer)를 중위 후속자 노드로 연결하고, 가리키는 곳이 없는 모든 왼쪽 널 포인터를 중위 선행자 노드로 연결한 것을 말하며, 재귀적인 중위 순회를 빠르게 할 수 있는 방법으로 사용된다. 이는 또한 조금 느리더라도 부모 포인터나 스택을 사용하지 않고도 스레드 이진 트리에서 노드의 부모를 찾을 수 있게 해 준다. 이는 스택 공간을 쓸 수 없거나, 부모 노드의 위치를 알 수 없을 때 유용하게 사용될 수 있다. (ko)
- Árvore binária com costura, ou Árvore binária com fios é uma estrutura de dados derivada da Árvore de busca binária, em que os ponteiros nulos são aproveitados para armazenar o endereço do predecessor ou sucessor em in-ordem. Uma Árvore de busca binária com elementos tem ponteiros. Para provar essa afirmação aplica-se indução sobre o número de elementos da árvore. Uma árvore com elemento tem dois ponteiros nulos. Adicionando um elemento em uma posição qualquer da árvore, um ponteiro deixa de ser nulo, porém surgem outros dois, pois novos elementos sempre são folhas. Assim a nova árvore tem ponteiros vazios. Uma ligação de costura aproveita a memória desperdiçada por esses ponteiros para apontar para o predecessor (se o nodo não tiver filho esquerdo) ou para o sucessor (se o nodo não tiver filho direito). Isso torna o percusso in-ordem mais fácil de ser implementado e mais eficiente. (pt)
- Прошитое двоичное дерево — это вариант двоичного дерева, который позволяет производить быстрый обход — если дан указатель на узел в прошитом дереве, можно легко найти следующий по порядку узел (и/или предыдущий). (ru)
- 在计算机科学中，引線二元樹（或稱引线二叉树）是添加了直接指向节点的前驱和后继的指针的二叉树。 (zh)
|
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 8914 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- En algorithmique, un arbre cousu, ou threaded tree en anglais, est une structure de données, basée sur un arbre binaire. (fr)
- In computing, a threaded binary tree is a binary tree variant that facilitates traversal in a particular order (often the same order already defined for the tree). An entire binary search tree can be easily traversed in order of the main key, but given only a pointer to a node, finding the node which comes next may be slow or impossible. For example, leaf nodes by definition have no descendants, so given only a pointer to a leaf node no other node can be reached. A threaded tree adds extra information in some or all nodes, so that for any given single node the "next" node can be found quickly, allowing tree traversal without recursion and the extra storage (proportional to the tree's depth) that recursion requires. (en)
- 스레드 이진 트리(Threaded binary tree)는 이진 트리의 한 종류로, 가리키는 곳이 없는 모든 오른쪽 널 포인터(null pointer)를 중위 후속자 노드로 연결하고, 가리키는 곳이 없는 모든 왼쪽 널 포인터를 중위 선행자 노드로 연결한 것을 말하며, 재귀적인 중위 순회를 빠르게 할 수 있는 방법으로 사용된다. 이는 또한 조금 느리더라도 부모 포인터나 스택을 사용하지 않고도 스레드 이진 트리에서 노드의 부모를 찾을 수 있게 해 준다. 이는 스택 공간을 쓸 수 없거나, 부모 노드의 위치를 알 수 없을 때 유용하게 사용될 수 있다. (ko)
- Прошитое двоичное дерево — это вариант двоичного дерева, который позволяет производить быстрый обход — если дан указатель на узел в прошитом дереве, можно легко найти следующий по порядку узел (и/или предыдущий). (ru)
- 在计算机科学中，引線二元樹（或稱引线二叉树）是添加了直接指向节点的前驱和后继的指针的二叉树。 (zh)
- Árvore binária com costura, ou Árvore binária com fios é uma estrutura de dados derivada da Árvore de busca binária, em que os ponteiros nulos são aproveitados para armazenar o endereço do predecessor ou sucessor em in-ordem. Uma ligação de costura aproveita a memória desperdiçada por esses ponteiros para apontar para o predecessor (se o nodo não tiver filho esquerdo) ou para o sucessor (se o nodo não tiver filho direito). Isso torna o percusso in-ordem mais fácil de ser implementado e mais eficiente. (pt)
|
| rdfs:label
|
- Arbre cousu (fr)
- 스레드 이진 트리 (ko)
- Árvore binária com costura (pt)
- Threaded binary tree (en)
- Прошитое двоичное дерево (ru)
- 线索二叉树 (zh)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is rdfs:seeAlso
of | |
| is foaf:primaryTopic
of | |
