Unit 3: Special Trees and Hashing

University:
Boston University
Course:
CAS CS 210 | Computer Systems
Academic year:

2021
Views:

0

Pages:

73
Author:

customer-7716562

Department of Computer Science and Engineering Course Category : PROGRAM CORE Slot No. : S4&S5 ABOUT THE COURSE UNIT III SPECIAL TREES AND HASHING  AVL Tree  B Tree  Trie  Hashing  Separate Chaining  Open Addressing  Linear Probing & Quadratic Probing  Double Hashing & Rehashing Department of Computer Science and Engineering 2 AVL Tree • An AVL tree (named after inventors Adelson-Velsky and Landis) is a self-balancing binary search tree • AVL Tree can be defined as height balanced binary search tree in which each node is associated with a balance factor. • It is calculated by subtracting the height of its right sub-tree from that of its left sub-tree. Balance Factor (k) = height (left(k)) - height (right(k)) Department of Computer Science and Engineering 3 • In AVL tree,Balance factor of every node is either 0 or 1 or 1. • If balance factor of any node is 1, it means that the left subtree is one level higher than the right sub-tree. • If balance factor of any node is 0, it means that the left subtree and right sub-tree contain equal height. • If balance factor of any node is -1, it means that the left subtree is one level lower than the right sub-tree. Department of Computer Science and Engineering 4 Department of Computer Science and Engineering 5 Department of Computer Science and Engineering 6 AVL Tree Operations Like BST Operations, commonly performed operations on AVL tree are1.Search Operation 2.Insertion Operation 3.Deletion Operation • After performing any operation on AVL tree, the balance factor of each node is checked. Department of Computer Science and Engineering 7 AVL Tree Rotations 1.Left Rotation (LL Rotation) – Right child to Right sub tree 2.Right Rotation (RR Rotation) – left child to left subtree 3.Left-Right Rotation (LR Rotation)- right child to left subtree 4.Right-Left Rotation (RL Rotation) – left child to right subtree Department of Computer Science and Engineering 8 LL Rotation 9 Department of Computer Science and Engineering RR Rotation Department of Computer Science and Engineering 10 Department of Computer Science and Engineering 11 Department of Computer Science and Engineering 12 Insertion in AVL Tree To insert an element in the AVL tree, follow the following steps• Insert the element in the AVL tree in the same way the insertion is performed in BST. • After insertion, check the balance factor of each node of the resulting tree. Department of Computer Science and Engineering 13 Now, following two cases are possibleCase-01:  After the insertion, the balance factor of each node is either 0 or 1 or 1. In this case, the tree is considered to be balanced. Conclude the operation. Insert the next element if any. Case-02:  After the insertion, the balance factor of at least one node is not 0 or 1 or -1. In this case, the tree is considered to be imbalanced. Perform the suitable rotation to balance the tree. After the tree is balanced, insert the next element if any. Department of Computer Science and Engineering 14 • Construct AVL Tree for the following sequence of numbers• 50 , 20 , 60 , 10 , 8 , 15 , 32 , 46 , 11 , 48 Step-01: Insert 50 Department of Computer Science and Engineering 15 • Step-02: Insert 20 Step-03: Insert 60 Department of Computer Science and Engineering 16 • Step-04: Insert 10 • Step-05: Insert 8 Department of Computer Science and Engineering 17 • Step-05: Insert 8 Department of Computer Science and Engineering 18 • Step-06: Insert 15 Department of Computer Science and Engineering 19 • Step-07: Insert 32 • Step-08: Insert 46 Department of Computer Science and Engineering 20 • Step-09: Insert 11 Department of Computer Science and Engineering 21 • Step-10: Insert 48 Department of Computer Science and Engineering 22 Department of Computer Science and Engineering 23 AVL Deletion • Deleting a node from an AVL tree is similar to that in a binary search tree. • Deletion also may disturb the balance factor of an AVL tree and therefore the tree needs to be rebalanced in order to maintain the AVLness. • For this purpose, we need to perform rotations Department of Computer Science and Engineering 24 Delete 30 25 Department of Computer Science and Engineering 26 Pros and cons Pros of AVL Trees • Faster Search Operations faster search operations than their counterparts such as red-black trees • Balancing Capabilities The longer it takes for a tree to be balanced, the longer the search will take. Cons of AVL Trees • Slow Inserts and Deletes If it is slightly unbalanced it can severely impact the amount of time that it takes to perform inserts and deletes • Fast Updating Systems They work much better with systems that are rarely updated, giving the system time to acquire all of the information that it needs to perform at its best. Department of Computer Science and Engineering 27 B - Tree • In search trees like binary search tree, AVL Tree, Red-Black tree, etc., every node contains only one value (key) and a maximum of two children. • But there is a special type of search tree called B-Tree in which a node contains more than one value (key) and more than two children. • B-Tree is a self-balanced search tree in which every node contains multiple keys and has more than two children. Department of Computer Science and Engineering 28 PROPERTIES OF B TREE • B-Tree of Order m has the following properties... Property 1 - All leaf nodes must be at same level. Property 2 - All nodes except root must have at least [m/2]1 keys and maximum of m-1 keys. Property 3 - All non leaf nodes except root (i.e. all internal nodes) must have at least m/2 children. Property 4 - If the root node is a non leaf node, then it must have atleast 2 children. Property 5 - A non leaf node with n-1 keys must have n number of children. Property 6 - All the key values in a node must be in Ascending Order. Department of Computer Science and Engineering 29 Department of Computer Science and Engineering 30 Operations on a B-Tree The following operations are performed on a B-Tree... Search Insertion Deletion Department of Computer Science and Engineering 31 Search Operation in B-Tree • Step 1 - Read the search element from the user. • Step 2 - Compare the search element with first key value of root node in the tree. • Step 3 - If both are matched, then display "Given node is found!!!" and terminate the function • Step 4 - If both are not matched, then check whether search element is smaller or larger than that key value. • Step 5 - If search element is smaller, then continue the search process in left subtree. • Step 6 - If search element is larger, then compare the search element with next key value in the same node and repeate steps 3, 4, 5 and 6 until we find the exact match or until the search element is compared with last key value in the leaf node. • Step 7 - If the last key value in the leaf node is also not matched then display "Element is not found" and terminate the function. Department of Computer Science and Engineering 32 Insertion Operation in B-Tree • Step 1 - Check whether tree is Empty. • Step 2 - If tree is Empty, then create a new node with new key value and insert it into the tree as a root node. • Step 3 - If tree is Not Empty, then find the suitable leaf node to which the new key value is added using Binary Search Tree logic. • Step 4 - If that leaf node has empty position, add the new key value to that leaf node in ascending order of key value within the node. • Step 5 - If that leaf node is already full, split that leaf node by sending middle value to its parent node. Repeat the same until the sending value is fixed into a node. • Step 6 - If the spilting is performed at root node then the middle value becomes new root node for the tree and the height of the tree is increased by one. Department of Computer Science and Engineering 33 • Example • Construct a B-Tree of Order 3 by inserting values 1,2,3,4,5,6,7,8,9,10 Department of Computer Science and Engineering 34 Department of Computer Science and Engineering 35 Department of Computer Science and Engineering 36 Department of Computer Science and Engineering 37 Department of Computer Science and Engineering 38 Department of Computer Science and Engineering 39 40 Department of Computer Science and Engineering Department of Computer Science and Engineering 41 Department of Computer Science and Engineering 42 Delete Operation • The delete operation has more rules than insert and search operations. The following algorithm applies: • Run the search operation and find the target key in the nodes • Three conditions applied based on the location of the target key, as explained in the following sections Department of Computer Science and Engineering 43 If the target key is in the leaf node  Target is in the leaf node, more than min keys.  Deleting this will not violate the property of B Tree  Target is in leaf node, it has min key nodes  Deleting this will violate the property of B Tree  Target node can borrow key from immediate left node, or immediate right node (sibling)  The sibling will say yes if it has more than minimum number of keys  The key will be borrowed from the parent node, the max value will be transferred to a parent, the max value of the parent node will be transferred to the target node, and remove the target value Department of Computer Science and Engineering 44 Target is in the leaf node, but no siblings have more than min number of keys  Search for key  Merge with siblings and the minimum of parent nodes  Total keys will be now more than min  The target key will be replaced with the minimum of a parent node Department of Computer Science and Engineering 45 If the target key is in an internal node • Either choose, in- order predecessor or in-order successor • In case the of in-order predecessor, the maximum key from its left subtree will be selected • In case of in-order successor, the minimum key from its right subtree will be selected • If the target key’s in-order predecessor has more than the min keys, only then it can replace the target key with the max of the in-order predecessor • If the target key’s in-order predecessor does not have more than min keys, look for in-order successor’s minimum key. • If the target key’s in-order predecessor and successor both have less than min keys, then merge the predecessor and successor. Department of Computer Science and Engineering 46 If the target key is in a root node • Replace with the maximum element of the in-order predecessor subtree • If, after deletion, the target has less than min keys, then the target node will borrow max value from its sibling via sibling’s parent. • The max value of the parent will be taken by a target, but with the nodes of the max value of the sibling. Department of Computer Science and Engineering 47 Example: Department of Computer Science and Engineering 48 Delete H • Since H is in a leaf and the leaf has more than the minimum number of keys, this is easy. We move the I over where the H had been. This gives: Department of Computer Science and Engineering 49 Delete R • Since R is not in a leaf, we find its successor (the next item in ascending order), which happens to be S, and move S up to replace the R. • Department of Computer Science and Engineering 50 Delete P • Although P is in a leaf, this leaf does not have an extra key; the deletion results in a node with only one key, which is not acceptable for a B-tree of order 5. • If the sibling node to the immediate left or right has an extra key, we can then borrow a key from the parent and move a key up from this sibling. • In our specific case, the sibling to the right has an extra key. So, the successor of P, which is S, is moved down from the parent, and the T is moved up. Department of Computer Science and Engineering 51 Department of Computer Science and Engineering 52 Delete D • Although D is in a leaf, the leaf has no extra keys, nor do the siblings to the immediate right or left. • In such a case the leaf has to be combined with one of these two siblings. This includes moving down the parent's key that was between those of these two leaves. • In our example, let's combine the leaf containing E with the leaf containing A B. We also move down the C. Department of Computer Science and Engineering 53 Department of Computer Science and Engineering 54 Trie • Trie data structure is a tree-based data structure used for storing collections of strings. • The word trie comes from the word reTRIEval which means to find or get something back. • If two strings have a common prefix then they will have the same ancestor in the trie. • In a trie data structure, we can store a large number of strings and can do search operations on it in an efficient way. • A trie can be used to sort a collection of strings alphabetically as well as search whether a string with a given prefix is present in the trie or not(prefix based searching) • A dictionary can be implemented efficiently with the help of a trie data structure. • Also known as Prefix Tree or Digital Tree Department of Computer Science and Engineering 55 Advantages of Trie over a hash table • A trie data structure can be used to implement a wide range of features that can't be implemented with a hash table. For example, Prefix-based searching can't be done with a hash table. • There won't be any collisions hence making the worst performance better than a hash table that is not implemented properly. • No need for hash functions. • Lookup time for a string in trie is O(k) where k = length of the word. • It can take even less than O(k) time when the word is not there in a trie. Department of Computer Science and Engineering 56 Properties of the Trie for a set of the string: • The root node of the trie always represents the null node. • Each child of nodes is sorted alphabetically. • Each node can have a maximum of 26 children (A to Z). • Each node (except the root) can store one letter of the alphabet. Applications of tries • Tries has an ability to insert, delete or search for the entries. Hence they are used in building dictionaries such as entries for telephone numbers, English words. • Tries are also used in spell-checking softwares. Department of Computer Science and Engineering 57 • The diagram below depicts a trie representation for the bell, bear, bore, bat, ball, stop, stock, and stack. Department of Computer Science and Engineering 58 struct TrieNode { struct TrieNode* children[ALPHABET_SIZE]; // This will keep track of number of strings that are // stored in the Trie from root node to any Trie node. int wordCount = 0; }; Department of Computer Science and Engineering 59 Insertion in Trie Data Structure • The root node was created. Every index of the childNode pointer array is NULL. The current node initially will be the root node. The first character of the input string is a. In the root node, we will check whether the a-a th index of the childNode array is NULL or not. As the a-a th index of the childNode array is NULL. We make a new TrieNode with help of the constructor defined in the structure of the TrieNode. We will point the a-a th index of the childNode pointer array of the root node to the new node created. We will make the new node created as the current node and proceed to the next step. As string a is not the end of the string tea we will not increment the wordcount variable for the current node or the new node created in step 1. • In step 2 we will follow the same steps as in step 1. The second character of the input string is n. In the current node, we will check whether the n-a th index of the NULL or not. As n-a th index of the childNode array is NULL we will again create a new node. We will point the n-a th index of the current node to the newly created node. We will make the new node as current and proceed to the next step. As the string n is not the end of the string tea we will not increment the wordcount value for this node. • In step 3 we will move to the third character of the input string, i.e d. We will check whether the d-a th index or the 0th index of the childNode pointer array is null or not. As it is NULL we will make a new node and do the same steps as in steps 1 and 2. We will make the new node the current node. However, as the string tea is the end of the string tea we will increment the wordcount value for this node. Department of Computer Science and Engineering 60 Insertion in Trie Data Structure Department of Computer Science and Engineering 61 Insertion in Trie Data Structure • Initially, the current node is the root node. The first character of the input string is a. As the a-a th index of the childNode pointer array is not NULL we will not create a new node. The current node is shifted from the root node to the node pointed by a-a th index of the childNode pointer array of the root node • Now we check for the second character of the input string,i.e n. As the n-a th index of the current node is also not null we shift the current node to the node pointed by n-a th index of the current node. • Now we check for the last character of the input string, i.e t. As the t-a th index of the current node is NULL we make a new node and follow the same steps as discussed above. We increment the wordcount variable for this node as this character is the last character of the input string. Department of Computer Science and Engineering 62 Department of Computer Science and Engineering 63 struct TrieNode* createNode() { struct TrieNode* newNode = (struct TrieNode*)malloc(sizeof(struct TrieNode)); if (newNode) { int i; for (i = 0; i < ALPHABET_SIZE; i++) { newNode->children[i] = NULL; } newNode-> wordCount = false; } return newNode; } Department of Computer Science and Engineering 64 void insert(struct TrieNode *root, const char *key) { { //initialize the currentNode pointer with the root node TrieNode *currentNode = root; //Store the length of the key string int length = key.size(); //iterate across the length of the string for (int i = 0; i < length; i++) { //Check X-'a' th index is NULL or not if (currentNode->children[key[i] - 'a'] == NULL) { //If null make a new node //Point the X-'a' th index of current node to the new node currentNode->children[key[i] - 'a'] = createNode(); } //Move the current node pointer to the newly created node. currentNode = currentNode->children[key[i] - 'a']; } //Increment the wordEndCnt for the last currentNode pointer as it will point //the string that is the end of the string key. currentNode-> wordCount++; //return the updated root node return root; Department of Computer Science and Engineering }x` 65 Searching in Trie Data Structure • The search operation in a Trie data structure is similar to that of an Insert operation. • The only difference in a Search operation is that whenever we find a node having X-a th index of childNode pointer array of the current node as NULL we return false instead of making a new node. • Here X can be any character of the query string. • We return True only when we process the entire query string without coming across a null pointer and wordEndCnt for the last node is greater than 0. 66 Searching in Trie Data Structure • Initially, the current node is the root node. The first character of the query string is d. We check whether the d-a th index of the childNode pointer array of the current node is NULL or not. As it is not null we move the current node pointer to the node pointed by d-a th index of the current node which is the root node in step 1. • Now we check for the second character of the query string i.e a. As the a-a th index of the current node is also not NULL. We move the current node pointer to the node pointed by a-a th index of the current node. • Then, we process the last character of the query string, i.e d. As the d-a index of the current node is not equal to null we move the current node pointer to the node pointed by the d-a th index of the childNode pointer array of the current node. • Finally, we check if the wordcount for the current node is greater than 0 or not. If the wordcount is greater than 0 which is the case for the query string dad, we return true. Otherwise, we return false. Department of Computer Science and Engineering 67 Searching in Trie Data Structure bool search_key(TrieNode *root, string &queryString) { //Initialize the currentNode pointer with the root node TrieNode *currentNode = root; //Store the length of the query string int length = queryString.size(); for (int i = 0; i < length; i++) { //Check if the X-'a' th index is NULL or not if (currentNode->childNode[queryString[i] - 'a'] == NULL) { //If null then the query string is not present in the Trie //return false return false; } //If not NULL //Move the currentNode pointer to the node pointed by X-'a' th index of the //current node currentNode = currentNode->childNode[queryString[i] - 'a']; } //If currentNode pointer is not NULL //and wordEndCnt for the currentNode pointer //is greater than 0 then return true else //return false return currentNode != NULL && currentNode->wordEndCnt > 0; } 68 Deleting in Trie Data Structure The following are possible conditions when deleting key from trie, • Key may not be there in trie. Delete operation should not modify trie. • Key present as unique key (no part of key contains another key (prefix), nor the key itself is prefix of another key in trie). Delete all the nodes. • Key is prefix key of another long key in trie. Unmark the leaf node. • Key present in trie, having atleast one other key as prefix key. Delete nodes from end of key until first leaf node of longest prefix key. Department of Computer Science and Engineering 69 Deleting in Trie Data Structure int hasChildren(struct Trie* curr) { for (int i = 0; i < CHAR_SIZE; i++) { if (curr->character[i]) { return 1; // child found } } return 0; } // Recursive function to delete a string from a Trie int deletion(struct Trie **curr, char* str) { // return 0 if Trie is empty if (*curr == NULL) { return 0; } // if the end of the string is not reached if (*str) { // recur for the node corresponding to the next character in // the string and if it returns 1, delete the current node // (if it is non-leaf) 70 Deleting in Trie Data Structure if (*curr != NULL && (*curr)->character[*str - 'a'] != NULL && deletion(&((*curr)->character[*str - 'a']), str + 1) && (*curr)->isLeaf == 0) { if (!hasChildren(*curr)) { free(*curr); (*curr) = NULL; return 1; } else { return 0; } } } have any children if (!hasChildren(*curr)) { free(*curr); // delete the current node (*curr) = NULL; return 1; // delete the non-leaf parent nodes } // if the current node is a leaf node and has children else { // mark the current node as a non-leaf node (DON'T DELETE IT) (*curr)->isLeaf = 0; return 0; // don't delete its parent nodes } } // if the end of the string is reached if (*str == '\0' && (*curr)->isLeaf) return 0; { } // if the current node is a leaf node and doesn't Department of Computer Science and Engineering 71 Deleting in Trie Data Structure Performance of Trie The time complexity of a Trie data structure for insertion/deletion/search operation is just O(n), where n is key length. The space complexity of a Trie data structure is O(N × M × C), where N is the total number of strings, M is the maximum length of the string, and C is the alphabet’s size Applications of Trie ⮚ As a replacement for other data structures ⮚ Autocomplete / Dictionary ⮚ Spell checker ⮚ Lexicographic sorting of a set of keys ⮚ Longest prefix matching Department of Computer Science and Engineering 72 Hashing • Hashing is one of the searching techniques that uses a constant time. The time complexity in hashing is O(1) • The hash table is an associative data structure that stores data as associated keys. An array format is used to store hash table data, where each value is assigned its unique index. By knowing the index of the desired data, we can access it very quickly. • As a result, inserting and searching data is very fast, regardless of data size. In a Hash Table, elements are stored in an array, and an index is generated using hashing techniques in a data structure. 73

Unit 3: Special Trees and Hashing

Related Documents

Recommended Documents

Description

Related Documents

Free up your schedule!

Take 5 seconds to unlock