A 2-3-4 tree (also called a 2-4 tree), in computer science, is a self-balancing data structure that is commonly used to implement dictionaries. The numbers means a tree where every node with children has either two children (2-node) and one data element or three children (3-node) and two data elements or four children (4-node) and three data elements. 2-3-4 tree 2-node. svg 2 node 2-3-4-tree 3-node. svg 3 node 2-3-4-tree 4-node.

PropertyValue
dbpedia-owl:abstract
  • Ein 2-3-4-Baum ist in der Informatik eine Datenstruktur, genauer ein B-Baum des 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.
  • A 2-3-4 tree (also called a 2-4 tree), in computer science, is a self-balancing data structure that is commonly used to implement dictionaries. The numbers means a tree where every node with children has either two children (2-node) and one data element or three children (3-node) and two data elements or four children (4-node) and three data elements. 2-3-4 tree 2-node. svg 2 node 2-3-4-tree 3-node. svg 3 node 2-3-4-tree 4-node. svg 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 an isometry of 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.
  • 2-3-4木（2-3-4き、Template:Lang-en-short）または2-4木は計算機科学の用語であり、4次のB木（Template:Lang-en-short）と同じである。 一般に2-3-4木はB木のように辞書として使うことができる平衡木の一種である。探索、挿入、削除をO(log n)で行うことができる。ここでnは木の要素数である。 2-3-4木は木の操作において多くの特別なケースが存在するので大半のプログラミング言語において比較的実装が難しい。赤黒木の方が実装が簡単で代わりに用いられる傾向がある。
  • 2-3-4 树在计算机科学中是阶为 4 的B树。 大体上同B树一样，2-3-4 树是可以用做字典的一种自平衡数据结构。它可以在O（log n）时间内查找、插入和删除，这里的 n 是树中元素的数目。 2-3-4 树在多数编程语言中实现起来相对困难，因为在树上的操作涉及大量的特殊情况。红黑树实现起来更简单一些，所以可以用它来替代。
  • 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.
dbpedia-owl:wikiPageExternalLink
dcterms:subject
rdfs:comment
  • 2-3-4木（2-3-4き、Template:Lang-en-short）または2-4木は計算機科学の用語であり、4次のB木（Template:Lang-en-short）と同じである。 一般に2-3-4木はB木のように辞書として使うことができる平衡木の一種である。探索、挿入、削除をO(log n)で行うことができる。ここでnは木の要素数である。 2-3-4木は木の操作において多くの特別なケースが存在するので大半のプログラミング言語において比較的実装が難しい。赤黒木の方が実装が簡単で代わりに用いられる傾向がある。
  • 2-3-4 树在计算机科学中是阶为 4 的B树。 大体上同B树一样，2-3-4 树是可以用做字典的一种自平衡数据结构。它可以在O（log n）时间内查找、插入和删除，这里的 n 是树中元素的数目。 2-3-4 树在多数编程语言中实现起来相对困难，因为在树上的操作涉及大量的特殊情况。红黑树实现起来更简单一些，所以可以用它来替代。
  • Ein 2-3-4-Baum ist in der Informatik eine Datenstruktur, genauer ein B-Baum des 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.
  • A 2-3-4 tree (also called a 2-4 tree), in computer science, is a self-balancing data structure that is commonly used to implement dictionaries. The numbers means a tree where every node with children has either two children (2-node) and one data element or three children (3-node) and two data elements or four children (4-node) and three data elements. 2-3-4 tree 2-node. svg 2 node 2-3-4-tree 3-node. svg 3 node 2-3-4-tree 4-node.
  • 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).
rdfs:label
  • 2-3-4-Baum
  • Arbre 2-3-4
  • 2-3-4 tree
  • 2-3-4木
  • 2-3-4树
owl:sameAs
foaf:page
is dbpedia-owl:wikiPageRedirects of
is owl:sameAs of
is foaf:primaryTopic of