Honestly, this is probably one of the most hardest concepts for me to understand well, and when I was introduced to BSTs in my Software Design class, it was super hard for me to develop it into C or C++ code. I think understanding the basic algorithm or 'psuedocode' of a BST is a super important step when you have to translate a problem involving a BST structure into C/C++ code. so, what is a BST?A BST, or Binary Search Tree, is a tree data structure where every node (every circle in the diagram) has at most two child nodes: a left child node and a right child node. The left node (and subtree) is smaller than the parent node value, and the right node (and subtree) is larger than the parent node value. Every node doesn't have to have two children nodes; it could just have one node, with the other node pointing to NULL (meaning no value is stored in the node - so its not being used). A BST is represented by the pointer (address) to the topmost node, which is also called the root node. Every node has three different parts: the data value of the node, a pointer to the left node, and a pointer to the right node. We declare a node structure using struct function in C. To declare a node structure, we have the value of the node (usually a number, but can be any data type), the left node pointer (pointer to the left child of the parent node), and the right node pointer (pointer to the right child of the parent node). Note: when I say pointer, I am talking about a variable storing the address of the node (right/left). Declaring a Node Structure in C
So now that we know how a BST is structured, why do we even need it? If we need to store a bunch of random int data types, can't we just use an array of int types? We can most definetely use an array, however, for some tasks, the BST is super effective and efficient in terms of time complexity (how long it takes for the program to run). For example, when you are trying to sort elements in a particular order, the BST is very efficient since the elements are already sorted in a tree format. (right node is always greater than parent node and left node is always smaller than parent node). Therefore, it has an efficient algorithm, compared to arrays. algorithms with BSTs!!First, lets go through the search algorithm in a BST. How would you search an element in a BST? What if the element already exists in the BST? What if it doesn't exist? The easiest way to search for an element in a BST is to implement this recursively (meaning the program just calls itself again and again, until it reaches the base case). Check out the algorithm- this was based off of the geeks for geeks BST search set 1: https://www.geeksforgeeks.org/binary-search-tree-set-1-search-and-insertion/ In this search BST algorithm, if the output was a NULL node, then the program was not successful in finding the node with the element value. If it didn't return NULL, and it returned an actual existing node, it means it did find a value matching with the element. Lets now attempt an insert algorithm in a BST. How would we insert an element in a BST? Where would we insert the element? When we insert an element in a BST, we actually have to create a new node in order to actually insert it into the tree. We would first have to traverse through the tree to figure out where the element needs to be inserted, and then we create a new node to insert in that location. Lets use a helper function (seperate function) to make a new node, so that its easier to call that in our main insertBST function. Check out the algorithm-- this algorithm was based off of the geeks for geeks BST insert set 1: https://www.geeksforgeeks.org/binary-search-tree-set-1-search-and-insertion/ We can also use a recursive method to insert a new element into the tree. It was kinda difficult for me to grasp this at first, so I had to draw out how the tree would look like as you call the function again and again, recursively. So the base case here is whether the root is NULL, and if it is then you insert a new node there because that's where the element should exist. This program is recursively, so in the end, the new node is assigned to the root->left, or root->right depending on the value of the element. This is how it's added to the tree. NOTE: For this algorithm, we are assuming that the element does not exist in the tree already.
3 Comments
Mualla Argin
6/7/2019 10:23:58 pm
Was gonna do an hour of code every day but I guess I'll read these instead!:)
Reply
Aarushi Ramesh
6/7/2019 10:32:12 pm
lmao yessssss 😂!!!! tysm imy!!!
Reply
2/28/2024 07:25:16 am
Cloud computing revolutionizes the way businesses and individuals access, store, and manage data and applications. It leverages remote servers hosted on the internet to process, store, and manage data, offering scalability, flexibility, and cost-effectiveness. Users can access resources on-demand from anywhere, enabling collaboration and innovation. Cloud computing services range from infrastructure to software, providing businesses with the agility to adapt to changing demands and scale operations efficiently. It empowers organizations to focus on core competencies while outsourcing IT infrastructure management.
Reply
Leave a Reply. |
Archives
March 2021
Topics
All
|