include/lib/algo/avl_tree.h


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

#ifndef INC_LIB_ALGO_AVL_TREE_H
#define INC_LIB_ALGO_AVL_TREE_H

#include <lib/bool.h>
#include <lib/monad.h>
#include <stdint.h>
#include <stdlib.h>
#include <sys/types.h>

#define AvlHeight_t uint8_t

typedef bool_t (*AvlComparator)(void *, void *);

typedef struct AVLNode {
  void *data;
  AvlComparator compare;
  struct AVLNode *left;
  struct AVLNode *right;
  AvlHeight_t height;
} AVLNode;

// Get the height of an AVL node
AvlHeight_t get_height(AVLNode *node);

// Get the Maximum Height between two
AvlHeight_t max_height(AvlHeight_t a, AvlHeight_t b);

// Get the balance factor of a node
ssize_t get_balance_factor(AVLNode *node);

// Rotate an AVL node right
AVLNode *right_rotate(AVLNode *parent);

// Rotate an AVL node left
AVLNode *left_rotate(AVLNode *parent);

// Create AVL node
AVLNode *create_avl_node(void *data, AvlComparator compare);

// Insert data into AVL tree
Result avl_insert(AVLNode *node, void *data, AvlComparator compare);

// In-order traversal print pointer
void print_in_order(AVLNode *root);

// Free avl tree nodes starting at root
void free_avl_tree(AVLNode *root);

// Free avl tree and their data starting at root
void free_avl_tree_nodes(AVLNode *root);

#endif