From baebca68ac33d4c5a41c05c8cc7375a80f928a4b Mon Sep 17 00:00:00 2001 From: mo khan Date: Sun, 16 Aug 2020 18:19:07 -0600 Subject: Fix mistake in program profile --- src/02/03/btree.c | 31 ++++++++++++++---- src/02/03/btree.h | 4 ++- src/02/03/btree_test.c | 55 +++++++++++++++++++++---------- src/02/README.md | 89 +++++++++++++++++++++++++++----------------------- 4 files changed, 113 insertions(+), 66 deletions(-) (limited to 'src/02') diff --git a/src/02/03/btree.c b/src/02/03/btree.c index b44e173..8601927 100644 --- a/src/02/03/btree.c +++ b/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; } diff --git a/src/02/03/btree.h b/src/02/03/btree.h index fd26ba4..fe41860 100644 --- a/src/02/03/btree.h +++ b/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); diff --git a/src/02/03/btree_test.c b/src/02/03/btree_test.c index 12416a5..47cd438 100644 --- a/src/02/03/btree_test.c +++ b/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; } diff --git a/src/02/README.md b/src/02/README.md index e0ae1b0..fd0d1c5 100644 --- a/src/02/README.md +++ b/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 -- cgit v1.2.3