2–3 tree

From Wikipedia, the free encyclopedia
  (Redirected from 2-3 tree)
Jump to: navigation, search
2-3 tree
Type Tree
Invented 1970
Invented by John Hopcroft
Time complexity
in big O notation
Average Worst case
Space O(n) O(n)
Search O(log n) O(log n)
Insert O(log n) O(log n)
Delete O(log n) O(log n)

In computer science, a 2–3 tree is a tree data structure, where every node with children (internal node) has either two children (2-node) and one data element or three children (3-nodes) and two data elements. Nodes on the outside of the tree (leaf nodes) have no children and one or two data elements.[1][2] 2−3 trees were invented by John Hopcroft in 1970.[3]

2–3 trees are an isometry of AA trees, meaning that they are equivalent data structures. In other words, for every 2–3 tree, there exists at least one AA tree with data elements in the same order. 2–3 trees are balanced, meaning that each right, center, and left subtree contains the same or close to the same amount of data.

Properties[edit]

  • Every non-leaf is a 2-node or a 3-node. A 2-node contains one data item and has two children. A 3-node contains two data items and has 3 children.
  • All leaves are at the same level (the bottom level)
  • All data is kept in sorted order
  • Every leaf node will contain 1 or 2 fields.

Non-leaf nodes[edit]

These contain one or two fields which indicate the range of values in its subtrees. If a node has two children, it will have one field; if the node has three children, it will have two fields. Each non-leaf node will contain a value in field 1 which is greater than the largest item in its left sub-tree, but less than or equal to the smallest item in its right sub-tree (or center sub-tree, if it has three children). If that node has three children, field 2 contains a value which is greater than the largest value in the center sub-tree, but less than or equal to the smallest item in its right sub-tree. The purpose of these values is to direct a search function to the correct sub-tree and eventually to the correct data node.

Operations[edit]

Insertion[edit]

Insertion works by searching for the proper location of the key and adds it there. If the node becomes a 4-node then the node is split int two 2-nodes and the middle key is moved up to the parent. The diagram illustrates the process.

Insertion of a number in a 2-3 tree for the 3 possible cases.

See also[edit]

References[edit]

  1. ^ Gross, R. Hernández, J. C. Lázaro, R. Dormido, S. Ros (2001). Estructura de Datos y Algoritmos. Prentice Hall. ISBN 84-205-2980-X. 
  2. ^ Aho, Alfred V.; Hopcroft, John E.; Ullman, Jeffrey D. (1974). The Design and Analysis of Computer Algorithms. Addison-Wesley. , p.145-147
  3. ^ Cormen, Thomas (2009). Introduction to Algorithms. London: The MIT Press. p. 504. ISBN 978-0262033848. 

External links[edit]