The Code

AVLTree.h
#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


AVLTree.cpp
#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; }


AVLTree.ino
#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