The Code

The C code
struct btNode { uint16_t key; void* data; btNode* left; btNode* right; }; btNode* root = NULL; struct observed { float temp; float airPress; float humidity; }; struct lNode { uint16_t key; void* data; lNode* next; }; lNode *lStart = NULL, *lEnd = NULL; bool btInsert(uint16_t key, btNode** leaf, observed* dta) { if (*leaf == NULL) { *leaf = (btNode*)malloc(sizeof(btNode)); if (!*leaf) { return false; } (*leaf)->key = key; (*leaf)->left = (*leaf)->right = NULL; (*leaf)->data = malloc(sizeof(observed)); memcpy((*leaf)->data, dta, sizeof(observed)); return true; } if (key < (*leaf)->key) { return btInsert(key, &(*leaf)->left, dta); } return btInsert(key, &(*leaf)->right, dta); } observed* btSearch(uint16_t key, btNode* leaf) { if (leaf) { if (leaf->key == key) { return (observed*)leaf->data; } if (key < leaf->key) { return btSearch(key, leaf->left); } else return btSearch(key, leaf->right); } else { return NULL; } } void btDeleteTree(btNode* leaf) { if (leaf) { btDeleteTree(leaf->left); btDeleteTree(leaf->right); free(leaf->data); free(leaf); } } void btPrint(btNode* leaf) { if (leaf) { btPrint(leaf->left); observed* found = (observed*)leaf->data; cout << "key: " << leaf->key << " Temp: " << found->temp << " Press: " << found->airPress << " Hum: " << found->humidity << '\n'; btPrint(leaf->right); } } int btHeight(btNode* leaf) { if (leaf) { return 1 + btMax(btHeight(leaf->left), btHeight(leaf->right)); } return 0; } int btMax(int a, int b) { return (a <= b) ? b : a; } int btCount(btNode* leaf) { if (leaf) { return 1 + btCount(leaf->left) + btCount(leaf->right); } return 0; } bool appendToList(uint16_t key, void* data) { lNode* nNode = (lNode*)malloc(sizeof(lNode)); if (!nNode) { return false; } nNode->key = key; nNode->data = data; nNode->next = NULL; if (!lEnd) { lStart = lEnd = nNode; } else { lEnd = lEnd->next = nNode; } return true; } lNode* readListItem(int item) { lNode* rNode = lStart; for (int i = 0; i < item; i++) { rNode = rNode->next; } return rNode; } void deleteList() { lNode* dNode = lStart; while (dNode) { lStart = dNode->next; free(dNode); dNode = lStart; } lStart = lEnd = NULL; } void btExtractKey(btNode* leaf) { if (leaf) { btExtractKey(leaf->left); appendToList(leaf->key, leaf->data); btExtractKey(leaf->right); free(leaf); // delete the tree leaf } } void resetTree(btNode** leaf, int iFrom, int iTo) { if (iFrom > iTo) { return; } int iMid = (iFrom + iTo) / 2; lNode* rNode = readListItem(iMid); btReset(leaf, rNode); resetTree(leaf, iFrom, iMid - 1); resetTree(leaf, iMid + 1, iTo); } bool btReset(btNode** leaf, lNode* rNode) { if (*leaf == NULL) { *leaf = (btNode*)malloc(sizeof(btNode)); (*leaf)->key = rNode->key; (*leaf)->left = (*leaf)->right = NULL; (*leaf)->data = rNode->data; return true; } else if (rNode->key < (*leaf)->key) { return btReset(&(*leaf)->left, rNode); } return btReset(&(*leaf)->right, rNode); } void reBuildTree() { int nCount = btCount(root); btExtractKey(root); root = NULL; //restart the tree resetTree(&root, 0, nCount - 1); deleteList(); //recover the linked list memory; }


main() demo code
#include "stdafx.h" #include <stdint.h> #include <stdlib.h> #include <iostream> using namespace std; void btPrint(btNode*); bool btInsert(uint16_t, btNode**, observed*); observed* btSearch(uint16_t, btNode*); void btDeleteTree(btNode*); int btMax(int, int); int btHeight(btNode*); int btCount(btNode*); bool appendToList(uint16_t, void*); lNode* readListItem(int); void deleteList(); void btExtractKey(btNode*); void resetTree(btNode**, int, int); bool btReset(btNode**, lNode*); void reBuildTree(); int main() { int keys[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; for (int i = 0; i < 9; i++) { observed obs = { rand() % 10,rand() % 20, rand() % 30 }; btInsert(keys[i], &root, &obs); } btPrint(root); observed * found = btSearch(6, root); if (found) { cout << "Key 6 lookup = Temp: " << found->temp << " Press: " << found->airPress << " Hum: " << found->humidity << '\n'; } else { cout << "Nope\n"; } cout << "B-Tree height: " << btHeight(root) << '\n'; cout << "Optimal height <= " << (int)log2(btCount(root)) + 1 << '\n'; reBuildTree(); cout << "B-Tree height now: " << btHeight(root) << '\n'; btDeleteTree(root); cin.get();     return 0; }


setup() (Arduino) demo code
template<class T> inline Print &operator <<(Print &obj, T arg) { obj.print(arg); return obj; } void setup() { Serial.begin(115200); int keys[] = {5, 3, 8, 2, 7, 6, 4, 9, 1}; //int keys[] = {1,2,3,4,5,6,7,8,9}; // an unbalanced insertion for(int i = 0; i < 9; i++) {     observed obs = {random(1,10), random(11, 20), random(30, 40)};     if(btInsert(keys[i], &root, &obs)) {      Serial << "Inserted: " << '\n';     } } observed * found = btSearch(6, root); if(found) {     Serial << "Key 6 = Temp: " << found->temp << " Press: " << found->airPress << " Hum: " << found->humidity << '\n'; } else {     Serial << "Nope\n"; } btPrint(root); // display the tree values Serial << "B-Tree height: " << btHeight(root) << '\n'; Serial << "Node Count: " << btCount(root) << '\n'; Serial << "Optimal height <= " << (int)(log(btCount(root)) / log(2) + 0.5) << '\n'; reBuildTree(); btPrint(root); Serial << "B-Tree height: " << btHeight(root) << '\n'; btDeleteTree(root); }


A Template C++ Class
BTree.h
#ifndef BTree_h #define BTree_h // T is the data type and K is the key type // K must support == and < operators template<typename T, typename K> class BTree { public: using BTIter = void(*)(K, T*); BTree(); ~BTree(); bool insert(K, T*, bool=false); size_t count(); size_t height(); T* search(K); T* searchGE(K); void iterate(BTIter); bool isBalanced(); void balanceTree(); private: struct btNode { K key; void* data; btNode* left; btNode* right; }; btNode* root = NULL; size_t tSize, nSize; bool btInsert(K, btNode**, T*, bool); void btDelete(btNode*); size_t btCount(btNode*); size_t btHeight(btNode*); size_t btMax(size_t, size_t); T* btSearch(K, btNode*); T* btSearchGE(K, btNode*); void btIterate(btNode*, BTIter); void rightRotate(btNode**); void leftRotate(btNode**); void vineToTree(btNode**); void treeToVine(btNode**); void compress(btNode**, int); void rotateOrCompress(btNode**, int); void dswTreeBalance(btNode**); }; //constructor template<typename T, typename K> BTree<T, K>::BTree() { tSize = sizeof(T); nSize = sizeof(btNode); } // destructor template<typename T, typename K> BTree<T, K>::~BTree() { btDelete(root); } template<typename T, typename K> bool BTree<T, K>::insert(K key, T* data, bool updateValue=false) { return btInsert(key, &root, data, updateValue); } template<typename T, typename K> size_t BTree<T, K>::count() { return btCount(root); } template<typename T, typename K> size_t BTree<T, K>::height() { return btHeight(root); } template<typename T, typename K> T* BTree<T, K>::search(K key) { return btSearch(key, root); } template<typename T, typename K> T* BTree<T, K>::searchGE(K key) { return btSearchGE(key, root); } template<typename T, typename K> void BTree<T, K>::iterate(BTIter callback) { btIterate(root, callback); } template<typename T, typename K> bool BTree<T, K>::isBalanced() { return btHeight(root) <= (int)log2(btCount(root)) + 1; } template<typename T, typename K> void BTree<T, K>::balanceTree() { dswTreeBalance(&root); } //private methods template<typename T, typename K> bool BTree<T, K>::btInsert(K key, btNode** leaf, T* data, bool uV) { if (*leaf == NULL) { *leaf = (btNode*)malloc(nSize); if (!*leaf) { return false; } (*leaf)->key = key; (*leaf)->left = (*leaf)->right = NULL; (*leaf)->data = malloc(tSize); if ((*leaf)->data) { memcpy((*leaf)->data, data, tSize); return true; } else { return false; } } if (key == (*leaf)->key) { if (uV) { // can update the data for this key so memcpy((*leaf)->data, data, tSize); return true; } else { return false; // duplicate key update not allowed } } if (key < (*leaf)->key) { return btInsert(key, &(*leaf)->left, data, uV); } return btInsert(key, &(*leaf)->right, data, uV); } template<typename T, typename K> void BTree<T, K>::btDelete(btNode* leaf) { if (leaf) { btDelete(leaf->left); btDelete(leaf->right); free(leaf->data); free(leaf); } } template<typename T, typename K> size_t BTree<T, K>::btCount(btNode* leaf) { if (leaf) { return 1 + btCount(leaf->left) + btCount(leaf->right); } return 0; } template<typename T, typename K> size_t BTree<T, K>::btMax(size_t a, size_t b) { return (a <= b) ? b : a; } template<typename T, typename K> size_t BTree<T, K>::btHeight(btNode* leaf) { if (leaf) { return 1 + btMax(btHeight(leaf->left), btHeight(leaf->right)); } return 0; } template<typename T, typename K> T* BTree<T, K>::btSearch(K key, btNode* leaf) { if (leaf) { if (leaf->key == key) { return (T*)leaf->data; } if (key < leaf->key) { return btSearch(key, leaf->left); } else { return btSearch(key, leaf->right); } } return NULL; } template<typename T, typename K> T* BTree<T, K>::btSearchGE(K key, btNode* leaf) { if (leaf) { if (leaf->key == key) { return (T*)leaf->data; } if (key < leaf->key) { return btSearchGE(key, leaf->left); } if (leaf->right) { if (leaf->right->key >= key) { return (T*)leaf->right->data; } return btSearchGE(key, leaf->right); } } return NULL; } template<typename T, typename K> void BTree<T, K>::btIterate(btNode*leaf, BTIter callback) { if (leaf) { btIterate(leaf->left, callback); callback(leaf->key, (T*)leaf->data); btIterate(leaf->right, callback); } } template<typename T, typename K> void BTree<T, K>::dswTreeBalance(btNode** rootP) { btNode *root = *rootP; treeToVine(&root); vineToTree(&root); *rootP = root; } template<typename T, typename K> void BTree<T, K>::rightRotate(btNode** root) { btNode *oldLeft, *oldLeftRight; oldLeft = (*root)->left; oldLeftRight = (*root)->left->right; oldLeft->right = *root; oldLeft->right->left = oldLeftRight; *root = oldLeft; } template<typename T, typename K> void BTree<T, K>::leftRotate(btNode** root) { btNode *oldRight, *oldRightLeft; oldRight = (*root)->right; oldRightLeft = (*root)->right->left; oldRight->left = *root; oldRight->left->right = oldRightLeft; *root = oldRight; } template<typename T, typename K> void BTree<T, K>::treeToVine(btNode** tree) { btNode* root = *tree; if (!root) { return; } while (root->left) { rightRotate(&root); } if (root->right) { treeToVine(&(root->right)); } *tree = root; } template<typename T, typename K> void BTree<T, K>::vineToTree(btNode **vine) { btNode *root = *vine; int n = btCount(root); // M is one less than largest power of 2 <= (n+1) int M = pow(2, floor((log(n + 1) / log(2)))) - 1; // or int M = pow(2, floor(log2(n + 1))) - 1; compress(&root, n - M); while (M > 1) { M = floor(M / 2); compress(&root, M); } *vine = root; } template<typename T, typename K> void BTree<T, K>::compress(btNode **root, int times) { for (int i = 0; i < times; i++) { rotateOrCompress(&(*root), i); } } template<typename T, typename K> void BTree<T, K>::rotateOrCompress(btNode **root, int times) { if (times == 0) { leftRotate(&(*root)); } else { rotateOrCompress(&((*root)->right), times - 1); } } #endif


BTree.cpp
#include "stdafx.h" #include <stdint.h> #include <stdlib.h> #include "BTree.h" #include <iostream> using namespace std; struct observed { float temp; float airPress; float humidity; }; void btPrint(int, observed*); int main() { BTree<observed, int> bTree; int keys[] = {5, 3, 8, 2, 7, 6, 4, 9, 1, 12, 15, 21, 11, 26}; for (int i = 0; i < 14; i++) { observed obs = { rand() % 10,rand() % 20, rand() % 30 }; if (bTree.insert(keys[i], &obs)) { cout << "Inserted: " << '\n'; } } bTree.iterate(btPrint); btPrint(11, bTree.searchGE(11)); btPrint(5, bTree.searchGE(5)); cout << (bTree.isBalanced() ? "Tree is balanced\n" : "Tree not balanced\n"); bTree.balanceTree(); cout << (bTree.isBalanced() ? "Tree is balanced\n" : "Tree not balanced\n"); cin.get();     return 0; } void btPrint(int key, observed* obs) { cout << "Key: " << key << " Temp: " << obs->temp << " Press: " << obs->airPress << " Hum: " << obs->humidity << '\n'; }


BTree.ino
#include "BTree.h" template<class T> inline Print &operator <<(Print &obj, T arg) { obj.print(arg); return obj; } int tst = 0; void setup() { Serial.begin(115200); BTree<observed, int> bTree; //int keys[] = {5, 3, 8, 2, 7, 6, 4, 9, 1}; int keys[] = {1,2,3,4,5,6,7,8,9}; for(int i = 0; i < 9; i++) {     observed obs = {random(1,10), random(11, 20), random(30, 40)};     if(bTree.insert(keys[i], &obs)) {      Serial << "Inserted: " << '\n';     } } bTree.iterate(btPrint); Serial << "Tree height: " << bTree.height() << '\n'; Serial << (bTree.isBalanced() ? "Tree is balanced\n" : "Tree not balanced\n"); observed* fo = bTree.search(5); btPrint(5, fo); bTree.balanceTree(); Serial << "Tree height: " << bTree.height() << '\n'; tst = 0; bTree.iterate(btPrint); } bool btPrint(int key, observed* obs) { Serial << "Key: " << key << " Temp: " << obs->temp << " Press: " << obs->airPress << " Hum: " << obs->humidity << '\n'; }


Read the chapter in my book C++ Data Structures with immediate download from Amazon