2–3 tree

From Wikipedia, the free encyclopedia - View original article

2-3 tree
TypeTree
Invented1970
Invented byJohn Hopcroft
Time complexity
in big O notation
AverageWorst case
SpaceO(n)O(n)
SearchO(log n)O(log n)
InsertO(log n)O(log n)
DeleteO(log n)O(log n)
 
  (Redirected from 2-3 tree)
Jump to: navigation, search
2-3 tree
TypeTree
Invented1970
Invented byJohn Hopcroft
Time complexity
in big O notation
AverageWorst case
SpaceO(n)O(n)
SearchO(log n)O(log n)
InsertO(log n)O(log n)
DeleteO(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.

Definitions[edit]

2-node[edit]

We say that a node is a 2-node if and only if it has one data element and two children if it is an internal node.

3-node[edit]

We say that a node is a 3-node if and only if it has two data elements and three children if it is an internal node.

4-node[edit]

We say that a node is a 4-node if and only if it has three data elements and four children if it is an internal node.

2-3 tree[edit]

We say that T is a 2-3 tree if and only if one of the following statements hold:

Properties[edit]

Operations[edit]

Searching[edit]

Searching for an item in a 2-3 tree is similar to searching for an item in a binary search tree. Since the data elements in each node is ordered, a search function will be directed to the correct subtree and eventually to the correct node which contains the item.

  1. Let T be a 2-3 tree and d be the data element we want to find. If T is empty, then d is not in T and we're done.
  2. Let r be the root of T.
  3. Suppose r is a leaf. If d is not in r, then d is not in T. Otherwise, d is in T. In particular, d can be found at a leaf node. We need no further steps and we're done.
  4. Suppose r is a 2-node with left child L and right child R. Let e be the data element in r. There are three cases: If d is equal to e, then we've found d in T and we're done. If d < e, then set T to L, which by definition is a 2-3 tree, and go back to step 2. If d > e, then set T to R and go back to step 2.
  5. Suppose r is a 3-node with left child L, middle child M, and right child R. Let a and b be the two data elements of r, where a < b. There are four cases: If d is equal to a or b, then d is in T and we're done. If d < a, then set T to L and go back to step 2. If a < d < b, then set T to M and go back to step 2. If d > b, then set T to R and go back to step 2.

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 from 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]