2 3 tree implemented in C++. See Implementing a 2 3 Tree in C++. The code was compiled using g++ compiler with the option -std=c++2a .
Everything seems to work, including the iterator classes, with the exeception that rbegin() seems to return an iterator that does not work properly
Using std::shared_ptr improves efficiency. For example, when we copy a tree, we only have to copy a shared_ptr, but there is a drawback. For the details see:
-
Stackoverflow discussion of implementing B trees using shared pointers
-
C++11 Smart Pointer Tutorial Series: Part 1 of **shared_ptr Tutorial and Examples** <https://thispointer.com/learning-shared_ptr-part-1-usage-details/>_ -
C++11 Smart Pointer – Part 5: shared_ptr, Binary trees and the problem of Cyclic References <https://thispointer.com/shared_ptr-binary-trees-and-the-problem-of-cyclic-references/>_ -
Implementation of Binary Search Trees Via Smart Pointer <https://thispointer.com/shared_ptr-binary-trees-and-the-problem-of-cyclic-references/>_
Problem with this thinking: See comments in ~/bst/todo.rst
The 4-node is used to combine a 3-node and a new key, initially the key to be inserted. The question is, what do we do with the value associated with the key, or in the case of emplace(), what do we do with the constructor arguments associated with a value that will be created in place from existing memory? See http://algs4.cs.princeton.edu/33balanced.
Tree Iteration Implementation Discussions <https://data-structs.kurttest.com/notes/tree-iteration.html>_