C++ Data Structures with Templates

The Code

#ifndef AVLTree_h
#define AVLTree_h
template<typename T, typename K>
class AVLTree {
public:
	using BTIter = bool(*)(K, T*);
	AVLTree();
	~AVLTree();
	bool insert(K, T*);
	bool deleteNode(K);
	size_t count();
	size_t height();
	T* search(K);
	void iterate(BTIter);
private:
	struct btNode {
		K key;
		void* data;
		btNode* left;
		btNode* right;
	};
	btNode* root = NULL;
	size_t tSize, nSize;
	btNode* btInsert(K, btNode**, T*);
	btNode* getLowKeyNode(btNode*);
	btNode* btDeleteNode(K, btNode**);
	void btDelete(btNode*);
	size_t btCount(btNode*);
	int16_t btHeight(btNode*);
	size_t btMax(size_t, size_t);
	bool btRepeat, insertOK, deleteOK;
	T* btSearch(K, btNode*);
	void btIterate(btNode*, BTIter);
	btNode* rightRotate(btNode**);
	btNode* leftRotate(btNode**);
};
//constructor
template<typename T, typename K>
AVLTree<T, K>::AVLTree() {
	tSize = sizeof(T);
	nSize = sizeof(btNode);
}
// destructor
template<typename T, typename K>
AVLTree<T, K>::~AVLTree() {
	btDelete(root);
}
// public methods
template<typename T, typename K>
bool AVLTree<T, K>::insert(K key, T* data) {
	root = btInsert(key, &root, data);
	return insertOK;
}
template<typename T, typename K>
bool AVLTree<T, K>::deleteNode(K key) {
	deleteOK = false;
	root = btDeleteNode(key, &root);
	return deleteOK;
}
template<typename T, typename K>
T* AVLTree<T, K>::search(K key) {
	return btSearch(key, root);
}
template<typename T, typename K>
void AVLTree<T, K>::iterate(BTIter callback) {
	btRepeat = true;
	btIterate(root, callback);
}
// public for testing although may still be useful
template<typename T, typename K>
size_t AVLTree<T, K>::count() {
	return btCount(root);
}
template<typename T, typename K>
size_t AVLTree<T, K>::height() {
	return btHeight(root);
}
// private methods
template<typename T, typename K>
typename AVLTree<T, K>::btNode* AVLTree<T, K>::btInsert(K key, btNode** leaf, T* data) {
	if (*leaf == NULL) {
		insertOK = true;
		*leaf = (btNode*)malloc(nSize);
		if (!*leaf) {
			insertOK = false;
			return NULL;
		}
		(*leaf)->key = key;
		(*leaf)->left = (*leaf)->right = NULL;
		(*leaf)->data = malloc(tSize);
		if ((*leaf)->data) {
			memcpy((*leaf)->data, data, tSize);
			return *leaf;
		}
		else {
			insertOK = false;
		}
		return NULL;
	}
	if (key == (*leaf)->key) {
		// wait for update option
		return (*leaf);
	}
	if (key < (*leaf)->key) {
		(*leaf)->left = btInsert(key, &(*leaf)->left, data);
	}
	else {
		(*leaf)->right = btInsert(key, &(*leaf)->right, data);
	}
	int16_t diff = btHeight((*leaf)->left) - btHeight((*leaf)->right);
	if (diff > 1) {
		//left branch is too hight compared to right branch
		if (key < (*leaf)->left->key) {
			return rightRotate(leaf);
		}
		else if (key >(*leaf)->left->key) {
			(*leaf)->left = leftRotate(&((*leaf)->left));
			return rightRotate(leaf);
		}
	}
	if (diff < -1) {
		//right branch is too high compared to left branch
		if (key >(*leaf)->right->key) {
			return leftRotate(leaf);
		}
		else if (key < (*leaf)->right->key) {
			(*leaf)->right = rightRotate(&((*leaf)->right));
			return leftRotate(leaf);
		}
	}
	return *leaf;
}
template<typename T, typename K>
typename AVLTree<T, K>::btNode* AVLTree<T, K>::btDeleteNode(K key, btNode** leaf) {
	if (*leaf == NULL) {
		return *leaf;
	}
	// locate and delete the node
	if (key < (*leaf)->key) {
		(*leaf)->left = btDeleteNode(key, &(*leaf)->left);
	}
	else if (key >(*leaf)->key) {
		(*leaf)->right = btDeleteNode(key, &(*leaf)->right);
	}
	else {
		// this is the node we are looking to delete
		btNode* temp;
		if ((*leaf)->left == NULL || (*leaf)->right == NULL) {
			// one or both child nodes might be NULL
			temp = (*leaf)->left ? (*leaf)->left : (*leaf)->right;
			if (temp == NULL) {
				// no children
				temp = *leaf;
				*leaf = NULL;
			}
			else {
				// one child so copy child to this node
				**leaf = *temp;
			}
			// free the node (or copied child) memory allocations
			free(temp->data);
			free(temp);
			deleteOK = true;
		}
		else {
			temp = getLowKeyNode((*leaf)->right);
			// copy the lowest node on the right path to this node
			(*leaf)->key = temp->key;
			memcpy((*leaf)->data, temp->data, tSize);
			// and then zap that node instead
			(*leaf)->right = btDeleteNode(temp->key, &(*leaf)->right);
		}
	}
	if ((*leaf) == NULL) {
		return *leaf;
	}
	// OK - now the delete is over we may need to 
	// fix the tree balance
	int16_t diff = btHeight((*leaf)->left) - btHeight((*leaf)->right);
	if (diff > 1) {
		// get the height difference on the left path
		diff = btHeight((*leaf)->left->left) - btHeight((*leaf)->left->right);
		if (diff < 0) {
			(*leaf)->left = leftRotate(&(*leaf)->left);
			return rightRotate(leaf);
		}
		else {
			return rightRotate(leaf);
		}
	}
	if (diff < -1) {
		// calc the geight difference on the right path
		diff = btHeight((*leaf)->right->left) - btHeight((*leaf)->right->right);
		if (diff <= 0) {
			return leftRotate(leaf);
		}
		else {
			(*leaf)->right = rightRotate(&(*leaf)->right);
			return leftRotate(leaf);
		}
	}
	return *leaf;
}
template<typename T, typename K>
typename AVLTree<T, K>::btNode* AVLTree<T, K>::getLowKeyNode(btNode* leaf) {
	btNode* temp = leaf;
	// walk down to the last left hand child (lowest key on branch)
	while (temp->left != NULL) {
		temp = temp->left;
	}
	return temp;
}
template<typename T, typename K>
T* AVLTree<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);
	}
	else {
		return NULL;
	}
}
template<typename T, typename K>
void AVLTree<T, K>::btIterate(btNode*leaf, BTIter callback) {
	if (leaf && btRepeat) {
		btIterate(leaf->left, callback);
		if (btRepeat) {
			btRepeat = callback(leaf->key, (T*)leaf->data);
			btIterate(leaf->right, callback);
		}
	}
}
template<typename T, typename K>
size_t AVLTree<T, K>::btCount(btNode* leaf) {
	if (leaf) {
		return 1 + btCount(leaf->left) + btCount(leaf->right);
	}
	return 0;
}
template<typename T, typename K>
size_t AVLTree<T, K>::btMax(size_t a, size_t b) {
	return (a <= b) ? b : a;
}
template<typename T, typename K>
int16_t AVLTree<T, K>::btHeight(btNode* leaf) {
	if (leaf) {
		return 1 + btMax(btHeight(leaf->left), btHeight(leaf->right));
	}
	return 0;
}
template<typename T, typename K>
typename AVLTree<T, K>::btNode* AVLTree<T, K>::rightRotate(btNode** root) {
	btNode *oldLeft, *oldLeftRight;
	oldLeft = (*root)->left;
	oldLeftRight = oldLeft->right;
	oldLeft->right = *root;
	(*root)->left = oldLeftRight;
	return oldLeft;
}
template<typename T, typename K>
typename AVLTree<T, K>::btNode* AVLTree<T, K>::leftRotate(btNode** root) {
	btNode *oldRight, *oldRightLeft;
	oldRight = (*root)->right;
	oldRightLeft = oldRight->left;
	oldRight->left = *root;
	oldRight->left->right = oldRightLeft;
	return oldRight;
}
template<typename T, typename K>
void AVLTree<T, K>::btDelete(btNode* leaf) {
	if (leaf) {
		btDelete(leaf->left);
		btDelete(leaf->right);
		free(leaf->data);
		free(leaf);
	}
}
#endif

#include "stdafx.h"
#include <stdint.h>
#include <stdlib.h>
#include "AVLTree.h"
#include <iostream>
using namespace std;
struct observed {
	float temp;
	float airPress;
	float humidity;
};
bool btPrint(int, observed*);
int main()
{
	AVLTree<observed, int> avlTree;
	//int keys[] = { 1, 2, 3, 4, 5, 6, 26, 27,28, 25, 24, 23, 21, 20, 51, 95, 49, 33, 66, 21, 22, 49, 48,47, 44, 11, 65, 93 };
	int keys[] = { 2, 7, 4, 9, 5, 1, 8, 21, 2 };
	for (int i = 0, j = sizeof(keys) / sizeof(int); i < j; i++) {
		observed obs = { rand() % 10,rand() % 20, rand() % 30 };
		if (avlTree.insert(keys[i], &obs)) {
			cout << "Inserted: " << '\n';
		}
	}
	avlTree.iterate(btPrint);
	//btPrint(11, avlTree.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");
	cout << (avlTree.deleteNode(7) ? "Node 7 deleted\n" : "node 26 not deleted\n");
	cout << avlTree.height() << '\n';
	avlTree.iterate(btPrint);
	cin.get();
	return 0;
}
bool btPrint(int key, observed* obs) {
	cout << "Key: " << key << " Temp: " << obs->temp << " Press: " << obs->airPress << " Hum: " << obs->humidity << '\n';
	return true;
}

#include "AVLTree.h"
struct observed{
  float temp;
  float airPress;
  float humidity;
};
template<class T> inline Print &operator <<(Print &obj, T arg) { obj.print(arg); return obj; }
void setup() {
  Serial.begin(115200);
  AVLTree<observed, int> avlTree;
  //int keys[] = {5, 3, 8, 2, 7, 6, 4, 9, 1};
  int keys[] = {9,8,7,6,1,2,3,4,5};
  Serial.println(freeRam());
  for(int i = 0; i < 9; i++) {
    observed obs = {random(1,10), random(11, 20), random(30, 40)};
    if(avlTree.insert(keys[i], &obs)) {
      btPrint(keys[i], &obs);
      Serial << "Inserted: " << '\n';
    }
  }
  Serial << "Tree height: " << avlTree.height() << '\n';
  avlTree.iterate(btPrint);
  avlTree.deleteNode(7);
  avlTree.deleteNode(2);
  avlTree.deleteNode(4);
  avlTree.deleteNode(5);
  avlTree.deleteNode(99);
  avlTree.iterate(btPrint);
  Serial << "Tree height: " << avlTree.height() << '\n';
}
bool btPrint(int key, observed* obs) {
  Serial << "Key: " << key << " Temp: " << obs->temp << " Press: " << obs->airPress << " Hum: " << obs->humidity << '\n';
  return true;
}

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