Vwwxrf

I am a hobbyist computer programmer trying to learn modern C++ (in this case C++17). I thought it might be an interesting challenge to write a Binary Search Tree similar to std::map while using heap-like array structure to store the elements of the tree such that the index of the parent node is always half that of the child nodes and the root node index is one. As expected this lead to a poor performing implementation (unlike moving pointers around, elements needed to be moved around the array (std::vector) one at a time). During the course of this work I did learn of the DeBruijn algorithm for determining the most significant bit (http://supertech.csail.mit.edu/papers/debruijn.pdf). I did make some naming design choices that may be unconventional: variables (including constexpr variables) are all snake_case as are all of the public facing std::map-like functions. Internal private functions are camelCase as are non-STL functions (isBST, viewTree, etc.) that are used for debugging and enum classes are CamelCase. I hope folks aren’t too offended by these choices, but they helped me keep things straight.
This BST uses the AVL self-balancing method (yes, I know std::map uses red-black), and I must confess some of the weights did get away from me. In the end I resorted to some on-the-fly reweighting schemes that probably make the program even slower than it would have been without resorting to this method (see rebalance – reweight (pivot) – should be totally unnecessary, but I never found its cause. Extra thanks to the person who finds the missing weight term). During the course of this project I needed to come up with methods to compute how to shift nodes around to simulate moving sub-trees. Suggestions, better methods within these constraints, etc. will be appreciated.

BSTree.hpp:

#pragma once
#ifndef BSTREE
#define BSTREE

#include <cstdint>
#include <functional>
#include <iomanip>
#include <iostream>
#include <queue>
#include <sstream>
#include <stack>
#include <utility>
#include <vector>
#include <gsl.h>
#include <stdexcept>

constexpr std::size_t min_size = 2;
constexpr std::size_t root_node = 1;
constexpr std::size_t default_depth = 4;
constexpr std::size_t out_of_range = 0;
constexpr void printSpaces(std::size_t num)

 for (std::size_t i = 0; i < num; ++i) std::cout << ' ';

constexpr std::size_t leftChild(size_t index)

 return index << 1;

constexpr std::size_t rightChild(size_t index)

 return (index << 1) + 1;

constexpr std::size_t myParent(size_t index)

 return index >> 1;

constexpr bool isLeftEdge(std::size_t index) = temp >> 16;
 return temp + 1 == index;

constexpr bool isRightEdge(std::size_t index) = temp >> 8;
 temp 
enum class Justify

 Left,
 Right,
 Center
;
enum class ChildType :bool

 Left,
 Right
;
constexpr ChildType whatType(std::size_t index) 
 if(index & 1) return ChildType::Right;
 return ChildType::Left;


template <class K, class M = char>
class BSTree 
public:
 struct Node;
 using key_type = K;
 using key_compare = std::function<bool(const key_type&, const key_type&)>;
 using value_type = std::pair<K, M>;
 using mapped_type = M;
 using reference = value_type& ;
 using const_reference = const value_type&;
 using size_type = std::size_t;
 using container_type = std::vector<Node>;
 template <bool isconst> struct bstIterator;
 class value_compare;
 using iterator = bstIterator<false>;
 using const_iterator = bstIterator<true>;

 BSTree(std::size_t size = min_size);
 BSTree(std::size_t size, const key_compare fn);
 mapped_type& at(const key_type& key);
 const mapped_type& at(const key_type& key) const;
 iterator begin();
 const_iterator begin() const;
 const_iterator cbegin() const;
 void clear();
 std::size_t count(const key_type& key) const;
 const_iterator cend() const noexcept;
 const_iterator crbegin() const;
 const_iterator crend() const noexcept;
 iterator end() noexcept;
 const_iterator end() const noexcept;
 std::pair<iterator, iterator> equal_range(const key_type& key);
 std::pair<const_iterator, const_iterator>
 equal_range(const key_type& key) const;
 iterator erase(const_iterator position);
 iterator erase(const_iterator first, const_iterator last);
 std::size_t erase(const key_type& key);
 iterator find(const key_type key);
 const_iterator find(const key_type key) const;
 std::size_t height();
 std::pair<typename BSTree<K, M>::iterator, bool>
 insert(const key_type& key, const mapped_type& mapped = mapped_type());
 std::pair<typename BSTree<K, M>::iterator, bool> 
 insert(const value_type & value);
 iterator insert(iterator, const value_type & value);
 template <class InputIterator>
 void insert(InputIterator first, InputIterator last);
 void insert(std::initializer_list<value_type> il);
 bool isBalanced();
 bool isBST();
 key_compare key_comp() const;
 iterator lower_bound(const key_type& key);
 const_iterator lower_bound(const key_type& key) const;
 mapped_type& operator[](const key_type& key);
 void reserve(std::size_t size);
 std::size_t size() const noexcept;
 void swap(BSTree&) noexcept;
 iterator rbegin();
 const_iterator rbegin() const;
 iterator rend() noexcept;
 const_iterator rend() const noexcept;
 iterator upper_bound(const key_type & key);
 const_iterator upper_bound(const key_type & key) const;
 value_compare value_comp;
 void viewKeys();
 void viewTree(std::size_t root = root_node,
 std::size_t depth = default_depth);

 class value_compare
 
 friend class BSTree;
 protected:
 key_compare comp;
 value_compare(key_compare c):comp(c) 
 public:
 using result_type = bool;
 using first_argument_type = value_type;
 using second_argument_type = value_type;
 bool operator()(const value_type& a, const value_type& b) const
 
 return comp(a.first, b.first);
 
 ;

 template <bool isconst = false>
 struct bstIterator
 
 public:
 using value_type = std::pair<K, M>;
 using reference = typename std::conditional_t
 < isconst, value_type const &, value_type & >;
 using pointer = typename std::conditional_t
 < isconst, value_type const *, value_type * >;
 using vec_pointer = typename std::conditional_t
 <isconst, std::vector<Node> const *, std::vector<Node> *>;
 using key_compare_pointer = typename std::conditional_t
 <isconst, std::function<bool(const K&, const K&)> const *, 
 std::function<bool(const K&, const K&)> *>;
 using iterator_category = std::bidirectional_iterator_tag;

 bstIterator() noexcept : ptrToBuffer(nullptr),
 index_(0), reverse_(false), ptrToComp(nullptr) 
/*
* copy/conversion constructor
*/
 bstIterator(const BSTree<K, M>::bstIterator<false>& i) noexcept : 
 ptrToBuffer(i.ptrToBuffer),
 index_(i.index_),
 reverse_(i.reverse_),
 ptrToComp(i.ptrToComp) 
/*
* dereferencing and other operators
*/
 reference operator*() 
 if (index_ == out_of_range) 
 std::stringstream ss;
 ss << "nPointer Out Of Range!n";
 throw std::out_of_range(ss.str());
 
 return (*ptrToBuffer).at(index_).value_;
 
 pointer operator->() return &(operator *()); 
 bstIterator& operator++ () 
 if (!reverse_) 
 if (index_ == out_of_range) 
 std::stringstream ss;
 ss << "nOut Of Range: operator++n";
 throw std::out_of_range(ss.str());
 
 nextIndex();
 return *this;
 
 if (index_ != out_of_range) previousIndex();
 else index_ = highest(root_node);
 return *this;
 
 bstIterator operator ++(int) 
 const bstIterator iter = *this;
 if (!reverse_) 
 if (index_ == out_of_range) 
 std::stringstream ss;
 ss << "nOut Of Range: operator ++(int)n";
 throw std::out_of_range(ss.str());
 
 nextIndex();
 return iter;
 
 if(index_ != out_of_range) previousIndex();
 else index_ = highest(root_node);
 return iter;
 
 bstIterator& operator --() 
 if (reverse_) 
 if (index_ == out_of_range) 
 std::stringstream ss;
 ss << "nOut Of Range: operator--n";
 throw std::out_of_range(ss.str());
 
 nextIndex();
 return *this;
 
 if (index_ != out_of_range) previousIndex();
 else index_ = highest(root_node);
 return *this;
 
 bstIterator operator --(int) 
 const bstIterator iter = *this;
 if (reverse_) 
 if (index_ == out_of_range) 
 std::stringstream ss;
 ss << "nOut Of Range: operator --(int)n";
 throw std::out_of_range(ss.str());
 
 nextIndex();
 return iter;
 
 if (index_ != out_of_range) previousIndex();
 else index_ = highest(root_node);
 return iter;
 
 bool operator==(const bstIterator &other) noexcept 
 if (comparable(other))
 return (index_ == other.index_);
 return false;
 
 bool operator!=(const bstIterator &other) noexcept 
 if (comparable(other)) return !this->operator==(other);
 return true;
 
 friend class BSTree<K, M>;
 private:
 inline bool comparable(const bstIterator & other) noexcept 
 return (reverse_ == other.reverse_);
 
 std::size_t highest(std::size_t root) 
 while ((*ptrToBuffer).at(root).rnode) root = rightChild(root);
 return root;
 
 std::size_t lowest(std::size_t root) 
 while ((*ptrToBuffer).at(root).lnode) root = leftChild(root);
 return root;
 
 void nextIndex() 
 if ((*ptrToBuffer).at(index_).rnode) 
 index_ = lowest(rightChild(index_));
 return;
 
 if (!isRightEdge(index_)) 
 const key_type key = (*ptrToBuffer).at(index_).key();
 index_ = myParent(index_);
 while ((*ptrToComp)((*ptrToBuffer).at(index_).key(), key)) 
 index_ = myParent(index_);
 
 else index_ = out_of_range;
 
 void previousIndex() 
 if ((*ptrToBuffer).at(index_).lnode) 
 index_ = highest(leftChild(index_));
 return;
 
 if (!isLeftEdge(index_)) 
 const key_type key = (*ptrToBuffer).at(index_).key();
 index_ = myParent(index_);
 while ((*ptrToComp)(key, (*ptrToBuffer).at(index_).key())) 
 index_ = myParent(index_);
 
 else index_ = out_of_range;
 

 vec_pointer ptrToBuffer;
 size_type index_;
 bool reverse_;
 key_compare_pointer ptrToComp;
 ;

private:
 struct Node 
 Node(key_type key = key_type(), mapped_type mapped = mapped_type()) 
 noexcept : value_(std::make_pair(key, mapped)), lnode(false), 
 rnode(false) 
 Node(value_type value) : value_(value), lnode(false), rnode(false) 
 Node(const Node &node) : value_(node.value_), lnode(node.lnode), 
 rnode(node.rnode) 
 virtual ~Node() = default;
 Node& operator=(const Node&) = default;
 Node(Node&&) = default;
 Node& operator=(Node&&) = default;

 key_type& key() noexcept return value_.first; 
 const key_type& key() const noexcept return value_.first; 
 mapped_type& mapped() noexcept return value_.second; 
 const mapped_type& mapped() const return value_.second; 
 void printKey(std::size_t size, Justify just);

 value_type value_;
 bool lnode;
 bool rnode;
 ;
 uint8_t msbDeBruijn32(uint32_t v) noexcept;
 void moveDown(std::size_t root, ChildType type);
 void shift(std::size_t root, int diff);
 void moveUp(std::size_t);
 void shiftLeft(std::size_t);
 void shiftRight(std::size_t);
 void rotateRight(std::size_t index);
 void rotateLeft(std::size_t index);
 void rotateLR(std::size_t index);
 void rotateRL(std::size_t index);
 void reweight(std::size_t index);
 bool rebalanceRoot();
 bool rebalance(std::size_t index, bool increase);
 void simpleRemove(std::size_t parent, ChildType type);
 std::size_t bottomNode(std::size_t current, ChildType type);
 void complexRemove(std::size_t child, ChildType type);
 void wipeout(std::size_t child, ChildType type);
 std::size_t locate(key_type key, std::size_t start = root_node);
 std::size_t erase(const key_type& key, std::size_t start);
 std::size_t height(std::size_t node);
 void inject(std::size_t index, iterator& iter, key_type key, 
 mapped_type mapped, ChildType type);
 std::pair<typename BSTree<K, M>::iterator, bool>
 insert(std::size_t, const key_type & , const mapped_type & );
 iterator bound(const key_type & key, bool upper);
 bool isBalanced(std::size_t index);
 bool isBST(std::size_t current);
 void inorder(std::size_t index, 
 std::function<void(key_type&, mapped_type&)> fn);
 void traverseByLevel(std::size_t root, std::size_t max_level, 
 std::function<void(std::size_t, std::size_t)> fn);

 std::size_t node_count;
 std::vector<Node> nodes;
 std::vector<int8_t> weights;
 key_compare comp;
;

template<class K, class M>
inline BSTree<K, M>::BSTree(std::size_t size) : comp(std::less<K>()), 
value_comp(std::less<K>())

 try 
 nodes.reserve(size);
 weights.reserve(size);
 
 catch (const std::exception& e) 
 throw;
 
 node_count = 0;


template<class K, class M>
inline BSTree<K, M>::BSTree(std::size_t size, 
 const key_compare fn) : comp(fn), value_comp(fn)

 try 
 nodes.reserve(size);
 weights.reserve(size);
 
 catch (const std::exception& e) 
 throw;
 
 node_count = 0;


template<class K, class M>
inline typename BSTree<K, M>::mapped_type & 
BSTree<K, M>::at(const key_type & key)

 const std::size_t index = locate(key);
 if (index == out_of_range) 
 std::stringstream ss;
 ss << "nOut Of Range for key: "" << key << ""n";
 throw std::out_of_range(ss.str());
 
 return nodes.at(index).mapped();


template<class K, class M>
inline const typename BSTree<K, M>::mapped_type & 
BSTree<K, M>::at(const key_type & key) const

 std::size_t index = locate(key);
 if (index == out_of_range) 
 std::stringstream ss;
 ss << "nOut Of Range for key: "" << key << ""n";
 throw std::out_of_range(ss.str());
 
 return nodes.at(index).mapped();


template<class K, class M>
inline typename BSTree<K, M>::iterator BSTree<K, M>::begin()

 iterator iter;
 iter.ptrToBuffer = &nodes;
 iter.index_ = iter.lowest(root_node);
 iter.reverse_ = false;
 iter.ptrToComp = &comp;
 return iter;


template<class K, class M>
inline typename BSTree<K, M>::const_iterator BSTree<K, M>::begin() const

 return cbegin();


template<class K, class M>
inline typename BSTree<K, M>::const_iterator BSTree<K, M>::cbegin() const

 const_iterator iter;
 iter.ptrToBuffer = &nodes;
 iter.index_ = iter.lowest(root_node);
 iter.reverse_ = false;
 iter.ptrToComp = &comp;
 return iter;


template<class K, class M>
inline void BSTree<K, M>::clear()

 nodes.resize(min_size);
 weights.resize(min_size);
 node_count = 0;
 weights.at(root_node) = 0;
 nodes.at(root_node).lnode = false;
 nodes.at(root_node).rnode = false;


template<class K, class M>
inline std::size_t BSTree<K, M>::count(const key_type& key) const

 if (locate(key) != out_of_range) return 1;
 return 0;


template<class K, class M>
inline typename BSTree<K, M>::const_iterator BSTree<K, M>::cend() const noexcept

 const_iterator iter;
 iter.ptrToBuffer = &nodes;
 iter.index_ = out_of_range;
 iter.reverse_ = false;
 iter.ptrToComp = &comp;
 return iter;


template<class K, class M>
inline typename BSTree<K, M>::const_iterator BSTree<K, M>::crbegin() const

 const_iterator iter;
 iter.ptrToBuffer = &nodes;
 iter.index_ = iter.highest(root_node);
 iter.reverse_ = true;
 iter.ptrToComp = &comp;
 return iter;


template<class K, class M>
inline typename BSTree<K, M>::const_iterator BSTree<K, M>::crend() const noexcept

 const_iterator iter;
 iter.ptrToBuffer = &nodes;
 iter.index_ = out_of_range;
 iter.reverse_ = true;
 iter.ptrToComp = &comp;
 return iter;


template<class K, class M>
inline typename BSTree<K, M>::iterator BSTree<K, M>::end() noexcept

 iterator iter;
 iter.ptrToBuffer = &nodes;
 iter.index_ = out_of_range;
 iter.reverse_ = false;
 iter.ptrToComp = &comp;
 return iter;


template<class K, class M>
inline typename BSTree<K, M>::const_iterator BSTree<K, M>::end() const noexcept

 return cend();


template<class K, class M>
inline std::pair<typename BSTree<K, M>::iterator,
 typename BSTree<K, M>::iterator>
 BSTree<K, M>::equal_range(const key_type & key)

 iterator lower = bound(key, false);
 iterator upper = bound(key, true);
 return std::make_pair(lower, upper);


template<class K, class M>
inline std::pair<typename BSTree<K, M>::const_iterator,
 typename BSTree<K, M>::const_iterator>
 BSTree<K, M>::equal_range(const key_type & key) const

 std::pair<const_iterator, const_iterator> range;
 const_iterator& lower = range.first;
 const_iterator& upper = range.second;

 lower = upper = lower_bound();
 upper.nextIndex();
 return range;


template<class K, class M>
inline uint8_t BSTree<K, M>::msbDeBruijn32(uint32_t v) noexcept

 /*
 The use of a deBruijn sequence in order to find the most significant bit 
 (MSB) in a 32-bit value. This cool idea is from a 1998 paper out of MIT 
 (http://supertech.csail.mit.edu/papers/debruijn.pdf).
 */
 static const std::array<uint8_t, 32> BitPosition
 
 0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
 8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
 ;

 v 

template<class K, class M>
inline void BSTree<K, M>::moveDown(std::size_t root, ChildType type)

 std::stack<std::size_t> inv_tree;
 std::queue<std::size_t> sub_tree;
 sub_tree.push(root);
 while (!sub_tree.empty()) 
 const std::size_t current = sub_tree.front();
 sub_tree.pop();
 inv_tree.push(current);
 if (nodes.at(current).lnode) sub_tree.push(leftChild(current));
 if (nodes.at(current).rnode) sub_tree.push(rightChild(current));
 
 const std::size_t diff = (type == ChildType::Left) ? root : root + 1;
 const int root_msb = msbDeBruijn32(root);
 while (!inv_tree.empty()) 
 const std::size_t current = inv_tree.top();
 inv_tree.pop();
 const int n = msbDeBruijn32(current);
 const std::size_t forward = current + diff * (1 << (n - root_msb));
 nodes.at(forward) = nodes.at(current);
 weights.at(forward) = weights.at(current);
 nodes.at(current).lnode = false;
 nodes.at(current).rnode = false;
 weights.at(current) = 0;
 
 if (type == ChildType::Left) nodes.at(root).lnode = true;
 else nodes.at(root).rnode = true;


template<class K, class M>
inline void BSTree<K, M>::shift(std::size_t root, int diff)

 if (root <= 1) return;
 std::queue<size_t> sub_tree;
 const int root_msb = msbDeBruijn32(root);
 sub_tree.push(root);
 while (true) 
 int levelCount = sub_tree.size();
 if (levelCount == 0) return;
 while (levelCount > 0) 
 const std::size_t current = sub_tree.front();
 sub_tree.pop();
 if (nodes.at(current).lnode) sub_tree.push(current << 1);
 if (nodes.at(current).rnode) sub_tree.push((current << 1) + 1);
 const int n = msbDeBruijn32(current);
 const std::size_t forward = current + diff * (1 << (n - root_msb));
 nodes.at(forward) = nodes.at(current);
 weights.at(forward) = weights.at(current);
 nodes.at(current).lnode = false;
 nodes.at(current).rnode = false;
 weights.at(current) = 0;
 --levelCount;
 
 



template<class K, class M>
inline void BSTree<K, M>::moveUp(std::size_t root)

 const int diff = (root >> 1) - root;
 shift(root, diff);


template<class K, class M>
inline void BSTree<K, M>::shiftLeft(std::size_t root)

 const int diff = -1;
 shift(root, diff);


template<class K, class M>
inline void BSTree<K, M>::shiftRight(std::size_t root)

 const int diff = 1;
 shift(root, diff);


template<class K, class M>
inline void BSTree<K, M>::rotateRight(std::size_t index)

 const std::size_t parent = myParent(index);
 nodes.at(parent).lnode = false;
 moveDown(parent, ChildType::Right);
 const std::size_t rchild = rightChild(index);
 const std::size_t sibling = index + 1;
 if (nodes.at(index).rnode) 
 shiftRight(rchild);
 nodes.at(index).rnode = false;
 nodes.at(sibling).lnode = true;
 
 else 
 nodes.at(sibling).lnode = false;
 
 moveUp(index);
 nodes.at(parent).rnode = true;
 reweight(parent);
 reweight(index);
 reweight(sibling);


template<class K, class M>
inline void BSTree<K, M>::rotateLeft(std::size_t index)

 const std::size_t parent = myParent(index);
 nodes.at(parent).rnode = false;
 moveDown(parent, ChildType::Left);
 const std::size_t lchild = leftChild(index);
 const std::size_t sibling = index - 1;
 if (nodes.at(index).lnode) 
 shiftLeft(lchild);
 nodes.at(index).lnode = false;
 nodes.at(sibling).rnode = true;
 
 else 
 nodes.at(sibling).rnode = false;
 
 moveUp(index);
 nodes.at(parent).lnode = true;
 reweight(parent);
 reweight(index);
 reweight(sibling);


template<class K, class M>
inline void BSTree<K, M>::rotateLR(std::size_t index)

 const std::size_t parent = myParent(index);
 const std::size_t rchild = rightChild(index);
 std::size_t rlgrand(out_of_range), rrgrand(out_of_range);
 if (nodes.at(rchild).lnode) rlgrand = leftChild(rchild);
 if (nodes.at(rchild).rnode) rrgrand = rightChild(rchild);

 nodes.at(parent).lnode = false;
 moveDown(parent, ChildType::Right);
 nodes.at(parent) = nodes.at(rchild);
 nodes.at(rchild).lnode = false;
 nodes.at(rchild).rnode = false;
 nodes.at(index).rnode = false;
 const std::size_t sibling = index + 1;
 if (rrgrand != out_of_range) 
 const int diff = ((rrgrand + 1) >> 1) - rrgrand;
 shift(rrgrand, diff);
 nodes.at(sibling).lnode = true;
 
 if (rlgrand != out_of_range) 
 moveUp(rlgrand);
 nodes.at(index).rnode = true;
 
 nodes.at(parent).rnode = true;
 nodes.at(parent).lnode = true;
 reweight(rchild);
 reweight(parent);
 reweight(index);
 reweight(sibling);


template<class K, class M>
inline void BSTree<K, M>::rotateRL(std::size_t index)

 const std::size_t parent = myParent(index);
 const std::size_t lchild = leftChild(index);
 std::size_t llgrand(out_of_range), lrgrand(out_of_range);
 if (nodes.at(lchild).lnode) llgrand = leftChild(lchild);
 if (nodes.at(lchild).rnode) lrgrand = rightChild(lchild);

 nodes.at(parent).rnode = false;
 moveDown(parent, ChildType::Left);
 nodes.at(parent) = nodes.at(lchild);
 nodes.at(lchild).lnode = false;
 nodes.at(lchild).rnode = false;
 nodes.at(index).lnode = false;
 const std::size_t sibling = index - 1;
 if (llgrand != out_of_range) 
 const int diff = ((llgrand - 1) >> 1) - llgrand;
 shift(llgrand, diff);
 nodes.at(sibling).rnode = true;
 
 if (lrgrand != out_of_range) 
 moveUp(lrgrand);
 nodes.at(index).lnode = true;
 
 nodes.at(parent).lnode = true;
 nodes.at(parent).rnode = true;
 reweight(lchild);
 reweight(parent);
 reweight(index);
 reweight(sibling);


template<class K, class M>
inline void BSTree<K, M>::reweight(std::size_t index)

 int left(0), right(0);
 if (nodes.at(index).lnode) left = 
 gsl::narrow_cast<int>(height(leftChild(index)));
 if (nodes.at(index).rnode) right = 
 gsl::narrow_cast<int>(height(rightChild(index)));
 weights.at(index) = gsl::narrow_cast<int8_t>(right - left);


template<class K, class M>
inline bool BSTree<K, M>::rebalanceRoot()

 reweight(root_node);
 if (weights.at(root_node) >= -1 && weights.at(root_node) <= 1) return false;
 if (weights.at(root_node) > 0) rotateLeft(rightChild(root_node));
 else rotateRight(leftChild(root_node));
 reweight(root_node);
 return true;


template<class K, class M>
inline bool BSTree<K, M>::rebalance(std::size_t index, bool increase)

 if (index == 1) 
 return rebalanceRoot();
 
 const bool changed = true;
 while (index > 1) 
 const std::size_t parent = myParent(index);
 const int8_t old_weight = weights.at(parent);
 reweight(parent);
 if (weights.at(parent) == old_weight) return !changed;
 if ((whatType(index) == ChildType::Left && increase) 
 return changed;


template<class K, class M>
void BSTree<K, M>::simpleRemove(std::size_t index, ChildType type)

 const std::size_t parent = myParent(index);
/*
 nodes.at(index).lnode = false;
 nodes.at(index).rnode = false;
*/
 weights.at(index) = 0;
 if (type == ChildType::Right) 
 nodes.at(parent).rnode = false;
 if (weights.at(parent) - 1 < -1) 
 const std::size_t sibling = index - 1;
 rebalance(sibling, true);
 return;
 
 if (--weights.at(parent) == 0) rebalance(parent, false);
 
 else 
 nodes.at(parent).lnode = false;
 if (weights.at(parent) + 1 > 1) 
 const std::size_t sibling = index + 1;
 rebalance(sibling, true);
 return;
 
 if (++weights.at(parent) == 0) rebalance(parent, false);
 


template<class K, class M>
std::size_t BSTree<K, M>::bottomNode(std::size_t current, ChildType type)

 while (true) 
 if (type == ChildType::Right) 
 if (nodes.at(current).lnode) 
 current = leftChild(current);
 continue;
 
 break;
 
 if (nodes.at(current).rnode) 
 current = rightChild(current);
 continue;
 
 break;
 
 return current;


template<class K, class M>
void BSTree<K, M>::complexRemove(std::size_t child, ChildType type)

 const std::size_t index = myParent(child);
 if (type == ChildType::Left) // move left child
 if (!nodes.at(child).rnode) 
 moveUp(child);
 nodes.at(index).rnode = true;
 if (++weights.at(index) == 0) rebalance(index, false);
 return;
 
 wipeout(child, type);
 return;
 
 if (!nodes.at(child).lnode) // move right child
 moveUp(child);
 nodes.at(index).lnode = true;
 if (--weights.at(index) == 0) rebalance(index, false);
 return;
 
 wipeout(child, type);
 return;


template<class K, class M>
inline void BSTree<K, M>::wipeout(std::size_t child, ChildType type)

 const std::size_t current = (type == ChildType::Left) ?
 bottomNode(rightChild(child), type) :
 bottomNode(leftChild(child), type);
 nodes.at(myParent(child)).value_ = nodes.at(current).value_;
 if (type==ChildType::Left) 
 if (nodes.at(current).lnode) moveUp(leftChild(current)); 
 else nodes.at(myParent(current)).rnode = false;
 
 else 
 if (nodes.at(current).rnode) moveUp(rightChild(current));
 else nodes.at(myParent(current)).lnode = false;
 
 rebalance(current, false);


template<class K, class M>
std::size_t BSTree<K, M>::locate(key_type key, std::size_t start)

 std::size_t current = start;
 while (true) 
 if (nodes.at(current).key() == key) return current;
 if (comp(key, nodes.at(current).key())) 
 if (!nodes.at(current).lnode) return out_of_range;
 current = current << 1;
 continue;
 
 if (!nodes.at(current).rnode) return out_of_range;
 current = (current << 1) + 1;
 
 return out_of_range;


template<class K, class M>
typename BSTree<K, M>::iterator BSTree<K, M>::erase(const_iterator position)

 constexpr std::size_t count_zero = 0;
 iterator iter;

 if (position == cend()) return end();
 key_type next_key;
 std::size_t next_index(0);
 if (++position != cend()) 
 next_key = position->first;
 next_index = position.index_;
 
 --position;
 if (erase(position->first, position.index_) == count_zero) return end();
 if (next_index == out_of_range) return end();
 iter = find(next_key);
 return iter;


template<class K, class M>
typename BSTree<K, M>::iterator
BSTree<K, M>::erase(const_iterator first, const_iterator last)

 iterator iter;

 for (auto it = first; it != last; ++it) iter = erase(it);
 return iter;


template<class K, class M>
std::size_t BSTree<K, M>::erase(const key_type& key)

 return erase(key, 1);


template<class K, class M>
std::size_t BSTree<K, M>::erase(const key_type& key, std::size_t start)

 constexpr std::size_t count_zero = 0;
 constexpr std::size_t count_one = 1;
 const auto index = locate(key, start);
 if (index == out_of_range) return count_zero;
 const bool left = nodes.at(index).lnode;
 const bool right = nodes.at(index).rnode;
 --node_count;
 if (!left && !right) 
 simpleRemove(index, whatType(index));
 return count_one;
 
 const std::size_t lchild = leftChild(index);
 const std::size_t rchild = rightChild(index);
 if (left && !right) 
 moveUp(lchild);
 rebalance(index, false);
 return count_one;
 
 if (!left && right) 
 moveUp(rchild);
 rebalance(index, false);
 return count_one;
 
 if (left&&right) 
 if (height(rchild) <= height(lchild))
 complexRemove(lchild, ChildType::Left);
 else complexRemove(rchild, ChildType::Right);
 return count_one;
 
 throw std::exception();
 return count_zero;


template<class K, class M>
inline typename BSTree<K, M>::iterator BSTree<K, M>::find(const key_type key)

 iterator iter;
 iter.ptrToBuffer = &nodes;
 iter.reverse_ = false;
 iter.ptrToComp = &comp;
 iter.index_ = locate(key);
 return iter;


template<class K, class M>
inline typename BSTree<K, M>::const_iterator
BSTree<K, M>::find(const key_type key) const

 const_iterator iter;
 iter.ptrToBuffer = &nodes;
 iter.reverse_ = false;
 iter.ptrToComp = &comp;
 iter.index_ = locate(key);
 return iter;


template<class K, class M>
std::size_t BSTree<K, M>::height(std::size_t index)

 int height = 0;
 if (index == out_of_range) return height;
 std::queue<size_t> sub_tree;
 sub_tree.push(index);

 while (true) 
 int nodeCount = sub_tree.size();
 if (nodeCount == 0) return height;
 height++;
 while (nodeCount > 0) 
 const std::size_t current = sub_tree.front();
 sub_tree.pop();
 if (nodes.at(current).lnode) sub_tree.push(leftChild(current));
 if (nodes.at(current).rnode) sub_tree.push(rightChild(current));
 --nodeCount;
 
 


template<class K, class M>
inline std::size_t BSTree<K, M>::height()

 if (node_count == 0) return 0;
 return height(root_node);


template<class K, class M>
inline void BSTree<K, M>::inject(std::size_t index, iterator & iter,
 key_type key, mapped_type mapped, ChildType type)

 ++node_count;
 std::size_t child 0 ;
 bool tilted = false;
 if (type == ChildType::Left) 
 child = leftChild(index);
 nodes.at(index).lnode = true;
 if (--weights.at(index) != 0) tilted = true;
 
 else 
 child = rightChild(index);
 nodes.at(index).rnode = true;
 if (++weights.at(index) != 0) tilted = true;
 
 nodes.at(child).key() = key;
 nodes.at(child).mapped() = mapped;
 weights.at(child) = 0;
 iter.index_ = child;
 if (tilted) 
 if (rebalance(index, true)) iter.index_ = locate(key);
 


template<class K, class M>
std::pair<typename BSTree<K, M>::iterator, bool>
BSTree<K, M>::insert(std::size_t root, const key_type& key,
 const mapped_type& mapped)


 iterator iter;
 iter.reverse_ = false;
 iter.ptrToComp = &comp;
 iter.ptrToBuffer = &nodes;

 if (node_count == 0) 
 ++node_count;
 nodes.resize(min_size);
 weights.resize(min_size);

 nodes.at(root_node).key() = key;
 nodes.at(root_node).mapped() = mapped;
 weights.at(root_node) = 0;
 iter.index_ = 1;
 return std::pair(iter, true);
 
 std::size_t index = root;
 while (true) 
 if (key == nodes.at(index).key()) 
 nodes.at(index).mapped() = mapped;
 iter.index_ = index;
 return std::pair(iter, false);
 break;
 
 if (2 * index >= nodes.size()) 
 const int n = msbDeBruijn32(index);
 nodes.resize(1 << (n + 2));
 weights.resize(nodes.size());
 
 if (comp(key, nodes.at(index).key())) 
 if (!nodes.at(index).lnode) 
 inject(index, iter, key, mapped, ChildType::Left);
 return std::pair(iter, true);
 
 index = leftChild(index);
 continue;
 
 if (!nodes.at(index).rnode) 
 inject(index, iter, key, mapped, ChildType::Right);
 return std::pair(iter, true);
 
 index = rightChild(index);
 


template<class K, class M>
std::pair<typename BSTree<K, M>::iterator, bool>
BSTree<K, M>::insert(const key_type& key, const mapped_type& mapped)

 return insert(1, key, mapped);


template<class K, class M>
inline std::pair<typename BSTree<K, M>::iterator, bool>
BSTree<K, M>::insert(const value_type& value)

 return insert(value.first, value.second);


template<class K, class M>
inline typename BSTree<K, M>::iterator
BSTree<K, M>::insert(iterator hint, const value_type & value)

 const std::size_t index = hint.index_;
 if (index == out_of_range) 
 if (!comp(value.first, (--hint)->first))
 return insert(hint.index_, value.first, value.second).first;
 return insert(root_node, value.first, value.second).first;
 
 if (comp(value.first, hint->first)) !comp(value.first, hint->first))
 return insert(index, value.first, value.second).first;
 return insert(root_node, value.first, value.second).first;
 
 ++hint;
 if (hint.index_ == out_of_range 

template<class K, class M>
template<class InputIterator>
inline void BSTree<K, M>::insert(InputIterator first, InputIterator last)

 for (auto it = first; it != last; ++it) 
 const auto reply = insert(root_node, it->first, it->second);


template<class K, class M>
inline void BSTree<K, M>::insert(std::initializer_list<value_type> il)

 for (auto it = il.begin(); it != il.end(); ++it) 
 const auto reply = insert(root_node, it->first, it->second);


template<class K, class M>
bool BSTree<K, M>::isBalanced(std::size_t index)

 std::size_t old_level = gsl::narrow_cast<std::size_t>(-1);
 bool ret = true;
 if (index == out_of_range) return true;
 traverseByLevel(index, height(index), [&](std::size_t level,
 std::size_t current) -> void
 );
 return ret;


template<class K, class M>
inline bool BSTree<K, M>::isBalanced()

 return isBalanced(root_node);


template<class K, class M>
bool BSTree<K, M>::isBST(std::size_t index)

 std::size_t old_level = gsl::narrow_cast<std::size_t>(-1);
 bool ret = true;
 if (index == out_of_range) return true;
 traverseByLevel(index, height(index), [&](std::size_t level, 
 std::size_t current) -> void 
 
 if (level != old_level) 
 old_level = level;
 
 if (current == 0) return;
 if (nodes.at(current).lnode) 
 const std::size_t lchild = leftChild(current);
 if (comp(nodes.at(current).key(), nodes.at(lchild).key())) 
 ret = false;
 return;
 
 
 if (nodes.at(current).rnode) 
 const std::size_t rchild = rightChild(current);
 if (comp(nodes.at(rchild).key(), nodes.at(current).key())) 
 ret = false;
 return;
 
 
 );
 return ret;


template<class K, class M>
inline bool BSTree<K, M>::isBST()

 return isBST(root_node);


template<class K, class M>
inline typename BSTree<K, M>::key_compare BSTree<K, M>::key_comp() const

 return comp;


template<class K, class M>
inline typename BSTree<K, M>::iterator
BSTree<K, M>::bound(const key_type & key, bool upper)

 iterator iter;

 std::size_t index = root_node;
 iter.ptrToBuffer = &nodes;
 iter.reverse_ = false;
 iter.ptrToComp = &comp;
 while (true) 
 if (key == nodes.at(index).key()) 
 iter.index_ = index;
 if (upper) return ++iter;
 return iter;
 
 if (comp(key, nodes.at(index).key())) // key < root->key
 if (nodes.at(index).lnode) 
 index = leftChild(index);
 continue;
 
 else 
 iter.index_ = index;
 return iter;
 
 
 if (nodes.at(index).rnode) 
 index = rightChild(index);
 continue;
 
 iter.index_ = index;
 return ++iter;
 


template<class K, class M>
inline typename BSTree<K, M>::iterator
BSTree<K, M>::lower_bound(const key_type & key)

 return bound(key, false);


template<class K, class M>
inline typename BSTree<K, M>::const_iterator
BSTree<K, M>::lower_bound(const key_type & key) const

 const_iterator iter;

 iter = bound(key, false);
 return iter;


template<class K, class M>
inline typename BSTree<K, M>::mapped_type &
BSTree<K, M>::operator[](const key_type & key)

 std::size_t index = locate(key);
 if (index == out_of_range) 
 mapped_type mapped;
 const auto[iter, reply] = insert(root_node, key, mapped);
 index = iter.index_;
 
 return nodes.at(index).mapped();


template<class K, class M>
inline void BSTree<K, M>::reserve(std::size_t size)

 nodes.reserve(size);
 weights.reserve(size);


template<class K, class M>
inline std::size_t BSTree<K, M>::size() const noexcept

 return node_count;


template<class K, class M>
inline void BSTree<K, M>::swap(BSTree & other) noexcept

 std::swap(nodes, other.nodes);
 std::swap(weights, other.weights);
 std::swap(node_count, other.node_count);


template<class K, class M>
inline typename BSTree<K, M>::iterator BSTree<K, M>::rbegin()

 iterator iter;
 iter.ptrToBuffer = &nodes;
 iter.index_ = iter.highest(root_node);
 iter.reverse_ = true;
 iter.ptrToComp = &comp;
 return iter;


template<class K, class M>
inline typename BSTree<K, M>::const_iterator BSTree<K, M>::rbegin() const

 return crbegin();


template<class K, class M>
inline typename BSTree<K, M>::iterator BSTree<K, M>::rend() noexcept

 iterator iter;
 iter.ptrToBuffer = &nodes;
 iter.index_ = out_of_range;
 iter.reverse_ = true;
 iter.ptrToComp = &comp;
 return iter;


template<class K, class M>
inline typename BSTree<K, M>::const_iterator BSTree<K, M>::rend() 
const noexcept

 return crend();


template<class K, class M>
inline typename BSTree<K, M>::iterator
BSTree<K, M>::upper_bound(const key_type & key)

 return bound(key, true);


template<class K, class M>
inline typename BSTree<K, M>::const_iterator
BSTree<K, M>::upper_bound(const key_type & key) const

 const_iterator iter;

 iter = bound(key, true);
 return iter;


template<class K, class M>
void BSTree<K, M>::inorder(std::size_t index,
 std::function<void(key_type&, mapped_type&)> fn)

 if (index == out_of_range) return;
 size_t current = index;
 std::stack<size_t> s;
 while (!s.empty() 

template<class K, class M>
inline void BSTree<K, M>::viewKeys()

 inorder(1, [](key_type& key, mapped_type& mapped) -> void 
 std::cout << key << 'n';
 );


template<class K, class M>
inline void BSTree<K, M>::traverseByLevel(std::size_t root, 
 std::size_t max_level, std::function<void(std::size_t, std::size_t)> fn)

 if (root < 1) return;
 std::queue<size_t> sub_tree;
 sub_tree.push(root);
 std::size_t level = 0;
 while (level < max_level) 
 int levelCount = sub_tree.size();
 if (levelCount == 0) return;
 while (levelCount > 0) 
 const std::size_t current = sub_tree.front();
 sub_tree.pop();
 if (nodes.at(current).lnode) sub_tree.push(leftChild(current));
 else sub_tree.push(0);
 if (nodes.at(current).rnode) sub_tree.push(rightChild(current));
 else sub_tree.push(0);
 fn(level, current);
 --levelCount;
 
 ++level;
 


template<class K, class M>
inline void BSTree<K, M>::Node::printKey(std::size_t size, Justify just)

 std::stringstream ss;
 char buf[255];

 ss << key();
 ss.getline(buf,255);
 std::string sbuf;
 const std::size_t length = s.length();
 switch (just) 
 case Justify::Left:
 std::cout << s;
 printSpaces(size - length);
 break;
 case Justify::Right:
 printSpaces(size - length);
 std::cout << s;
 break;
 case Justify::Center:
 const std::size_t pad = (size - length) >> 1;
 printSpaces(pad);
 std::cout << s;
 printSpaces(size - length - pad);
 break;
 


template<class K, class M>
inline void BSTree<K, M>::viewTree(std::size_t root, std::size_t depth)

 std::string s;
 std::size_t key_size = 0;

 traverseByLevel(root, depth, [&](std::size_t level, std::size_t index)
 -> void 
 std::stringstream ss;
 char buf[255];
 if (index != 0) 
 ss << nodes.at(index).key();
 ss.getline(buf, 255);
 s = buf;
 if (s.length() > key_size) key_size = s.length();
 s.clear();
 
 );
 std::size_t oldLevel = gsl::narrow_cast<std::size_t>(-1);
 traverseByLevel(root, depth, [&]
 (std::size_t level, std::size_t index) -> void 
 const std::size_t space_size = (key_size & 1) ? 1 : 2;
 if (level != oldLevel) 
 const std::size_t lead_space =
 ((1 << (depth - level - 1)) - 1) * 
 ((key_size + space_size) >> 1);
 oldLevel = level;
 std::cout << "n";
 printSpaces(lead_space);
 
 else 
 const std::size_t internal_space =
 ((1 << (depth - level - 1)) - 1)*(key_size + space_size) + space_size;
 printSpaces(internal_space);
 
 if (index != 0) nodes.at(index).printKey(key_size, Justify::Center);
 else printSpaces(key_size);
 );
 std::cout << "n";


#endif // !BSTREE

Test.cpp (It's a mess, but I have yet to learn how to write an organized test suit. Maybe that will be my next project.)

// test.cpp : This file contains the 'main' function. Program execution 
// begins and ends there.

#include "pch.h"
#include "BSTree.hpp"
#include <iostream>
#include <vector>
#include <fstream>
#include <string>
#include <sstream>
#include <cassert>
#include <chrono>
#include <cctype>
#include <map>
#include <tuple>
#include <random>

using std::cout;
using std::endl;
using namespace std::chrono;

bool myfunc(const int& a, const int& b) noexcept 
 return a > b;


template<class K>
bool myfunc2(const K& a, const K& b) noexcept 
 const bool ret = std::less<K>::less()(a, b);
 return ret;


int main()

 BSTree<int> bs_tree(20000);
 auto [it, good] = bs_tree.insert(5,'a');
 assert (good && "inserted 5,an");
 std::tie(it, good) = bs_tree.insert(2,'b');
 assert (good && "inserted 2,bn");
 std::tie(it, good) = bs_tree.insert(21,'c');
 assert(good && "inserted 21,cn");
 bs_tree.viewTree();
 auto count = bs_tree.erase(5);
 assert(count == 1 && "erased 5n");
 count = bs_tree.erase(5);
 assert(count == 0 && "erased 5n");
 bs_tree.viewTree();
 cout << std::boolalpha << bs_tree.isBalanced();
 cout << " " << std::boolalpha << bs_tree.isBST() << std::noboolalpha;
 cout << " " << bs_tree.height() << "n";
 std::tie(it, good) = bs_tree.insert(25, 'd');
 assert(good && "inserted 25,dn");
 std::tie(it, good) = bs_tree.insert(25, 'd');
 assert(!good && "inserted 25,dn");
 bs_tree.viewTree();
 count = bs_tree.erase(25);
 assert(count == 1 && "erased 25n");
 std::tie(it, good) = bs_tree.insert(5, 'd');
 assert(good && "inserted 5,dn");
 bs_tree.viewTree();
 std::tie(it, good) = bs_tree.insert(19,'e');
 assert(good && "inserted 19,en");
 std::tie(it, good) = bs_tree.insert(25,'f');
 assert(good && "inserted 25,fn");
 std::tie(it, good) = bs_tree.insert(55,'g');
 assert(good && "inserted 55,gn");
 std::tie(it, good) = bs_tree.insert(60,'h');
 assert(good && "inserted 60,hn");
 std::tie(it, good) = bs_tree.insert(15,'i');
 assert(good && "inserted 15,in");
 std::tie(it, good) = bs_tree.insert(0,'j');
 assert(good && "inserted 0,jn");
 cout << "Before erase:n";
 bs_tree.viewTree();
 bs_tree.erase(21);
 cout << "After:n";
 bs_tree.viewTree();
 bs_tree.erase(15);
 bs_tree.viewTree();
 auto [it2, result] = bs_tree.insert(63,'l');
 assert(result && "inserted 63,ln");
 auto it3 = bs_tree.insert(it2, std::make_pair(67,'k'));
 it3 = bs_tree.erase(it3);
 it2 = bs_tree.find(63);
 it3 = bs_tree.insert(it2, std::make_pair(67, 'k'));
 it2 = bs_tree.find(63);
 for (; it2 != bs_tree.end(); --it2) cout << it2->first << ": ";
 cout << "n";
 bs_tree.viewTree();
 bs_tree.erase(1);
 bs_tree[1] = '.';
 assert(bs_tree.at(1) == '.' && "operator[1]='.'n");
 bs_tree.viewTree();
 std::vector<std::pair<int, char>> pairs;
 for (int i = 0; i < 70; ++i) 
 auto iter = bs_tree.find(i);
 if (iter != bs_tree.end()) 
 cout << "found: " << iter->first << "-> " << iter->second << "n";
 pairs.push_back(std::make_pair(iter->first, iter->second));
 
 
 assert(pairs.size() == 10 && "pairs foundn");
 count = bs_tree.erase(5);
 assert(count == 1 && "erased 5n");
 bs_tree.viewTree();
 count = bs_tree.erase(0);
 assert(count == 1 && "erased 0n");
 count = bs_tree.erase(0);
 assert(count == 0 && "!erased 0n");
 bs_tree.viewTree();
 cout << "n";
 bs_tree.viewKeys();
 for (const auto p : bs_tree) cout << p.first << ": ";
 cout << "n";
 for (auto i = bs_tree.crbegin(); i != bs_tree.crend(); ++i) 
 cout << i->first << ": ";
 cout << "n";
 it = bs_tree.begin(); 
 it = bs_tree.erase(it);
 cout << it->first << ": " << (*++it).first << ": ";
 cout << (*++it).first << ": " << (*++it).first << ": " << 
 (*++it).first << "n";
 cout << (*it--).first << ": " << it->first << "n";
 bs_tree.viewTree();
 auto it5 = bs_tree.lower_bound(3);
 assert(it5->first == 19 && "lower bound of 3 is 19");
 auto it6 = bs_tree.upper_bound(60);
 assert(it6->first == 63 && "upper bound of 60 is 63");
 for (auto it = it5; it != it6; ++it) cout << it->first << "

Output verifying that it all works:

 5
 2 21



 2
 21


true true 2

 21
 2 25



 5
 2 21


Before erase:

 21
 5 55
 2 19 25 60
0 15
After:

 19
 5 55
 2 15 25 60
0

 19
 2 55
 0 5 25 60

63: 60: 55: 25: 19: 5: 2: 0:

 19
 2 55
 0 5 25 63
 60 67

 19
 2 55
 0 5 25 63
 1 60 67
found: 0-> j
found: 1-> .
found: 2-> b
found: 5-> d
found: 19-> e
found: 25-> f
found: 55-> g
found: 60-> h
found: 63-> l
found: 67-> k

 19
 1 55
 0 2 25 63
 60 67

 19
 1 55
 2 25 63
 60 67

1
2
19
25
55
60
63
67
1: 2: 19: 25: 55: 60: 63: 67:
67: 63: 60: 55: 25: 19: 2: 1:
2: 19: 25: 55: 60
60: 55

 55
 19 63
 2 25 60 67

19|25|55|60|
now
63-67-
Pointer Out Of Range!

63
25
63

 19
 2 63
 67


true true 3
Hello World!
pairs:

 5
 1 60
 0 2 25 63
 19 55 67


 25
 5 60
 1 19 55 63
0 2 6 67

 25
 5 60
 1 13 55 63
0 2 6 19 56 67

 25
 2 60
 1 13 55 63
 6 19 56 67


 New York
 Kansas South Carolina
 Delaware Mississippi Oklahoma Utah
 Arkansas Idaho Maryland Nevada North Dakota Pennsylvania Tennessee West Virginia

50
Boston
Boston

Out Of Range for key: "Mass"

Mobile is not the capital
'chicken' is less than 'turkey': true
'fox' is less than 'dog': false
count: 631638 size: 631638
BSTree Insert took 2810ms
It's Balanced: true
It's a BST: true
Map Insert took 473343us
map lower: 26 upper: 26
BST lower: 26 upper: 26
bs_tree size = 631638
BSTree find took 256ms
bs_tree size = 1000000
Map find took 16210us
BSTree erase took 1483ms
bs_tree size = 0
Map erase took 534368us
good bye!