blob: 98cd18b31fbcae4f25b57ad3c05114ccc53f6a2e (
plain)
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
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);
}
}
|
