Home

Implementing a 2 3 Tree in C++17

The complete source code is at https://github.com/kkruecke/23tree-in-cpp

2 3 Tree Discussions

The following sources discuss 2 3 Trees and their algorithms:

1. Balanced Trees from online book Algorithms 4th Edition.
2. Data Structures Balanced Trees from Univ. of Nevada CS 302 Data Structures.
3. Balanced Search Trees from Simon Frazer Univ. Data Structure and Programming.
4. Deletion in 2 3 trees from USC Data Structure and Object Oriented Design.
5. Virgina Tech 2 3 Tree slides from Virgina Tech Data Structures and ObjectOriented Development.

Implementation Overview

Nested Union tree23<Key, Value>::KeyValue

The key and value are stored in a KeyValue object that is a union of two std::pair's. KeyValue has a move assignement and move constructor to improve the efficiency of the tree insertion algorithm. Using a unions allows us to write to the std::pair<Key, Value> member without the need for constantly doing const_cast<Key&>(key) = k, but also allow the tree23<Key,Value>'s iterators to return pair<const Key, Value> references, again without the need to use explicit const_cast<> throughout the code.

See the comments in the code for more implementation details.