C++ Data Structures with Templates

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