| rdfs:comment
| - En informatique, un arbre ternaire de recherche (ATR ou TST — pour Ternary Search Tree en anglais) est une structure de données adaptée pour la recherche et combinant les avantages d'un arbre binaire de recherche et d'un arbre préfixe. (fr)
- In computer science, a ternary search tree is a type of trie (sometimes called a prefix tree) where nodes are arranged in a manner similar to a binary search tree, but with up to three children rather than the binary tree's limit of two. Like other prefix trees, a ternary search tree can be used as an associative map structure with the ability for incremental string search. However, ternary search trees are more space efficient compared to standard prefix trees, at the cost of speed. Common applications for ternary search trees include spell-checking and auto-completion. (en)
- Em ciência da computação, um árvore ternária de busca é um tipo de trie (às vezes chamado de árvore de prefixos), onde os nós são organizados em uma forma semelhante a uma árvore de busca binária, mas com até três filhos, em vez de apenas dois como em uma árvore binária. Assim como outras tries, uma árvore ternária de busca pode ser usada como um mapa associativo com melhores capacidades para a busca em strings. No entanto, árvore ternária de busca são mais eficientes em relação às outras tries, quando se fala em custo de velocidade. Suas aplicações mais comuns incluem a verificação ortográfica e auto-complemento. (pt)
- В інформатиці трійкове дерево пошуку — це тип префіксного дерева, де вузли розташовані таким чином, як в двійковому дереві пошуку, але мають щонайбільше троє дітей, замість двох (як у двійковому дереві пошуку). Як і інші префіксні дерева, трійкове дерево пошуку може бути використано як асоціативний масив з можливістю поступового пошуку рядків. Зазвичай трійкові дерева пошуку мають кращу просторову складність у порівнянні зі звичайними префіксними деревами, нехтуючи часовою складністю. Трійкові дерева пошуку переважно застосовують для написання алгоритмів перевірки орфографії та автодоповнення. (uk)
- 三叉搜索树在计算机科学中是trie树或前缀树的一种实现，树的各个节点之间的结构类似二叉搜索树。和其他的前缀树一样，三叉搜索树可以用于实现带前缀搜索功能的关联数组。三叉搜索树比标准的前缀树更节省空间，但是牺牲了部分查找速度。三叉搜索树常用于实现拼写检查和自动完成功能。 (zh)
- 三分探索木（さんぶんたんさくぎ、英: ternary search tree）は、トライ木の各ノードを二分探索木として表現したデータ構造である。各ノードは文字列中の文字と以下の三つの子ノードを持つ。
* その文字の代わりに、より小さな文字を指す左ノード
* その文字の代わりに、より大きな文字を指す右ノード
* その文字の次の文字を指す中央ノード 他のトライ木構造と同じく、三分探索木の各ノードは格納された文字列の接頭辞に対応している。中央ノードに格納された木は、そこに至るまでのノードを共通接頭辞として持つ。 c / | \ a u h | | | \ t t e u / / | / | s p e i s 上記の三分探索木は "as", "at", "cup", "cute", "he", "i", "us" が値として格納されている。三分探索木から値を取得するには次のような操作を行う。 このようにして、三分探索木から値を取得できる。 なお、値として "cute" と "cut" を含む（他の値の部分文字列であるような値を含む）ような三分探索木は、終端文字を表すノードを用いることで表現できる。上記の例に値 "cut" を追加した場合の例を以下に示す（ここでは終端文字を # と表している）。 (ja)
- Drzewo trójkowe (ternary search tree) – struktura danych do wyszukiwania napisów, łącząca szybkość działania drzewa trie, oraz małe użycie pamięci drzew binarnych. W drzewach binarnych każdy węzeł przechowuje kopię klucza, i klucz ten jest porównywany z poszukiwanym kluczem na każdym poziomie drzewa w głąb rekursji. Z kolei w drzewach trie na każdym poziomie drzewa, wybieramy następne poddrzewo na podstawie następnej litery w poszukiwanym kluczu. Drzewa trie, starają się wyeliminować powtarzanie porównywania, co może być kosztowne, w przypadku podobnych prefiksów w słowach (co jest powszechne w językach naturalnych, jako że słowa często mają podobny początek, i różnią się końcówkami). Drzewa trie rozwiązują to poprzez umieszczenie tablicy wskaźników w każdym węźle. Każdy indeks tablicy odp (pl)
|
| has abstract
| - En informatique, un arbre ternaire de recherche (ATR ou TST — pour Ternary Search Tree en anglais) est une structure de données adaptée pour la recherche et combinant les avantages d'un arbre binaire de recherche et d'un arbre préfixe. (fr)
- In computer science, a ternary search tree is a type of trie (sometimes called a prefix tree) where nodes are arranged in a manner similar to a binary search tree, but with up to three children rather than the binary tree's limit of two. Like other prefix trees, a ternary search tree can be used as an associative map structure with the ability for incremental string search. However, ternary search trees are more space efficient compared to standard prefix trees, at the cost of speed. Common applications for ternary search trees include spell-checking and auto-completion. (en)
- 三分探索木（さんぶんたんさくぎ、英: ternary search tree）は、トライ木の各ノードを二分探索木として表現したデータ構造である。各ノードは文字列中の文字と以下の三つの子ノードを持つ。
* その文字の代わりに、より小さな文字を指す左ノード
* その文字の代わりに、より大きな文字を指す右ノード
* その文字の次の文字を指す中央ノード 他のトライ木構造と同じく、三分探索木の各ノードは格納された文字列の接頭辞に対応している。中央ノードに格納された木は、そこに至るまでのノードを共通接頭辞として持つ。 c / | \ a u h | | | \ t t e u / / | / | s p e i s 上記の三分探索木は "as", "at", "cup", "cute", "he", "i", "us" が値として格納されている。三分探索木から値を取得するには次のような操作を行う。 1.
* 頂点ノードから「子に中央ノードを持たないノード」までを辿り、その経路を保存する 2. 1.
* "c-a-t-s" 3. 2.
* "c-a-t" 4. 3.
* "c-u-t-p" 5. 4.
* "c-u-t-e" 6. 5.
* "c-h-e" 7. 6.
* "c-h-u-i" 8. 7.
* "c-h-u-s" 9.
* それらの経路に対して頂点から順に、子が中央ノードでなければ自身の文字を消す 10. 1.
* "a-s" 11. 2. 1.
* "c-a-t-s" の "c" に対して "a" は左ノードで繋がっているので "c" を消す 12. 3. 2.
* "a-t-s" の "a" に対して "t" は中央ノードで繋がっているので "a" を残す 13. 4. 3.
* "a-t-s" の "t" に対して "s" は左ノードで繋がっているので "t" を消す 14. 5. 4.
* "a-s" の "s" は終端ノードなので残す 15. 6.
* "a-t" 16. 7.
* "c-u-p" 8.
* "c-u-t-e" 17. 9.
* "h-e" 18. 10.
* "i" 19. 11.
* "u-s" このようにして、三分探索木から値を取得できる。 なお、値として "cute" と "cut" を含む（他の値の部分文字列であるような値を含む）ような三分探索木は、終端文字を表すノードを用いることで表現できる。上記の例に値 "cut" を追加した場合の例を以下に示す（ここでは終端文字を # と表している）。 c / | \ a u h | | | \ t t e u / / | / | s p e i s / # 二分探索木と同様、三分探索木を平衡させることも可能である。長さmの文字列を、要素nを格納した平衡三分探索木から探索するのに必要な文字比較はたかだかm + log2nである。比較が文字列ではなく文字である点に注意されたい。 トライ木おける基数木と同様なやり方で、余計なノードをまとめて三分探索木を圧縮することも可能である。例えば上記の最初の例では、 "cu", "te", "he" および "us" は一つのノードに圧縮できる。 (ja)
- Drzewo trójkowe (ternary search tree) – struktura danych do wyszukiwania napisów, łącząca szybkość działania drzewa trie, oraz małe użycie pamięci drzew binarnych. W drzewach binarnych każdy węzeł przechowuje kopię klucza, i klucz ten jest porównywany z poszukiwanym kluczem na każdym poziomie drzewa w głąb rekursji. Z kolei w drzewach trie na każdym poziomie drzewa, wybieramy następne poddrzewo na podstawie następnej litery w poszukiwanym kluczu. Drzewa trie, starają się wyeliminować powtarzanie porównywania, co może być kosztowne, w przypadku podobnych prefiksów w słowach (co jest powszechne w językach naturalnych, jako że słowa często mają podobny początek, i różnią się końcówkami). Drzewa trie rozwiązują to poprzez umieszczenie tablicy wskaźników w każdym węźle. Każdy indeks tablicy odpowiada możliwej literze alfabetu (np. dla alfabetu łacińskiego mogło to bybyć 26 liter + 1 pozycje dla innych znaków). Rozwiązanie to jest obarczone jednak bardzo dużym narzutem wykorzystania pamięci (wiele węzłów w tym liście przechowuje całą tablicę, chociaż niepustych wskaźników jest bardzo mało - np. w języku polskim po prefiksie "Krak" niepuste są, 'o', 'a', 'e', 'ó', '-', 's', 'i', 'n', 'u', 'w', natomiast puste są wszystkie inne, np. 'b', 'c', 'd', 'f', 'g', ..., 'z'). Drzewa trójkowe eliminują ten problem. Problem jest ten znacznie dotkliwszy w przypadku dużych alfabetów (np. chiński), czy słowników wielojęzycznych (opartych na Unicode). Drzewo trójkowe, można rozumieć jako małe drzewo binarne, w których tablica została zastąpiona dodatkowym drzewem. (pl)
- Em ciência da computação, um árvore ternária de busca é um tipo de trie (às vezes chamado de árvore de prefixos), onde os nós são organizados em uma forma semelhante a uma árvore de busca binária, mas com até três filhos, em vez de apenas dois como em uma árvore binária. Assim como outras tries, uma árvore ternária de busca pode ser usada como um mapa associativo com melhores capacidades para a busca em strings. No entanto, árvore ternária de busca são mais eficientes em relação às outras tries, quando se fala em custo de velocidade. Suas aplicações mais comuns incluem a verificação ortográfica e auto-complemento. (pt)
- В інформатиці трійкове дерево пошуку — це тип префіксного дерева, де вузли розташовані таким чином, як в двійковому дереві пошуку, але мають щонайбільше троє дітей, замість двох (як у двійковому дереві пошуку). Як і інші префіксні дерева, трійкове дерево пошуку може бути використано як асоціативний масив з можливістю поступового пошуку рядків. Зазвичай трійкові дерева пошуку мають кращу просторову складність у порівнянні зі звичайними префіксними деревами, нехтуючи часовою складністю. Трійкові дерева пошуку переважно застосовують для написання алгоритмів перевірки орфографії та автодоповнення. (uk)
- 三叉搜索树在计算机科学中是trie树或前缀树的一种实现，树的各个节点之间的结构类似二叉搜索树。和其他的前缀树一样，三叉搜索树可以用于实现带前缀搜索功能的关联数组。三叉搜索树比标准的前缀树更节省空间，但是牺牲了部分查找速度。三叉搜索树常用于实现拼写检查和自动完成功能。 (zh)
|
![[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)