CC104 Finals - Trees and Binary Search Trees PDF

**WEEK 13** **Trees** §  root is on the top and the leaves are at the bottom §  displays data items in a hierarchical structure §  organize information in database systems §  also work as ordered array and a linked list §  A tree is composed of nodes connected by edges or lines   **Basic Ter...

**WEEK 13** **Trees** §  root is on the top and the leaves are at the bottom §  displays data items in a hierarchical structure §  organize information in database systems §  also work as ordered array and a linked list §  A tree is composed of nodes connected by edges or lines   **Basic Terminologies**  §  Nodes §  Root Node §  Edges / lines / paths §  Leaf nodes §  Internal Nodes / Child Nodes §  Subtree §  Visiting §  Traversing §  Levels §  Degree §  Depth of the tree §  Keys    **Exercise** ** **Given the tree below, find the following: 1\. Root node 2\. Depth of the tree 3\. Nodes in level 4 4\. Degree of D 5\. Child/Children of Z 6\. Total Nodes in the tree 7\. Parent of F 8\. Leaf Nodes 9\. Child nodes 10\. Maximum degree of the tree    **Binary Tree** Every node in a tree can have at most two children Left subtree Right subtree Two applications of binary tree Binary expression tree Binary search tree   Binary Search Tree D:\\Annual\\Martin\\Inventory\\January.dat. Hierarchical file structure in a computer systems one of the common trees Hierarchical file structure is not a binary tree Binary search trees are trees such that any node has a key which is no more than the key in its right child node and no less than the key in its left child node **Node Class** **class Node{** **int iData; //data used as key value** **float fData; //other data** **node leftChild; //node's left child** **node rightChild; //node's right child** **public void displayNode(){}{** **class Node{** **person p1; //reference to person object** **node leftChild; //node's left child** **node rightChild; //node's right child}** **class Person{** **int iData;** **float fData;}** **Tree Class** **class Tree{** **private Node root; //the only data field in Tree** **public void find(int key){}** **public void insert(int id, double dd){}** **public void delete(int id){}** **//you may include other methods}** **Finding a Node** **public Node find(int key){** **Node current = root** **Operations on Binary Tree** **Binary Expression Tree** a binary tree used in representing arithmetic expression Specifically the combinations of operators, operands, and order of evaluation   **Constructing an Expression Tree** Read the symbols one at a time. If the symbol is an operand: ü  Create a one-node tree. ü  Push a pointer to the node into the stack. If the symbol is an operator:   ü  3.1 Pop two pointers from stack. These pointers represent the address of the root nodes of two trees, T1 and T2. ü  3.2 Form a new tree whose root is the operator and whose left and right children are T1 and T2, respectively. ü  3.3 Push the pointer to the new tree into the stack.   Repeat steps 1 thru 3 until the last symbol has been read and processed.   **Binary Expression Tree**  Example: AB+CDE+/  **Exercise** Create a binary expression tree for the infix notation given below   1\. ( ( A + B ) - ( C / D ) ) + ( E \* ( F / D ) ) 2\. A + ( B \* ( C -- D ) ) -- ( E -- F \* ( G + H ) )   **Binary Tree Traversal** to visit all the nodes of the tree in order not commonly used as finding, inserting, deleting nodes useful in some circumstances and simpler than deleting of nodes   1\.       Inorder 2\.       Preorder 3\.       Postorder     **Inorder Traversal** 1\. If the node has a left subtree: Traverse the left subtree in inorder (recursive call). Once completed,  proceed to step 2. Otherwise, proceed to step 2. 2\. Read the root node. 3\. If the node has a right subtree: Traverse the right subtree in inorder (recursive call).   The nodes of the tree will be visited in the order: A B C D E F G **Preorder Traversal** 1\. Read the root node. 2\. If the node has a left subtree: Traverse the left subtree in preorder (recursive call). Once completed, proceed to step 3. Otherwise, proceed to step 3. 3\. If the node has a right subtree: Traverse the right subtree in preorder (recursive call).    **Postorder Traversal** 1\. If the node has a left subtree: Traverse the left subtree in postorder (recursive call). Once completed, proceed to step 2. Otherwise, proceed to step 2. 2\. If the node has a right subtree: Traverse the right subtree in postorder (recursive call). Once completed, proceed to step 3. Otherwise, proceed to step 3. 3\. Read the root node.   Generating the given expression tree into the three traversal methods.    **Inorder Sequence**  **Preorder Traversal**    **Postorder Traversal**   **Inorder Traversal Code** private void inOrder(node localRoot){ if(localRoot != null){ inOrder(localRoot.leftChild); localRoot.displayNode(); inOrder(localRoot.rightChild);}} **WEEK 14** **Balanced / unbalanced tree** ·         Balanced tree - equal items on each subtree of node to minimize the maximum path from the root to any leaf node §  Height-balanced - left and right subtree height of each node is within 1      ·         Unbalanced tree - root has more left descendants than its right descendants or viceversa ·         Self-balancing tree - attempt to keep its height, the number of levels of nodes underneath the root, as small as possible ·         Tree rotation - changes the structure of the tree without intervening any element in the tree especially its order  ** ** **AVL Tree** ·         named after G.M. Adelso-Velsky and E.M. Landis ·         can also be called as height balanced ·         Balance factor - done by right subtree less the height of its left subtree ·         Insertion - as it is inserting in an unbalanced BST and retraces the one's steps toward the root ·         Deletion -- same with BST ·         Search - no provisions will be taken and will not change the structure of the tree    an AVL tree because it shows that each left subtree has a height of 1 greater than each right subtree    not an AVL tree for the subtree of E has the height of 4 and the subtree of I has the height of 2   **Red-Black Tree** ·         a special type of BST that organizes pieces of comparable data such as numbers ·         two characteristics that this tree comprises o   The nodes are colored o   During insertion and deletion, rules are followed that preserve various arrangements of these colors **Red-Black Rules** ·         Every node is red or black. ·         The root is always black.  If a node is red, its children must be black. ·         Both children of every red node are black. ·         Every path from the root to a leaf, or to a null child, must contain the same number of black nodes. ·         Things should be done when tree is not balanced or the color rules are violated ·         Change the colors of the nodes.  Perform rotations.   **Red-Black Tree** ·         Rotations are designed to: o   Raise some nodes and lower others to help balance the tree o   Ensure that the characteristics of a binary search tree are not violated ·         To maintain the properties of red-black trees when inserting a node o   Enter a new element on a tree as a red leaf node o   Maintain the root as a black node o   When moving down the path to look on where to insert, update the colors of the nodes when you find a black parent with two red children o   Inserting a node at the bottom may result in two successive red nodes; employ rotation to reorder the coloring of the tree  **Splay Trees** ·         elements in the tree that have been accessed recently can be accessed very quickly ·         invented by Daniel Sleator and Robert Tarjan ·         it performs an operation called ―splaying‖ also know as rotation **Advantages** ü  Faster performance ü  Easier implementation ü  Efficient with identical keys   **Splay Trees** ** ** Three splay steps: Zig step           Zig-zig step                                        Zig-zag step   **2-3-4 Trees** **                          ** ·         Multiway tree - allowing having more data items and children per node ·         2-3-4 tree -- a multiway tree that can have up to 4 children and 3 data items per node ·         Possible arrangement for non-leaf nodes o   A node with one data item always has two children o   A node with two data items always has three children o   A node with three data items always has four children **Principle** ·         All children in the subtree rooted at child 0 have key values less than key 0 ·         All children in the subtree rooted at child 1 have key values greater than 0 but less than key 2 ·         All children in the subtree rooted at child 2 have key values greater than key 1 but less than key 2  All children in the subtree rooted at child 3 have key values greater than key 2  Find key value 64 Insert Operations    **Splitting a node** ·         A new, empty node is created.  It's a sibling of the node being split, and is placed to its right. ·         Data item C is moved into a new node. ·         Data item B is moved into the parent of the node being split. ·         Data item A remains where it is. ·     The rightmost two children are disconnected from the node being split and connected to the new node   **Split a root** ·         A new node is created that becomes the new root and the parent of the node being split. ·         A second new node is created that becomes a sibling of the node being split. ·         Data item C is moved into the new sibling. ·         Data item B is moved into the new root. ·         Data item A remains where it is. ·         The two rightmost children of the node being split are disconnected from it and connected to the new right---hand node.  **B-Trees** ·         ―B‖ -- balanced, Boieng, Bayer ·         keeps data in a sorted order ·         Database and filesystems -- applications that uses this data structure ·         require that all leaf nodes are at the same depth ·     Search, insert, delete are operations that can be performed  overflowed - adding on a full leaf node ·         To make nodes in order o   Half the leaf node making it the left child o   Pick the middle and place it on the root o   Create a new node placing the remaining values   **Exercise** From the tree below, insert the following values: ·     67 ·         54 ·         39      **Heap**  **WEEK 15** **Shell Sort** **·         does not sort the element itself but increases the efficiency of other sorting algorithms** **·         invented by Donald Shell in 1959** **·         extension of insertion sort  good for medium-sized arrays** **·         space between elements is known as increment and represented by letter h** **·         N-sorting** **o   n can be less than half the number of element** **o   n is reduced and the elements are sorted again until n is equal to 1** **·         avoid the sequence constructed with the powers of 2**  ** ** **Exercise:** **Given a series of elements below, generate its 5-sorted then 3-sorted** **13, 14, 94, 33, 82, 25, 59, 94, 65, 23, 45, 27, 73, 25, 39, 10** ** ** **Shellsort pseudocode** **Shell Sort (Sorting the array A\[size\])   ** **Determine the number of segments by dividing the number of cells by two.   ** **While the number of segments are greater than zero   ** **{** **For each segment, we do an Insertion** **Sort. (think of how to write the loops** **here efficiently\... )** **Divide the number of segments by two.   ** **}** ** ** **Partitioning** ** ** **·         divided into two groups: all items with a key value higher than the specified amount and all items lower than the key value** **·         horizontal line represents the pivot value; this determines which of the two groups an item is placed**  **Quick Sort** **·         operates by partitioning an array into two subarrays and then calling itself to quicksort each of these subarrays** ** ** **Basic steps** **·         Partition the array or subarray into left (smaller keys) and right (larger keys) groups.** **·         Call ourselves to sort the left group.** **·         Call ourselves again to sort the right group** **Pivot value to use** **·         Your pivot value should be the key value of an actual data item, which you can call as pivot.** **·         You can pick a data item more or less at random.  For simplicity, you can always pick the one on the right end of the subarray being partitioned.** **·         After the partition, if the pivot is inserted at the boundary between left and right subarrays, it will be in its final sorted position.**  ** ** ** ** **Median-of-Three** **·         ideal pivot choice but the process that it requires is not practical as it would take more time than the sort itself** **·         find the median of the first, last, and middle elements of the array and use this as the pivot**  **·         guaranteed that the element at the left end of the subarray is less than or equal to the pivot, and the element at the right end is greater than or equal to the pivot** **·         process of partition need not to examine these elements again** **WEEK 16** **Hash Table** **·         another data structure used to handle large amount of data that offers fast insertion and searching  fast searching and deleting** **·         based on arrays, and arrays are difficult to expand one they've been created** **·         no convenient way to visit the items in a hash table in any kind of order**  ** Dictionary** **·         English-language dictionary is a typical example of database that can be efficiently handled with a hash table** **·         computer-language compiler - similar widely used application for hash tables** ** ** **Converting Words to Numbers** **·         computers use various schemes for representing individual characters as numbers** **·         ASCII code - runs from 0 to 255 to accommodate capitals, punctuation, and so on** **·         How do you combine digits from individual letters into a number that represents an entire word?** **o   Sorts of approaches** ** ** **Add the Digits** **C = 3 A = 1 T = 20 S = 19** **Add them:** **3 + 1 + 20 + 19 =43** ** ** **a would be coded as** **0 + 0 + 0 + 0 + 0 + 0 + 0 + 0 + 0 + 1 = 1** ** ** **zzzzzzzzzz (ten Zs)** ** 26 + 26 + 26 + 26 +26 + 26 +26 + 26 + 26 + 26 = 260** ** ** **Multiply by Powers** **·         another approach of mapping words to numbers** **o   7,546 really means:** **§  7\*1000 + 5\*100 + 4\*10 + 6\*1** ** ** **·         Or writing the multipliers as powers of** **o   10: 7\*103 + 5\*102 + 4\*101 + 6\*100** ** ** **·         generates a unique number for every potential word** ** ** **Hashing** **·          use modulo operator (%), which finds the remainder when one number is divided by another** **·     smallNumber = largeNumber % smallRange;** ** **  ** ** **·         hash function - hashes (converts) a number in a large range into a number in a smaller range** **·         An array into which data is inserted using a hash function is called a hash table** **·         hugeNumber = ch0\*279 + ch0\*278 + ch0\*277 + ch0\*276 + ch0\*275 ch0\*274 + ch0\*273 + ch0\*272 + ch0\*271 + ch0\*270** **o   arraySize = numberWords \* 2; arrayIndex = hugeNumber % arraySize** ** ** **Collisions** **·         To insert the word melioration into the array, hash the word to obtain its index number, but find that the cell at that number is already occupied by the word demystify, which happens to hash exact same number (for a certain size array).** **·         Open addressing - search the array in some systematic way for an empty cell, and insert the new item there  linear probing, quadratic probing, and double hashing** **·         Separate chaining - new item is simply inserted in the list at that index** ** ** **Linear Probing**  ** ** ** Quadratic Probing** **·         load factor - ratio of the number of items in a table, to the table's size** **·         loadFactor = nItems / arraySize;** **·         Quadratic probing is an attempt to keep clusters from forming**  ** ** ** Problem with Quadratic Probes** **·         A quadratic probe eliminates the clustering problem seen with the linear probe called as primary clustering** **·         Secondary clustering - each additional item with a key that hashes to its maximum will require a longer probe** **Double Hashing** **·         Sometimes called as rehashing** **·         The secondary hash function must have certain characteristics:** **o    It must not be the same as the primary hash function.** **o   It must never output a 0 (otherwise there would be no step; every probe would land on the same cell, and the algorithm would go into an endless loop.)** **·         following form work well** **o   stepSize = constant -- (key % constant);  stepSize = 5 -- (key & 5)** ** ** ** ** ** Separate Chaining** **·          to install a linked list at each index in the hash table**  **o    Deletion** **o    Table Size** **o    Buckets** ** ** **WEEK 17** **Graphs** **·         one of the most versatile structures used in computer programming** **·         have shape dictated by a physical problem** **·     nodes are called vertices (the singular is vertex)** ** **  **·         circles represent freeway interchanges and straight lines connecting the circles represent freeways segments** **·         the circles are the vertices and the lines are the edges** **·     Adjacency** **o    if they are connected by a single edge** **o    Neighbors** **·         Path** **o   a sequence of edges** **o   Connected Graphs** **·         Directed and Weighted Graphs** **o   Non-directed graphs - edges don't have a direction** **o   Directed graphs - model situations in which can go in only one direction along an edge** **o   Weight - a number that can represent the physical distance between two vertices** **·         Historical Information** ** **  ** ** **·         Adjacency Matrix** **o   two-dimensional array in which the elements indicate whether an edge is present between two vertices** ** ** ** ** **·         Adjacency List** **o   refers to a linked list of a kind examined in the discussion of "recursion"** ** **  ** ** **·         Adding Vertices and Edges to a Graph** **o    Creation of vertex** **§  vertexList\[nVerts++\] = new Vertex('F);** ** ** **o    Inserting the edge** **§  addjMat\[1\]\[3\] = 1; addjMat\[3\]\[1\] = 1;** ** ** **Depth-First Search**  ** ** **·         Rule 1:  If possible, visit an adjacent unvisited vertex, mark it, and push it on the stack.** **·         Rule 2:  If you can't follow Rule 1, then, if possible, pop vertex off the stack.** **·         Rule 3:  If you can't follow Rule 1 and Rule 2, it's finished.** ** ** ** **