2–3 tree

<h2 id="definitions">Definitions</h2>
<p>We say that an internal node is a 2-node if it has <i>one</i> data element and <i>two</i> children.
</p><p>We say that an internal node is a 3-node if it has <i>two</i> data elements and <i>three</i> children.
</p><p>A 4-node, with three data elements, may be temporarily created during manipulation of the tree but is never persistently stored in the tree.
</p>

<p>We say that T is a 2–3 tree if and only if one of the following statements hold:<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a>
</p>
<ul><li>T is empty. In other words, T does not have any nodes.</li>
<li>T is a 2-node with data element a. If T has left child p and right child q, then
<ul><li>p and q are 2–3 trees of the same <a href="/facts/Tree_(data_structure)/RcXz9noF">height</a>;</li>
<li>a is greater than each element in p; and</li>
<li>a is less than each data element in q.</li></ul></li>
<li>T is a 3-node with data elements a and b, where a  < b. If T has left child p, middle child q, and right child r, then
<ul><li>p, q, and r are 2–3 trees of equal height;</li>
<li>a is greater than each data element in p and less than each data element in q; and</li>
<li>b is greater than each data element in q and less than each data element in r.</li></ul></li></ul>
<h2 id="properties">Properties</h2>
<ul><li>Every internal node is a 2-node or a 3-node.</li>
<li>All leaves are at the same level.</li>
<li>All data is kept in sorted order.</li></ul>
<h2 id="operations">Operations</h2>
<h3>Searching</h3>
<p>Searching for an item in a 2–3 tree is similar to searching for an item in a <a href="/facts/Binary_search_tree/gWubNt7b">binary search tree</a>. Since the data elements in each node are ordered, a search function will be directed to the correct subtree and eventually to the correct node which contains the item.
</p>
<ol><li>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.</li>
<li>Let t be the root of T.</li>
<li>Suppose t is a leaf.
<ul><li>If d is not in t, then d is not in T. Otherwise, d is in T. We need no further steps and we're done.</li></ul></li>
<li>Suppose t is a 2-node with left child p and right child q. Let a be the data element in t. There are three cases:
<ul><li>If d is equal to a, then we've found d in T and we're done.</li>
<li>If 
  
    
      
        d
        <
        a
      
    
    {\displaystyle d<a}
  
, then set T to p, which by definition is a 2–3 tree, and go back to step 2.</li>
<li>If 
  
    
      
        d
        >
        a
      
    
    {\displaystyle d>a}
  
, then set T to q and go back to step 2.</li></ul></li>
<li>Suppose t is a 3-node with left child p, middle child q, and right child r. Let a and b be the two data elements of t, where 
  
    
      
        a
        <
        b
      
    
    {\displaystyle a<b}
  
. There are four cases:
<ul><li>If d is equal to a or b, then d is in T and we're done.</li>
<li>If 
  
    
      
        d
        <
        a
      
    
    {\displaystyle d<a}
  
, then set T to p and go back to step 2.</li>
<li>If 
  
    
      
        a
        <
        d
        <
        b
      
    
    {\displaystyle a<d<b}
  
, then set T to q and go back to step 2.</li>
<li>If 
  
    
      
        d
        >
        b
      
    
    {\displaystyle d>b}
  
, then set T to r and go back to step 2.</li></ul></li></ol>
<h3>Insertion</h3>
<p>Insertion maintains the balanced property of the tree.<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a>
</p><p>To insert into a 2-node, the new key is added to the 2-node in the appropriate order.
</p><p>To insert into a 3-node, more work may be required depending on the location of the 3-node. If the tree consists only of a 3-node, the node is split into three 2-nodes with the appropriate keys and children.
</p>

<p>If the target node is a 3-node whose parent is a 2-node, the key is inserted into the 3-node to create a temporary 4-node. In the illustration, the key 10 is inserted into the 2-node with 6 and 9. The middle key is 9, and is promoted to the parent 2-node. This leaves a 3-node of 6 and 10, which is split to be two 2-nodes held as children of the parent 3-node.
</p><p>If the target node is a 3-node and the parent is a 3-node, a temporary 4-node is created then split as above. This process continues up the tree to the root. If the root must be split, then the process of a single 3-node is followed: a temporary 4-node root is split into three 2-nodes, one of which is considered to be the root. This operation grows the height of the tree by one.
</p>
<h3>Deletion</h3>
<p>Deleting a key from a non-leaf node can be done by replacing it by its immediate predecessor or successor, and then deleting the predecessor or successor from a leaf node.  Deleting a key from a leaf node is easy if the leaf is a 3-node.  Otherwise, it may require creating a temporary 1-node which may be absorbed by reorganizing the tree, or it may repeatedly travel upwards before it can be absorbed, as a temporary 4-node may in the case of insertion.  Alternatively, it's possible to use an algorithm which is both top-down and bottom-up, creating temporary 4-nodes on the way down that are then destroyed as you travel back up.  Deletion methods are explained in more detail in the references.<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a><a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a> 
</p>
<h3>Parallel operations</h3>
<p>Since 2–3 trees are similar in structure to <a href="/facts/Red%25E2%2580%2593black_tree/ckgWTV7G">red–black trees</a>, <a href="/facts/Red%25E2%2580%2593black_tree/ckgWTV7G">parallel algorithms for red–black trees</a> can be applied to 2–3 trees as well.
</p>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/2%25E2%2580%25933%25E2%2580%25934_tree/kFdeSPS4">2–3–4 tree</a></li>
<li><a href="/facts/2%25E2%2580%25933_heap/F1cnoDm1">2–3 heap</a></li>
<li><a href="/facts/AA_tree/RvWECz8n">AA tree</a></li>
<li><a href="/facts/B-tree/IHE2l8GR">B-tree</a></li>
<li><a href="/facts/(a%2cb)-tree/lLon4yTJ">(a,b)-tree</a></li>
<li><a href="/facts/Finger_tree/XkeWM77c">Finger tree</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Knuth, Donald M (1998). "6.2.4". The Art of Computer Programming. Vol. 3 (2 ed.). Addison Wesley. ISBN 978-0-201-89685-5. The 2–3 trees defined at the close of Section 6.2.3 are equivalent to B-Trees of order 3. <a href="978-0-201-89685-5" target="_blank">978-0-201-89685-5</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>R. Hernández; J. C. Lázaro; R. Dormido; S. Ros (2001). Estructura de Datos y Algoritmos. Prentice Hall. ISBN 84-205-2980-X. <a href="84-205-2980-X" target="_blank">84-205-2980-X</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>Aho, Alfred V.; Hopcroft, John E.; Ullman, Jeffrey D. (1974). The Design and Analysis of Computer Algorithms. Addison-Wesley. ISBN 978-0-201-00029-0., pp.145–147 <a href="978-0-201-00029-0" target="_blank">978-0-201-00029-0</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
<li id="fn:4"><p>Cormen, Thomas (2009). Introduction to Algorithms. London: The MIT Press. pp. 504. ISBN 978-0-262-03384-8. <a href="978-0-262-03384-8" target="_blank">978-0-262-03384-8</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li>
<li id="fn:5"><p>Sedgewick, Robert; Wayne, Kevin (2011). "3.3". Algorithms (4 ed.). Addison Wesley. ISBN 978-0-321-57351-3. <a href="978-0-321-57351-3" target="_blank">978-0-321-57351-3</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li>
<li id="fn:6"><p>Sedgewick, Robert; Wayne, Kevin (2011). "3.3". Algorithms (4 ed.). Addison Wesley. ISBN 978-0-321-57351-3. <a href="978-0-321-57351-3" target="_blank">978-0-321-57351-3</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li>
<li id="fn:7"><p>Sedgewick, Robert; Wayne, Kevin (2011). "3.3". Algorithms (4 ed.). Addison Wesley. ISBN 978-0-321-57351-3. <a href="978-0-321-57351-3" target="_blank">978-0-321-57351-3</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li>
<li id="fn:8"><p>"2-3 Trees", Lyn Turbak, handout #26, course notes, CS230 Data Structures, Wellesley College, December 2, 2004.  Accessed Mar. 11, 2024. <a href="https://www.cs.princeton.edu/~dpw/courses/cos326-12/ass/2-3-trees.pdf" target="_blank">https://www.cs.princeton.edu/~dpw/courses/cos326-12/ass/2-3-trees.pdf</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li>
</ol>

2–3 tree open-in-new

2–3 tree