This is the portion of data structures and algorithms that I got completely lost on as a third year ECE major. It was also THE FIRST thing they taught us in that class (why they wouldn’t start with linear data structures like arrays and lists is beyond me). Fortunately there are TONS of resources to brush up on tree data structures and thus the implementation of this was not as painful as I thought it was going to be. <\/p>\n\n\n\n
Up until now, every data structure we\u2019ve implemented has been linear<\/strong>. There is exactly one path<\/strong> through the data.<\/p>\n\n\n\n If you imagine them visually, they look like a chain:<\/p>\n\n\n\n Each element knows about at most one next element (and sometimes one previous element). If you want to find something in a linked list, you usually have to walk element by element:<\/p>\n\n\n\n Worst case:<\/p>\n\n\n\n This is fine for small datasets, but once data gets large, linear traversal becomes expensive.<\/p>\n\n\n\n Tree data structures break away from the idea of a single path.<\/p>\n\n\n\n Instead of each element pointing to just one next element, tree elements can branch (hence the tree name):<\/p>\n\n\n\n The advantage here should become pretty clear. Let’s see we want to find the E Node. For our linked list, that means walking the entire list until we hit the E node. That is 5 ops. For this tree above, we simply visit A, then B, then we hit E (how this actually occurs will become more clear as we step into the specific definition of what makes a binary search tree a binary search tree). <\/p>\n\n\n\n So, how does that specific case above actually occur and optimize our search for a node? A Binary Search Tree is a specific kind of tree with two rules:<\/p>\n\n\n\n Each node has at most two children:<\/p>\n\n\n\n For every node:<\/p>\n\n\n\n It is this second rule that really solidifies why our search for E case is faster for a BST vs a linear data structure. <\/p>\n\n\n\n Search example:<\/p>\n\n\n\n Everything left of 50 is smaller. This rule is applied recursively throughout the tree.<\/p>\n\n\n\n So lets say we want to look for the value 60 in this tree:<\/p>\n\n\n\n Instead of checking every element, you eliminate half the tree at each step (in ideal cases where we have a balanced tree). <\/p>\n\n\n\n BSTs are defined primarily by three operations:<\/p>\n\n\n\n Place a new value in the correct position while maintaining ordering.<\/p>\n\n\n\n Find whether a value exists by following left\/right decisions.<\/p>\n\n\n\n Remove a value while preserving BST structure.<\/p>\n\n\n\n This is the hardest operation because removing nodes can break ordering if done incorrectly.<\/p>\n\n\n\n Traversal isn\u2019t always listed as a \u201ccore BST operation,\u201d but it is extremely important.<\/p>\n\n\n\n Traversal means visiting every node in a specific order.<\/p>\n\n\n\n For BSTs, the most important traversal is:<\/p>\n\n\n\n This prints BST values in sorted order.<\/p>\n\n\n\n This is one of the biggest reasons BSTs are useful.<\/p>\n\n\n\n BST performance depends on tree shape.<\/p>\n\n\n\n If the tree stays balanced:<\/p>\n\n\n\n If the tree becomes skewed (like inserting sorted data):<\/p>\n\n\n\n Worst case BST becomes a linked list.<\/p>\n\n\n\n This is exactly what our benchmarks later will demonstrate.<\/p>\n\n\n\n So like before, I will show you the header file and then we will discuss each function. This code is FULL of comments since the concepts here are sometimes a bit rough to grasp (or at least I found them hard to grasp upon first look): <\/p>\n\n\n\n bst.h<\/strong><\/p>\n\n\n\n bst.c <\/strong><\/p>\n\n\n\n And here is what we get when we benchmark our tree structure:<\/p>\n\n\n\n Throughout this entire blog post I have hinted at the idea of a balanced tree. This tree we implemented is not “balanced” by any means depending on how you insert elements. If we were to insert elements that are already in order, we literally would have a BST that looks like a linked list at a 45 degree angle:<\/p>\n\n\n\n Pretty funny if you ask me, and the result of this is that our complexity table for operations ends up being identical to a linked list. The REAL power comes when we insert the values in a random order: <\/p>\n\n\n\n I apologize for the really bad formatting on that above tree, but it should get the point across that the operations on this tree are faster than our unbalanced tree from before. It results in O(log(n)) complexity at best, and at worst, O(n) complexity since it essentially is a linked list. <\/p>\n\n\n\n So… what if there was a way to insert into a tree to force it to be balanced? There is (AVL tree), and that is going to be our next post which will be delayed since the Mardi Gras season is now upon us. For those of you unaware, Mardi Gras is Louisiana’s excuse to drop everything we are doing and party for a week straight \ud83d\ude42 <\/p>\n\n\n\n <\/p>\n","protected":false},"excerpt":{"rendered":" This is the portion of data structures and algorithms that I got completely lost on as a third year ECE major. It was also THE FIRST thing they taught us in that class (why they wouldn’t start with linear data structures like arrays and lists is beyond me). Fortunately there are TONS of resources to […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-89","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/mattbick.dev\/index.php?rest_route=\/wp\/v2\/posts\/89","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/mattbick.dev\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mattbick.dev\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mattbick.dev\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/mattbick.dev\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=89"}],"version-history":[{"count":1,"href":"https:\/\/mattbick.dev\/index.php?rest_route=\/wp\/v2\/posts\/89\/revisions"}],"predecessor-version":[{"id":90,"href":"https:\/\/mattbick.dev\/index.php?rest_route=\/wp\/v2\/posts\/89\/revisions\/90"}],"wp:attachment":[{"href":"https:\/\/mattbick.dev\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=89"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mattbick.dev\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=89"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mattbick.dev\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=89"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
Linked lists, stacks, queues, and deques all share one core idea:<\/p>\n\n\n\n[ A ] -> [ B ] -> [ C ] -> [ D ] -> [ E ] \/\/ should remind you of our previous linked list implementations <\/code><\/pre>\n\n\n\n
This makes them simple and predictable, but it also limits how efficiently we can search them.<\/p>\n\n\n\nO(N) \/\/ for other ops as we have shown, we can augment the linked list data structure with a tail or previous pointer to make other ops O(1)<\/code><\/pre>\n\n\n\n
\n\n\n\nEnter Tree Data Structures<\/h1>\n\n\n\n
A\n \/ \\\n B C\n \/ \\\n D E<\/code><\/pre>\n\n\n\n
\n\n\n\nIntroducing the Binary Search Tree (BST)<\/h1>\n\n\n\n
Rule 1 \u2014 Binary<\/h3>\n\n\n\n
left child\nright child<\/code><\/pre>\n\n\n\n
\n\n\n\nRule 2 \u2014 Ordered (This Is The Important Part)<\/h3>\n\n\n\n
left subtree < node value < right subtree \/\/ for out letters, it means being in alphabetical order. for numbers, we can just use more than or less than operators<\/code><\/pre>\n\n\n\nAnother Example:<\/h2>\n\n\n\n
50\n \/ \\\n 30 70\n \/ \\ \/ \\\n 20 40 60 80<\/code><\/pre>\n\n\n\n
Everything right of 50 is larger.<\/p>\n\n\n\nStart at 50 \u2192 60 > 50 \u2192 go right\nAt 70 \u2192 60 < 70 \u2192 go left\nFound 60<\/code><\/pre>\n\n\n\n
\n\n\n\nThe Three Core BST Operations<\/h1>\n\n\n\n
Insert<\/h3>\n\n\n\n
\n\n\n\nSearch<\/h3>\n\n\n\n
\n\n\n\nDelete<\/h3>\n\n\n\n
\n\n\n\nThe Hidden Fourth Operation: Traversal<\/h1>\n\n\n\n
In-Order Traversal<\/h3>\n\n\n\n
Left \u2192 Node \u2192 Right<\/code><\/pre>\n\n\n\n
\n\n\n\nImportant Reality: BSTs Are Not Always Fast<\/h1>\n\n\n\n
Search \u2248 O(log N)<\/code><\/pre>\n\n\n\nSearch \u2248 O(N)<\/code><\/pre>\n\n\n\n
\n\n\n\nThe Actual Challenge: Implementation in C:<\/h2>\n\n\n\n
#ifndef BST_H\n#define BST_H\n\n#include <stdio.h>\n#include <stdlib.h>\n\nstruct Node {\n\n int key;\n struct Node* l;\n struct Node* r;\n};\n\nstruct BST {\n struct Node* root;\n};\n\nstruct Node* alloc_node(int key);\n\nint insert(int key, struct BST* tree);\n\nstruct Node* search(int key, struct BST* tree);\n\nstruct Node** search_for_delete(int key, struct BST* tree);\n\nint delete(int key, struct BST* tree);\n\nvoid free_subtree(struct Node* node);\n\nvoid destroy_bst(struct BST* tree);\n\nvoid print_sub_tree_in_order(struct Node* node);\n\nvoid print_tree_in_order(struct BST* tree);\n\n#endif<\/code><\/pre>\n\n\n\n#include "bst.h"\n\nstruct Node* alloc_node(int key) {\n struct Node* new_node = malloc(sizeof(struct Node));\n if (!new_node) return NULL; \/\/malloc failed, return NULL\n new_node->key = key;\n new_node->l = NULL;\n new_node->r = NULL;\n return new_node;\n}\n\nint insert(int key, struct BST* tree) {\n\n if (!tree) return 1; \/\/error, bst pointer is invalid!\n\n \/\/first, we handle the case where we are inserting into an empty tree\n if (!tree->root) {\n struct Node* new_root = alloc_node(key);\n tree->root = new_root;\n return 0;\n }\n\n \/\/okay so now, if the tree is not empty, we have to traverse the tree\n \/\/to start, we grab the current root node\n struct Node* curr_node = tree->root;\n\n while (1) {\n if (key < curr_node->key) {\n if (curr_node->l == NULL) {\n struct Node* new_node = alloc_node(key);\n if (!new_node) return 1; \/\/node allocation failed\n curr_node->l = new_node;\n return 0;\n }\n curr_node = curr_node->l; \/\/if the node is populated, we keep traversing\n }\n else if (key > curr_node->key) {\n if (curr_node->r == NULL) {\n struct Node* new_node = alloc_node(key);\n if (!new_node) return 1; \/\/node allocation failed\n curr_node->r = new_node;\n return 0;\n }\n curr_node = curr_node->r; \/\/if the node is populated, we keep traversing\n }\n else {\n \/\/the key is equal... we will exlcude duplicate\n return 2; \/\/duplicate error code!\n }\n }\n\n return 0;\n}\n\nstruct Node* search(int key, struct BST* tree) {\n\n if (!tree || !tree->root) return NULL; \/\/invalid tree pointer or tree is empty\n\n struct Node* curr_node = tree->root;\n\n while (1) {\n if (key < curr_node->key) { \/\/if less, we need to search down the left node\n if (curr_node->l == NULL) return NULL; \/\/this means there is no left node, which means node is not in the tree, return NULL\n curr_node = curr_node->l;\n }\n else if (key > curr_node->key) { \/\/if more, we need to search down the right node\n if (curr_node->r == NULL) return NULL; \/\/same as above, just for the right node\n curr_node = curr_node->r;\n }\n else {\n return curr_node;\n }\n }\n\n return NULL; \/\/node not found, return NULL\n}\n\nstruct Node** search_for_delete(int key, struct BST* tree) {\n\n if (!tree || !tree->root) return NULL;\n\n struct Node** curr_node = &tree->root;\n\n while (1) {\n if (key < (*curr_node)->key) {\n if ((*curr_node)->l == NULL) return NULL;\n curr_node = &(*curr_node)->l;\n }\n else if (key > (*curr_node)->key) {\n if ((*curr_node)->r == NULL) return NULL;\n curr_node = &(*curr_node)->r;\n }\n else {\n return curr_node;\n }\n }\n\n return NULL;\n}\n\nint delete(int key, struct BST* tree) {\n\n struct Node** node_link = search_for_delete(key, tree);\n if (!node_link) return 1; \/\/node not found, return 1\n\n struct Node* node = *node_link;\n\n \/\/this node is leaf node, deletion is easy\n if (!node->l && !node->r) {\n *node_link = NULL;\n free(node);\n return 0;\n }\n else if (node->l && !node->r) { \/\/only left node\n *node_link = node->l;\n free(node);\n return 0;\n }\n else if (!node->l && node->r) { \/\/only right node\n *node_link = node->r;\n free(node);\n return 0;\n }\n else if (node->l && node->r) {\n\n \/\/if node has both children, it gets complicated, we need to preserve the correctness of the tree\n \/\/to do this, we have to use a little trick\n \/\/its called successor (another apporach is precessor)\n \/\/we take the node to be deleted (which in this case, is *node_link or node as shown above)\n \/\/then, we go down the RIGHT subtree of that node\n \/\/once we go down the RIGHT subtree, we find the minimum node of that right subtree\n \/\/since we know this subtree is valid (or we at least assume it is), we simply keep following the left nodes\n \/\/once we hit the last left node, IE the mimimum, we stop\n \/\/using that miminum value (the key of the node), we insert that value into the node we wish to delete\n \/\/so now, instead of free(node), we ACTUALLY free the minimum node of the right subtree (the node we stole the key from)\n\n \/\/so, grab the right node\n struct Node** curr_node_link = &node->r;\n\n \/\/then, we iterate until we hit the minimum value by going deeper and deeper down the left path\n while ((*curr_node_link)->l != NULL) {\n curr_node_link = &(*curr_node_link)->l;\n }\n\n \/\/the node we wish to delete is not deleted\n \/\/instead we copy the value of minimum node into the node we wish to delete\n struct Node* successor = *curr_node_link;\n node->key = successor->key;\n\n \/\/if our successor node has a right subtree, we need to make sure it stays connected to our BST\n *curr_node_link = successor->r;\n\n \/\/THEN, we actually delete the minimum node\n free(successor);\n return 0;\n }\n\n return 0;\n}\n\nvoid free_subtree(struct Node* node) {\n\n if (node == NULL) return;\n\n free_subtree(node->l);\n free_subtree(node->r);\n free(node);\n}\n\nvoid destroy_bst(struct BST* tree) {\n\n if (tree == NULL) return;\n\n free_subtree(tree->root);\n tree->root = NULL;\n}\n\nvoid print_sub_tree_in_order(struct Node* node) {\n\n if (node == NULL) return; \/\/we have reached the end, early exit\n\n print_sub_tree_in_order(node->l);\n printf("%d ", node->key);\n print_sub_tree_in_order(node->r);\n}\n\n\/\/and to close, we are going to write a function that traverses the tree in order and prints the keys\n\/\/doing this should just print a sorted list of numbers from low to high!\n\/\/that is what makes BSTs so useful, their definition forces useful properties\nvoid print_tree_in_order(struct BST* tree) {\n\n \/\/to do this, we need print in this order:\n \/\/left subtree -> parent node -> right subtree\n \/\/this will be done recursively for this example\n \/\/in the future we might use a stack or other structure to implement this functionality, havent made my mind up yet\n\n \/\/therefore for this to work, we need to go all the way left (the smallest value), THEN PRINT\n\n if (tree == NULL || tree->root == NULL) return; \/\/invalid tree pointer, early exit dont even try and print\n\n print_sub_tree_in_order(tree->root);\n printf("\\n");\n}<\/code><\/pre>\n\n\n\n=== Binary Search Tree Benchmark ===\nReal implementation timing (includes malloc\/free)\n\n=============================\nBENCH N=1000\n=============================\n\n--- CASE: SORTED INSERT (worst-case shape) ---\ninsert worst O(N)\/op | 0.819 ms | 818.6 ns\/op\nsearch worst O(N)\/op | 914.651 ms | 457.3 ns\/op (REPS=2000000)\ndelete worst O(N)\/op | 0.008 ms | 8.1 ns\/op (OPS=1000)\n\n--- CASE: PSEUDO-RANDOM INSERT (average-ish shape) ---\ninsert avg ~O(log N)\/op | 0.055 ms | 54.8 ns\/op\nsearch avg ~O(log N)\/op | 89.296 ms | 44.6 ns\/op (REPS=2000000)\ndelete avg ~O(log N)\/op | 0.069 ms | 69.0 ns\/op (OPS=1000)\n\n=============================\nBENCH N=3000\n=============================\n\n--- CASE: SORTED INSERT (worst-case shape) ---\ninsert worst O(N)\/op | 5.284 ms | 1761.4 ns\/op\nsearch worst O(N)\/op | 3737.766 ms | 1868.9 ns\/op (REPS=2000000)\ndelete worst O(N)\/op | 0.021 ms | 7.0 ns\/op (OPS=3000)\n\n--- CASE: PSEUDO-RANDOM INSERT (average-ish shape) ---\ninsert avg ~O(log N)\/op | 0.157 ms | 52.4 ns\/op\nsearch avg ~O(log N)\/op | 121.852 ms | 60.9 ns\/op (REPS=2000000)\ndelete avg ~O(log N)\/op | 0.237 ms | 78.9 ns\/op (OPS=3000)\n\n=============================\nBENCH N=10000\n=============================\n\n--- CASE: SORTED INSERT (worst-case shape) ---\ninsert worst O(N)\/op | 99.876 ms | 9987.6 ns\/op\nsearch worst O(N)\/op | 16909.552 ms | 8454.8 ns\/op (REPS=2000000)\ndelete worst O(N)\/op | 0.088 ms | 8.8 ns\/op (OPS=10000)\n\n--- CASE: PSEUDO-RANDOM INSERT (average-ish shape) ---\ninsert avg ~O(log N)\/op | 0.661 ms | 66.1 ns\/op\nsearch avg ~O(log N)\/op | 152.629 ms | 76.3 ns\/op (REPS=2000000)\ndelete avg ~O(log N)\/op | 0.977 ms | 97.7 ns\/op (OPS=10000)\n<\/code><\/pre>\n\n\n\n
\n\n\n\nSome Important Notes on the Benchmark<\/h2>\n\n\n\n
Insert: 1, 2, 3, 4, 5\n\n1\n \\\n 2\n \\\n 3\n \\\n 4\n \\\n 5<\/code><\/pre>\n\n\n\nInsert Order: 3, 1, 5, 2, 4\n 3\n \/ \\\n 1 5\n \\ \/\n 2 4<\/code><\/pre>\n\n\n\n