1 files changed, 90 insertions, 0 deletions
diff --git a/src/lib/algo/avl_tree.c b/src/lib/algo/avl_tree.c
new file mode 100644
index 0000000..98cd18b
--- /dev/null
+++ b/src/lib/algo/avl_tree.c
@@ -0,0 +1,90 @@
+#include <lib/algo/avl_tree.h>
+#include <lib/monad.h>
+
+#include <stddef.h>
+#include <stdio.h>
+
+// Get the height of an AVL node
+uint8_t get_height(struct AVLNode* node)
+{
+  if (node == NULL) {
+    return 0;
+  }
+  return node->height;
+}
+
+// Get the Maximum Height between two
+uint8_t max_height(uint8_t a, uint8_t b)
+{
+  return (a > b) ? a : b;
+}
+
+// Get the balance factor of a node
+ssize_t get_balance_factor(struct AVLNode* node)
+{
+  if (node == NULL) {
+    return 0;
+  }
+  return get_height(node->left) - get_height(node->right);
+}
+
+// Rotate an AVL node right
+struct AVLNode* right_rotate(struct AVLNode* parent)
+{
+  struct AVLNode* child1 = parent->left;
+  struct AVLNode* child2 = child1->right;
+
+  child1->right = parent;
+  parent->left = child2;
+
+  parent->height = max_height(get_height(parent->left), get_height(parent->right)) + 1;
+  child1->height = max_height(get_height(child1->left), get_height(child1->right)) + 1;
+  return child1;
+}
+
+// Rotate an AVL node left
+struct AVLNode* left_rotate(struct AVLNode* parent)
+{
+  struct AVLNode* child1 = parent->right;
+  struct AVLNode* child2 = child1->left;
+
+  child1->left = parent;
+  parent->right = child2;
+
+  parent->height = max_height(get_height(parent->left), get_height(parent->right)) + 1;
+  child1->height = max_height(get_height(child1->left), get_height(child1->right)) + 1;
+  return child1;
+}
+
+// In-order traversal print pointer
+void print_in_order(struct AVLNode* root)
+{
+  if (root != NULL) {
+    print_in_order(root->left);
+    printf("%p ", root->data);
+    print_in_order(root->right);
+  }
+}
+
+// Free avl tree nodes starting at root
+void free_avl_tree(struct AVLNode* root)
+{
+  if (root != NULL) {
+    free_avl_tree(root->left);
+    free_avl_tree(root->right);
+    free(root);
+  }
+}
+
+// Free avl tree and their data starting at root
+void free_avl_tree_nodes(struct AVLNode* root)
+{
+  if (root != NULL) {
+    free_avl_tree_nodes(root->left);
+    free_avl_tree_nodes(root->right);
+    if (root->data != NULL) {
+      free(root->data);
+    }
+    free(root);
+  }
+}