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 91 92 93 94 95 96 97 98 | #include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
typedef struct _BSTNode {
int value;
struct _BSTNode* left;
struct _BSTNode* right;
} BSTNode;
int get_height(BSTNode const* root) {
if(root == NULL) {
return -1;
}
else {
int height_of_left = get_height(root -> left);
int height_of_right = get_height(root -> right);
return 1 + (height_of_left > height_of_right ? height_of_left : height_of_right);
}
}
int get_balance_score(BSTNode const* root) {
if(root == NULL) {
return 0;
}
else {
return get_height(root -> left) - get_height(root -> right);
}
}
void rotate_clockwise(BSTNode** a_root) { // Rotate left with root
BSTNode* old_root = *a_root;
BSTNode* new_root = old_root -> left;
old_root -> left = new_root -> right; // old_root -> left := "b"
new_root -> right = old_root;
*a_root = new_root;
}
void balance_after_insert_in_left(int value, BSTNode** a_root) {
if(get_balance_score(*a_root) == 2) {
if(value < (*a_root) -> left -> value) { // left -> left
// Single rotation
rotate_clockwise(a_root);
}
else if(value > (*a_root) -> left -> value) { // left -> right
// Double rotation
rotate_counterclockwise(&((*a_root) -> left));
rotate_clockwise(a_root);
}
}
}
// LECTURE EXERCISE
// 368get le07
// 368submit le07 *.txt
void insert(int value, BSTNode** a_root) {
if(*a_root == NULL) {
*a_root = malloc(sizeof **a_root);
**a_root = (BSTNode) { .value = value, .left = NULL, .right = NULL };
}
else if(value < (*a_root) -> value) {
insert(value, &((*a_root) -> left));
balance_after_insert_in_left(value, a_root);
}
else if(value > (*a_root) -> value) {
insert(value, &((*a_root) -> right));
balance_after_insert_in_right(value, a_root);
}
}
void print_bst_nodes(BSTNode const* root) {
if(root != NULL) {
print_bst_nodes(root -> left);
printf("[%d] ", root -> value);
print_bst_nodes(root -> right);
}
}
void print_bst(BSTNode const* root, char const* label) {
printf("%s%s", label, "");
print_bst_nodes(root);
printf("\n");
}
int main(int argc, char* argv[]) {
BSTNode* root = NULL;
insert(4, &root);
insert(2, &root);
insert(6, &root);
insert(1, &root);
insert(3, &root);
insert(5, &root);
insert(7, &root);
print_bst(root, "");
return EXIT_SUCCESS;
}
/* vim: set tabstop=4 shiftwidth=4 fileencoding=utf-8 noexpandtab: */
|
© Copyright 2023 Alexander J. Quinn This content is protected and may not be shared, uploaded, or distributed.