libvieter/test/tree/test_balancing.c

72 lines
2.1 KiB
C
Raw Permalink Normal View History

2023-02-01 22:12:34 +01:00
#include "acutest.h"
#include "vieter_tree_internal.h"
#include "vieter_tree_node.h"
#include "vieter_tree_balancing.h"
2023-02-01 23:04:35 +01:00
// This uses the examples from wikipedia
// https://en.wikipedia.org/wiki/Tree_rotation
2023-02-01 22:12:34 +01:00
void test_rotate_right() {
vieter_tree_node *a = vieter_tree_node_init();
vieter_tree_node *b = vieter_tree_node_init();
vieter_tree_node *p = vieter_tree_node_init();
vieter_tree_node_set_child(p, a, false);
vieter_tree_node_set_child(p, b, true);
vieter_tree_node *c = vieter_tree_node_init();
vieter_tree_node *q = vieter_tree_node_init();
vieter_tree_node_set_child(q, p, false);
vieter_tree_node_set_child(q, c, true);
vieter_tree_node *new_root = vieter_tree_node_rotate(q, true);
TEST_CHECK(new_root == p);
TEST_CHECK(new_root->children[0] == a);
TEST_CHECK(new_root->children[1] == q);
TEST_CHECK(new_root->children[1]->children[0] == b);
TEST_CHECK(new_root->children[1]->children[1] == c);
2023-02-01 23:04:35 +01:00
vieter_tree_node_free(a);
vieter_tree_node_free(b);
vieter_tree_node_free(p);
vieter_tree_node_free(c);
vieter_tree_node_free(q);
2023-02-01 22:12:34 +01:00
}
void test_rotate_left() {
vieter_tree_node *b = vieter_tree_node_init();
vieter_tree_node *c = vieter_tree_node_init();
vieter_tree_node *q = vieter_tree_node_init();
vieter_tree_node_set_child(q, b, false);
vieter_tree_node_set_child(q, c, true);
vieter_tree_node *a = vieter_tree_node_init();
vieter_tree_node *p = vieter_tree_node_init();
vieter_tree_node_set_child(p, a, false);
vieter_tree_node_set_child(p, q, true);
vieter_tree_node *new_root = vieter_tree_node_rotate(p, false);
TEST_CHECK(new_root == q);
TEST_CHECK(new_root->children[0] == p);
TEST_CHECK(new_root->children[1] == c);
TEST_CHECK(new_root->children[0]->children[0] == a);
TEST_CHECK(new_root->children[0]->children[1] == b);
2023-02-01 23:04:35 +01:00
vieter_tree_node_free(a);
vieter_tree_node_free(b);
vieter_tree_node_free(p);
vieter_tree_node_free(c);
vieter_tree_node_free(q);
2023-02-01 22:12:34 +01:00
}
TEST_LIST = {
2023-02-01 23:24:22 +01:00
{"tree rotate right", test_rotate_right},
{"tree rotate left", test_rotate_left},
2023-02-01 22:12:34 +01:00
{NULL, NULL}
};