CSC 1061 Week 13 More Trees PDF

CSC 1061 MORE TREES  OBJECTIVES AGENDA: WEEK 13 Follow and explain tree-based 1. Review Binary Tree algorithms 2. Review Binary Search Tree Explain the traversal algorithms for the common binary tre...

CSC 1061 MORE TREES  OBJECTIVES AGENDA: WEEK 13 Follow and explain tree-based 1. Review Binary Tree algorithms 2. Review Binary Search Tree Explain the traversal algorithms for the common binary tree traversals 3. Function as Arguments (in-order, pre-order, post-order, 4. Binary Tree as Array backwards in-order) 5. Other Trees List the rules for a binary search 1. Full Tree tree and determine whether a tree satisfies these rules 2. Complete Tree Carry out searches, insertions on 3. Heap a binary search tree and 4. B-Trees implement these algorithms using 6. TODO & Resources for Help the binary tree class BINARY TREE TRAVERSALS A binary tree is a data structure in which each parent node can have at most two children. Label the traversal name that matches the ordered set 1) In-Order a) 4, 5, 2, 3, 1 2) Pre-Order b) 4, 2, 5, 1, 3 3) Post-Order c) 3, 1, 5, 2, 4 4) Backward In-Order d) 1, 2, 4, 5, 3 BINARY SEARCH TREE (PROGRAMIZ) Binary search tree is a data structure that quickly allows us to maintain a sorted list. The properties that separate a binary search tree from a regular binary tree is All nodes of left subtree are less than or equal to the parent node All nodes of right subtree are greater than the parent node PASSING A FUNCTION AS ARGUMENT Templates have no knowledge about any special processing for one data type To keep templates generic, but still have them process specific tasks for a particular data type, a function can take another function as the argument. To pass a function as an argument, you must specify that the argument is a function in the prototype and function header with the full function signature: returnType placeHolderName(dataType, …) Only the function name is passed as the argument value, but it MUST match the signature of the function being passed in. BINARY TREE TRAVERSAL: GENERIC PROCESS template void BinTree::inOrder(void process(T)){ Note: process is a inOrder(process, root); placeholder and } doesn't really exist. template void BinTree::inOrder(void process(T), BinNode* cursor){ if(cursor != nullptr) { // checking against stopping case inOrder(process, cursor->left); // Left recursive call process(cursor->data); // Function call: execute process inOrder(process, cursor->right);// Right recursive call } } BINARY TREES AS ARRAYS The advantage of having a binary tree in an array is that an array has direct random access. Every node can be accessed directly with an index and every parent and child node is directly accessable based on the current node's index. The root node is at array BINARY TREES AS ARRAYS 0 1 2 3 4 5 6 7 8 9 10 11 12 10 5 12 3 7 11 16 6 12 Current node is at array[i]: its parent: array[(i - 1) / 2] left child: array[2 * i + 1] right child: array[2 * i + 2] Draw in the binNode highlighted in the array on the picture OTHER TYPES OF TREES Besides a Binary Search Tree, there are other types of trees: Full Trees Heaps​ Complete Trees B-Trees​ FULL BINARY TREE COMPLETE BINARY TREE A full tree is setup so that A complete tree has all levels every parent has either two filled ​except possibly the lowest or no children. one, which is filled from the left. HEAP (PROGRAMIZ) Heap (or Binary Heap) data structure is a complete binary tree that satisfies either the max heap or min heap property. complete binary tree 1. every level, except possibly the last, is filled 2. all the nodes are as far left as possible MAX HEAP PROPERTY MIN HEAP PROPERTY Each node is always greater Each node is always smaller than its child node/s and the than the child node/s and the key of the root node is the key of the root node is the largest among all other nodes smallest among all other nodes. HEAPIFY (PROGRAMIZ) Heapify is the process of creating a heap data structure from a binary tree. It is used to create a Min-Heap or a Max-Heap. Adding an element to the Heap is the process of: Re-heapification Upward Removing an element from the Heap is the process of: Re-heapification Downward B-TREE (PROGRAMIZ) B-tree is a special type of self-balancing search tree in which each node can contain more than one key and can have more than two children. It is a generalized form of the binary search tree. WHY B-TREE (PROGRAMIZ) The need for B-tree arose with the rise in the need for lesser time in accessing the physical storage media like a hard disk. The secondary storage devices are slower with a larger capacity. There was a need for such types of data structures that minimize the disk accesses. Other data structures such as a binary search tree, avl tree, red-black tree, etc can store only one key in one node. If you have to store a large number of keys, then the height of such trees becomes very large and the access time increases. However, B-tree can store many keys in a single node and can have multiple child nodes. This decreases the height significantly allowing faster disk accesses.  B-TREE PROPERTIES (PROGRAMIZ) 1. For each node, the keys are stored in increasing order. 2. In each node, there is a boolean value x.leaf which is true if the node is a leaf. 3. If MAX is the order of the tree, each internal node can contain at most MAX- 1 keys along with a pointer to each child. 4. Each node except root can have at most MAX children and at least MAX/2 children. 5. All leaves have the same depth (i.e. height-h of the tree). 6. The root has at least 2 children and contains a minimum of 1 key. B-TREE The idea is to combine the advantages of using dynamic memory and a static array. To search for a value, you will use the binary tree search to find the node with the range containing the value. Then the array inside the node can be searched using a standard array-searching algorithm (like a binary search.) A B-tree is typically used when manipulating a large, undetermined amount of data where values are constantly being added and deleted. A good example of when using a B-tree is appropriate is when implementing a relational database management system. POST-REVIEW Review the glossary terms and complete the matching question at the end. EARN YOUR PRE-WORK GRADE Post your weekly discussion question and research solution to D2L TODO Complete Week 13 Content Module in D2L to 100% WHAT'S COMING UP NEXT...WEEK 14  QUESTIONS | CLARIFICATIONS | HELP Student Office Hours: Schedule Meeting with Julie o By Appointment (both on-campus and remote via Zoom) o Drop-In Times Available (on-campus) Email: [email protected] RRCC On Campus Tutoring: https://www.rrcc.edu/learning- commons/tutoring 24/7 Online Tutoring: D2L > Content > Resources for Help