1 files changed, 69 insertions, 0 deletions
diff --git a/src/lib/algo/avl_tree.c b/src/lib/algo/avl_tree.c
index 98cd18b..db4fa4b 100644
--- a/src/lib/algo/avl_tree.c
+++ b/src/lib/algo/avl_tree.c
@@ -56,6 +56,75 @@ struct AVLNode* left_rotate(struct AVLNode* parent)
   return child1;
 }
 
+// Create AVL node
+struct AVLNode* create_avl_node(void* data, bool_t (*compare)(void*, void*))
+{
+  struct AVLNode* node = (struct AVLNode*)malloc(sizeof(struct AVLNode));
+  if (node == NULL) {
+    return NULL;
+  }
+  node->data = data;
+  node->compare = compare;
+  node->left = NULL;
+  node->right = NULL;
+  node->height = 1; // Leaf initially
+  return node;
+}
+
+// Insert data into AVL tree
+struct Result avl_insert(struct AVLNode* node, void* data, bool_t (*compare)(void*, void*))
+{
+  struct Result result;
+  // 1. Standard BST insertion
+  if (node == NULL) {
+    return (struct Result) {create_avl_node(data, compare), TRUE};
+  }
+
+  struct MaskData *node_data = (struct MaskData*)node->data;
+  if (node->compare(data, node_data)) {
+    result = avl_insert(node->left, data, compare);
+    if (!result.success) {
+      fprintf(stderr, "Failed to insert!");
+      return result;
+    }
+    node->left = (struct AVLNode*)result.data;
+  } else if (node->compare(node->data, data)) {
+    result = avl_insert(node->right, data, compare);
+    if (!result.success) {
+      fprintf(stderr, "Failed to insert!");
+      return result;
+    }
+    node->right = (struct AVLNode*)result.data;
+  } else {
+    return (struct Result) {node, FALSE};
+  }
+
+  // 2. Update height of the ancestor node
+  node->height = 1 + max_height(get_height(node->left), get_height(node->right));
+
+  ssize_t balance = get_balance_factor(node);
+
+  // 4. If the node becomes unbalanced
+
+  // LeftLeft
+  if ((balance > 1) && node->compare(data, node->left->data)) {
+    return (struct Result) {right_rotate(node), TRUE};
+  }
+  // RightRight
+  if ((balance < -1) && node->compare(node->right->data, data)) {
+    return (struct Result) {left_rotate(node), TRUE};
+  }
+  // LeftRight
+  if ((balance > 1) && node->compare(node->left->data, data)) {
+    return (struct Result) {right_rotate(node), TRUE};
+  }
+  // RightLeft
+  if ((balance < -1) && node->compare(data,node->right->data)) {
+    return (struct Result) {left_rotate(node), TRUE};
+  }
+  return (struct Result) {node, TRUE};
+}
+
 // In-order traversal print pointer
 void print_in_order(struct AVLNode* root)
 {