| dbo:abstract
|
- In computer science, a 2–3–4 tree (also called a 2–4 tree) is a self-balancing data structure that can be used to implement dictionaries. The numbers mean a tree where every node with children (internal node) has either two, three, or four child nodes:
* a 2-node has one data element, and if internal has two child nodes;
* a 3-node has two data elements, and if internal has three child nodes;
* a 4-node has three data elements, and if internal has four child nodes;
* 2-node
* 3-node
* 4-node 2–3–4 trees are B-trees of order 4; like B-trees in general, they can search, insert and delete in O(log n) time. One property of a 2–3–4 tree is that all external nodes are at the same depth. 2–3–4 trees are isomorphic to red–black trees, meaning that they are equivalent data structures. In other words, for every 2–3–4 tree, there exists at least one red–black tree with data elements in the same order. Moreover, insertion and deletion operations on 2–3–4 trees that cause node expansions, splits and merges are equivalent to the color-flipping and rotations in red–black trees. Introductions to red–black trees usually introduce 2–3–4 trees first, because they are conceptually simpler. 2–3–4 trees, however, can be difficult to implement in most programming languages because of the large number of special cases involved in operations on the tree. Red–black trees are simpler to implement, so tend to be used instead. (en)
- Ein 2-3-4-Baum (auch (2,4)-Baum) ist in der Informatik eine Datenstruktur, genauer ein B-Baum des minimalen Verzweigungsgrades 2, das heißt, er ist ein Baum, in dem jeder Knoten zwei, drei oder maximal vier Kinder besitzt und entsprechend ein, zwei oder maximal drei Datenelemente speichert, die nach dem gewählten Ordnungskriterium aufsteigend sortiert sind. Er stellt damit zugleich einen speziellen balancierten Suchbaum dar. Wie alle B-Bäume wird auch der 2-3-4-Baum häufig zur Speicherung großer Datenmengen verwendet. Das Suchen in diesen Bäumen ist mit einer Laufzeit von O(log n) möglich. Durch geschicktes Einfügen wird der 2-3-4-Baum stets balanciert gehalten. (de)
- Un arbre 2-3-4 est un 2-4 arbre B ou arbre B d'ordre 2, c'est-à-dire un arbre comportant uniquement des 2-nœuds, 3-nœuds et 4-nœuds (un N-nœud étant un nœud possédant N-1 clés et N fils), et dont les fils bornent les clés dans les sous arbres (on se reportera à l'article arbre B pour une définition précise). En tant qu'arbre B, on peut l'utiliser pour implémenter le type abstrait table de symboles. Les opérations de recherche, d'insertion et de suppression sont en O(ln n). L'aspect le plus intéressant des arbres 2-3-4 est leur représentation sous forme d'arbres bicolores :
* Un 2-nœud est représenté par un nœud noir seul ;
* Un 3-nœud est représenté par un nœud rouge plus son père noir (un 3-nœud peut être orienté à droite ou à gauche selon que le nœud rouge est le fils droit ou gauche) ;
* Un 4-nœud est représenté par 2 nœuds rouges plus leur père noir. Cette représentation est plus simple à manipuler car il s'agit d'un arbre binaire de recherche. De plus, elle gaspille moins de place mémoire quand l'arbre contient peu de 4-nœuds.
* 2-node
* 3-node
* 4-node
* Portail de l'informatique théorique (fr)
- 2-3-4木（2-3-4き、英: 2-3-4 tree）または2-4木は計算機科学の用語であり、4次のB木（英: B-tree）と同じである。 一般に2-3-4木はB木のように辞書として使うことができるの一種である。探索、挿入、削除をO(log n)で行うことができる。ここでnは木の要素数である。 2-3-4木は木の操作において多くの特別なケースが存在するので大半のプログラミング言語において比較的実装が難しい。赤黒木(red-black tree)の方が実装が簡単で代わりに用いられる傾向がある。 (ja)
- 2-3-4 树在计算机科学中是阶为 4 的B树。 大体同B树，2-3-4 树是一种自平衡数据结构，可用於實作字典。它可以在时间内查找、插入和删除，这里的 n 是树中元素的数目。 2-3-4 树在多数编程语言中实现起来相对困难，因为在树上的操作涉及大量特殊情况。红黑树实现起来更简单一些，所以可以用它来替代。 (zh)
|
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 9128 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:name
| |
| dbp:type
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- 2-3-4木（2-3-4き、英: 2-3-4 tree）または2-4木は計算機科学の用語であり、4次のB木（英: B-tree）と同じである。 一般に2-3-4木はB木のように辞書として使うことができるの一種である。探索、挿入、削除をO(log n)で行うことができる。ここでnは木の要素数である。 2-3-4木は木の操作において多くの特別なケースが存在するので大半のプログラミング言語において比較的実装が難しい。赤黒木(red-black tree)の方が実装が簡単で代わりに用いられる傾向がある。 (ja)
- 2-3-4 树在计算机科学中是阶为 4 的B树。 大体同B树，2-3-4 树是一种自平衡数据结构，可用於實作字典。它可以在时间内查找、插入和删除，这里的 n 是树中元素的数目。 2-3-4 树在多数编程语言中实现起来相对困难，因为在树上的操作涉及大量特殊情况。红黑树实现起来更简单一些，所以可以用它来替代。 (zh)
- In computer science, a 2–3–4 tree (also called a 2–4 tree) is a self-balancing data structure that can be used to implement dictionaries. The numbers mean a tree where every node with children (internal node) has either two, three, or four child nodes:
* a 2-node has one data element, and if internal has two child nodes;
* a 3-node has two data elements, and if internal has three child nodes;
* a 4-node has three data elements, and if internal has four child nodes;
* 2-node
* 3-node
* 4-node (en)
- Ein 2-3-4-Baum (auch (2,4)-Baum) ist in der Informatik eine Datenstruktur, genauer ein B-Baum des minimalen Verzweigungsgrades 2, das heißt, er ist ein Baum, in dem jeder Knoten zwei, drei oder maximal vier Kinder besitzt und entsprechend ein, zwei oder maximal drei Datenelemente speichert, die nach dem gewählten Ordnungskriterium aufsteigend sortiert sind. Er stellt damit zugleich einen speziellen balancierten Suchbaum dar. (de)
- Un arbre 2-3-4 est un 2-4 arbre B ou arbre B d'ordre 2, c'est-à-dire un arbre comportant uniquement des 2-nœuds, 3-nœuds et 4-nœuds (un N-nœud étant un nœud possédant N-1 clés et N fils), et dont les fils bornent les clés dans les sous arbres (on se reportera à l'article arbre B pour une définition précise). En tant qu'arbre B, on peut l'utiliser pour implémenter le type abstrait table de symboles. Les opérations de recherche, d'insertion et de suppression sont en O(ln n). L'aspect le plus intéressant des arbres 2-3-4 est leur représentation sous forme d'arbres bicolores :
* 2-node
* 3-node
* (fr)
|
| rdfs:label
|
- 2-3-4-Baum (de)
- 2–3–4 tree (en)
- Arbre 2-3-4 (fr)
- 2-3-4木 (ja)
- Árvore 2-3-4 (pt)
- 2-3-4树 (zh)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |