Commit baebca6
Changed files (4)
src
02
src/02/03/btree.c
@@ -23,13 +23,15 @@ static void inspect(BTree *tree, int level) {
}
/**
- * Initializes the root of a binary tree
+ * Initializes an new subtree in a binary tree
*
+ * @param parent the parent of the new btree node
* @param data the data to assign to the root of the tree.
- * @return Returns the root of the tree.
+ * @return Returns the new subtree
*/
-BTree *btree_init(int data) {
+BTree *btree_initialize(BTree *parent, int data) {
BTree *tree = malloc(sizeof(BTree));
+ tree->parent = parent;
tree->left = NULL;
tree->right = NULL;
tree->data = data;
@@ -66,7 +68,21 @@ List *btree_to_list(BTree *tree)
int btree_size(BTree *tree) {
List *list = btree_to_list(tree);
- return list_size(list);
+ return list ? list_size(list) : 0;
+}
+
+BTree *btree_rebalance(BTree *tree)
+{
+ if (!tree->parent)
+ return tree;
+
+ int size = btree_size(tree);
+ int parent_size = btree_size(tree->parent);
+ /*float ratio = size / parent_size;*/
+ float ratio = 0.0;
+ printf("%d / %d = %f\n", size, parent_size, ratio);
+
+ return tree;
}
/**
@@ -77,18 +93,19 @@ int btree_size(BTree *tree) {
*/
BTree *btree_insert(BTree *tree, int data) {
if (!tree)
- return btree_init(data);
+ return btree_initialize(NULL, data);
if (data <= tree->data)
if (tree->left)
btree_insert(tree->left, data);
else
- tree->left = btree_init(data);
+ tree->left = btree_initialize(tree, data);
else if (tree->right)
btree_insert(tree->right, data);
else
- tree->right = btree_init(data);
+ tree->right = btree_initialize(tree, data);
+ /*return btree_rebalance(tree);*/
return tree;
}
src/02/03/btree.h
@@ -4,10 +4,12 @@
typedef struct btree_node {
struct btree_node *left;
struct btree_node *right;
+ struct btree_node *parent;
int data;
} BTree;
-BTree *btree_init(int data);
+BTree *btree_initialize(BTree *parent, int data);
BTree *btree_insert(BTree *root, int data);
+BTree *btree_rebalance(BTree *tree);
void btree_inspect(BTree *tree);
int btree_size(BTree *tree);
src/02/03/btree_test.c
@@ -16,7 +16,7 @@ Ensure(BinaryTree, when_the_tree_is_NULL) {
Ensure(
BinaryTree,
when_inserting_an_item_less_than_the_root_in_a_tree_it_creates_a_node_on_the_left_side) {
- BTree *tree = btree_init(10);
+ BTree *tree = btree_insert(NULL, 10);
btree_insert(tree, -5);
assert_that(tree->left, is_not_equal_to(NULL));
@@ -26,7 +26,7 @@ Ensure(
Ensure(
BinaryTree,
when_inserting_an_item_greater_than_the_root_in_a_tree_it_creates_a_node_on_the_right_side) {
- BTree *tree = btree_init(10);
+ BTree *tree = btree_insert(NULL, 10);
btree_insert(tree, 16);
@@ -37,7 +37,7 @@ Ensure(
Ensure(
BinaryTree,
when_inserting_an_item_equal_to_the_root_in_a_tree_it_creates_a_node_on_the_left_side) {
- BTree *tree = btree_init(10);
+ BTree *tree = btree_insert(NULL, 10);
btree_insert(tree, 10);
@@ -78,6 +78,26 @@ Ensure(
assert_that(tree->left->right->left->data, is_equal_to(6));
}
+Ensure(BinaryTree, when_rebalancing_a_tree) {
+ BTree *tree = btree_insert(NULL, 1);
+ tree->right = btree_initialize(tree, 5);
+ tree->right->left = btree_initialize(tree, 2);
+ tree->right->left->right = btree_initialize(tree, 4);
+ tree->right->left->right = btree_initialize(tree, 4);
+
+ tree = btree_insert(tree, 2);
+ tree = btree_insert(tree, 4);
+ tree = btree_insert(tree, 3);
+
+ tree = btree_rebalance(tree);
+
+ assert_that(tree, is_not_equal_to(NULL));
+
+ /*printf("%d\n", tree->parent->data);*/
+ assert_that(tree->right->parent, is_not_equal_to(NULL));
+
+}
+
Ensure(
BinaryTree,
when_inserting_items_described_in_the_assignment_it_inserts_in_the_expected_position_in_the_tree) {
@@ -117,24 +137,25 @@ Ensure(BinaryTree, when_calculating_the_size_of_the_tree)
TestSuite *binary_search_tree_tests() {
TestSuite *suite = create_test_suite();
- add_test_with_context(suite, BinaryTree, when_the_tree_is_NULL);
- add_test_with_context(
- suite, BinaryTree,
- when_inserting_an_item_less_than_the_root_in_a_tree_it_creates_a_node_on_the_left_side);
- add_test_with_context(
- suite, BinaryTree,
- when_inserting_an_item_greater_than_the_root_in_a_tree_it_creates_a_node_on_the_right_side);
- add_test_with_context(
- suite, BinaryTree,
- when_inserting_an_item_equal_to_the_root_in_a_tree_it_creates_a_node_on_the_left_side);
- add_test_with_context(
- suite, BinaryTree,
- when_inserting_multiple_items_into_a_tree_it_inserts_in_the_correct_position);
+ /*add_test_with_context(suite, BinaryTree, when_the_tree_is_NULL);*/
+ /*add_test_with_context(*/
+ /*suite, BinaryTree,*/
+ /*when_inserting_an_item_less_than_the_root_in_a_tree_it_creates_a_node_on_the_left_side);*/
+ /*add_test_with_context(*/
+ /*suite, BinaryTree,*/
+ /*when_inserting_an_item_greater_than_the_root_in_a_tree_it_creates_a_node_on_the_right_side);*/
+ /*add_test_with_context(*/
+ /*suite, BinaryTree,*/
+ /*when_inserting_an_item_equal_to_the_root_in_a_tree_it_creates_a_node_on_the_left_side);*/
+ /*add_test_with_context(*/
+ /*suite, BinaryTree,*/
+ /*when_inserting_multiple_items_into_a_tree_it_inserts_in_the_correct_position);*/
+ add_test_with_context(suite, BinaryTree, when_rebalancing_a_tree);
/*add_test_with_context(*/
/*suite, BinaryTree,*/
/*when_inserting_items_described_in_the_assignment_it_inserts_in_the_expected_position_in_the_tree);*/
- add_test_with_context(suite, BinaryTree, when_calculating_the_size_of_the_tree);
+ /*add_test_with_context(suite, BinaryTree, when_calculating_the_size_of_the_tree);*/
return suite;
}
src/02/README.md
@@ -208,25 +208,32 @@ Insert 5:
Insert 2:
(1)
- / \
- (2) (5)
+ \
+ (5)
+ /
+ (2)
+
Insert 4:
(1)
- / \
- (2) (5)
- /
- (4)
+ \
+ (5)
+ /
+ (2)
+ \
+ (4)
Insert 3:
(1)
- / \
- (2) (5)
- /
- (4)
- /
- (3)
+ \
+ (5)
+ /
+ (2)
+ \
+ (4)
+ /
+ (3)
```
The above diagram illustrates some negative consequences
@@ -255,59 +262,59 @@ Other, balanced binary search tree algorithms like the
AVL tree or Red-Black tree typically require adding additional
data to each node in the tree in order to keep the tree balanced.
-The insertion of `1,5,2,4,3` into a scapegoat tree would look
+The insertion of `1,5,2,4,3` into a scapegoat tree would look
like the following:
```plaintext
Insert 1:
- (1) 0/1 > 2/3: false
+ (1)
Insert 5:
- (1) 1/2 > 2/3: false
+ (1) 1/2
\
- (5) 0/1 > 2/3: false
+ (5)
Insert 2:
- (1) 1/2 > 2/3: false
- / \
- (2) (5) 0/1 > 2/3: false
-
-Insert 4:
(1) 2/3 > 2/3: false
- / \
- (2) (5) 1/2 > 2/3: false
- /
- (4) 0/1 > 2/3: false
-
-Insert 3:
+ \
+ (5) 1/2 > 2/3: false
+ /
+ (2)
+Insert 4:
(1) 3/4 > 2/3: true (scapegoat)
- / \
- (2) (5) 2/3 > 2/3: false
- /
- (4) 1/2 > 2/3: false
- /
- (3) 0/1 > 2/3: false
+ \
+ (5) 2/3 > 2/3: false
+ /
+ (2) 1/2 > 2/3: false
+ \
+ (4)
```
The next step is to rebalance from the scapegoat node.
Rebalance:
-1. collect nodes in sorted order: [1,3,4,5]
+1. collect nodes in sorted order: [1,2,4,5]
1. find new root: size/2 = 4/2 = 2
-1. 3 is the second node and is selected as the new root
+1. 2 is the second node and is selected as the new root
1. [1] is moved to the left subtree
1. [4,5] are moved to the right subtree
-The final result is a balanced binary search tree.
-
```plaintext
- (3)
+ (2)
+ / \
+ (1) (4)
+ \
+ (5)
+
+Insert 3:
+
+ (2) 3/5 > 2/3: false
/ \
- (2) (4)
- / \
- (1) (5)
+ (1) (4) 1/3 > 2/3: false
+ / \
+ (3) (5)
```
### Description of the Code