AVL Tree

Mask data stored in AVL tree

1 files changed, 173 insertions, 0 deletions

diff --git a/src/main.c b/src/main.c
index 94315e4..a710ecb 100644
--- a/src/main.c
+++ b/src/main.c
@@ -16,8 +16,181 @@
 
 #define N_DILATIONS 3
 
+struct Result {
+  void* data;
+  bool_t success;
+};
+
+struct MaskData {
+  uint16_t label;
+  size_t area;
+  size_t perimeter;
+};
+
+struct MaskData* create_mask_data(uint16_t label) {
+  struct MaskData *data = (struct MaskData*)malloc(sizeof(struct MaskData));
+  data->label = label;
+  data->area = 0;
+  data->perimeter = 0;
+  return data;
+}
+
+struct AVLNode {
+  void* data;
+  bool_t (*compare)(void*, void*);
+  struct AVLNode* left;
+  struct AVLNode* right;
+  uint8_t height;
+};
+
+uint8_t get_height(struct AVLNode* node)
+{
+  if (node == NULL) {
+    return 0;
+  }
+  return node->height;
+}
+
+bool_t compare_labels(struct MaskData* left, struct MaskData* right)
+{
+  return left->label < right->label;
+}
+
+struct AVLNode* create_avl_mask_node(struct MaskData* data)
+{
+  struct AVLNode* node = (struct AVLNode*)malloc(sizeof(struct AVLNode));
+  if (node == NULL) {
+    return NULL;
+  }
+  node->data = data;
+  node->compare = (bool_t (*)(void*,void*))&compare_labels;
+  node->left = NULL;
+  node->right = NULL;
+  node->height = 1; // Leaf initially
+  return node;
+}
+
+uint8_t max_height(uint8_t a, uint8_t b)
+{
+  return (a > b) ? a : b;
+}
+
+ssize_t get_balance_factor(struct AVLNode* node)
+{
+  if (node == NULL) {
+    return 0;
+  }
+  return get_height(node->left) - get_height(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;
+}
+
+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;
+}
+
+struct AVLNode* insert_mask(struct AVLNode* node, struct MaskData* data)
+{
+  // 1. Standard BST insertion
+  if (node == NULL) {
+    return create_avl_mask_node(data);
+  }
+
+  struct MaskData *node_data = (struct MaskData*)node->data;
+  if (node->compare(data, node_data)) {
+    node->left = insert_mask(node->left, data);
+  } else if (node->compare(node->data, data)) {
+    node->right = insert_mask(node->right, data);
+  } else {
+    return node;
+  }
+
+  // 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 right_rotate(node);
+  }
+  // RightRight
+  if ((balance < -1) && node->compare(node->right->data, data)) {
+    return left_rotate(node);
+  }
+  // LeftRight
+  if ((balance > 1) && node->compare(node->left->data, data)) {
+    return right_rotate(node);
+  }
+  // RightLeft
+  if ((balance < -1) && node->compare(data,node->right->data)) {
+    return left_rotate(node);
+  }
+  return node;
+}
+
+void print_label(struct AVLNode* root) {
+  if (root != NULL) {
+    print_label(root->left);
+    struct MaskData* data = root->data;
+    printf("%d: (%zu, %zu) ", data->label, data->area, data->perimeter);
+    print_label(root->right);
+  }
+}
+
+void free_avl_tree(struct AVLNode* root) {
+  if (root != NULL) {
+    free_avl_tree(root->left);
+    free_avl_tree(root->right);
+    free(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);
+  }
+}
+
 int main(int argc, char** argv)
 {
+  struct AVLNode* root = NULL;
+  root = insert_mask(root, create_mask_data(2));
+  root = insert_mask(root, create_mask_data(5));
+  root = insert_mask(root, create_mask_data(1));
+  root = insert_mask(root, create_mask_data(3));
+  root = insert_mask(root, create_mask_data(4));
+  printf("Inorder traversal of AVL tree: ");
+  print_label(root);
+  printf("\n");
+  free_avl_tree_nodes(root);
   //-----------------------------------------------
   //-LIST-FILES-IN-DIRECTORY-----------------------
   //-----------------------------------------------