AVL Trees, B-Trees Dr. Nguyen Ho Man Rang Chapter 8 AVL Trees, B-Trees AVL Tree Concepts AVL Balance Data Structures and Algorithms AVL Tree Operations Multiway Trees B-Trees Dr. Nguyen Ho Man Rang Faculty of Computer Science and Engineering University of Technology, VNU-HCM 8.1 AVL Trees, B-Trees Outcomes Dr. Nguyen Ho Man Rang • L.1 - Depict the following concepts: binary tree, complete binary tree, balanced binary tree, AVL tree, multi-way tree, etc.2 - Describe the strorage structure for tree AVL Tree Concepts AVL Balance structures using pseudocode.3 - List necessary methods supplied for tree Operations structures, and describe them using pseudocode.
Multiway Trees B-Trees • L.4 - Identify the importance of “blanced” feature in tree structures and give examples to demonstate it.5 - Identiy cases in which AVL tree and B-tree are unblanced, and demonstrate methods to resolve all the cases step-by-step using figures.2 AVL Trees, B-Trees Outcomes Dr. Nguyen Ho Man Rang • L.6 - Implement binary tree and AVL tree using C/C++.7 - Use binary tree and AVL tree to solve problems in real-life, especially related to searching techniques. AVL Tree Concepts • L.8 - Analyze the complexity and develop AVL Balance AVL Tree experiment (program) to evaluate methods supplied for Operations tree structures.4 - Develop recursive implementations for B-Trees methods supplied for the following structures: list, tree, heap, searching, and graphs.2 - Analyze algorithms and use Big-O notation to characterize the computational complexity of algorithms composed by using the following control structures: sequence, branching, and iteration (not recursion).3 AVL Trees, B-Trees Contents Dr. Nguyen Ho Man Rang 1 AVL Tree Concepts 2 AVL Balance AVL Tree Concepts AVL Balance AVL Tree Operations 3 AVL Tree Operations Multiway Trees B-Trees 4 Multiway Trees 5 B-Trees 8.4 AVL Trees, B-Trees Dr.
Nguyen Ho Man Rang AVL Tree Concepts AVL Tree Concepts AVL Balance AVL Tree Operations Multiway Trees B-Trees 8.5 AVL Trees, B-Trees AVL Tree Dr. Nguyen Ho Man Rang Definition AVL Tree is: • A Binary Search Tree, AVL Tree Concepts • in which the heights of the left and right AVL Balance subtrees of the root differ by at most 1, and AVL Tree Operations • the left and right subtrees are again AVL Multiway Trees B-Trees trees.Adel’son-Vel’skii and E. AVL Tree is a Binary Search Tree that is balanced tree.6 AVL Trees, B-Trees AVL Tree Dr. Nguyen Ho Man Rang A binary tree is an AVL Tree if • Each node satisfies BST property: key of the node is greater than the key of each AVL Tree Concepts node in its left subtree and is smaller than AVL Balance AVL Tree or equals to the key of each node in its Operations Multiway Trees right subtree.
B-Trees • Each node satisfies balanced tree property: the difference between the heights of the left subtree and right subtree of the node does not exceed one.7 AVL Trees, B-Trees AVL Tree Dr. Nguyen Ho Man Rang Balance factor AVL Tree Concepts • left_higher (LH): HL = HR + 1 AVL Balance • equal_height (EH): HL = HR AVL Tree Operations Multiway Trees • right_higher (RH): HR = HL + 1 B-Trees (HL , HR : the heights of left and right subtrees) 8.8 AVL Trees, B-Trees AVL Trees Dr. Nguyen Ho Man Rang 8 8 8 8 5 5 10 5 10 AVL Tree Concepts 9 3 6 12 AVL Balance AVL Tree Operations 8 Multiway Trees B-Trees 5 10 3 6 9 1 4 5 7 8.9 AVL Trees, B-Trees Non-AVL Trees Dr. Nguyen Ho Man Rang 8 8 5 10 AVL Tree Concepts 3 9 12 AVL Balance AVL Tree Operations 8 8 Multiway Trees B-Trees 5 10 5 10 12 3 12 15 1 15 8.10 AVL Trees, B-Trees Why AVL Trees? Dr.
Nguyen Ho Man Rang • When data elements are inserted in a BST in sorted order: 1, 2, 3,. BST becomes a degenerate tree. Search operation takes O(n), which is AVL Tree Concepts AVL Balance inefficient. AVL Tree Operations Multiway Trees • It is possible that after a number of insert B-Trees and delete operations, a binary tree may become unbalanced and increase in height.
• AVL trees ensure that the complexity of search is O(log2 n).11 AVL Trees, B-Trees Dr. Nguyen Ho Man Rang AVL Tree Concepts AVL Balance AVL Balance AVL Tree Operations Multiway Trees B-Trees 8.12 AVL Trees, B-Trees Balancing Trees Dr. Nguyen Ho • When we insert a node into a tree or delete Man Rang a node from a tree, the resulting tree may be unbalanced. → rebalance the tree.
AVL Tree Concepts • Four unbalanced tree cases: AVL Balance AVL Tree • left of left: a subtree of a tree that is Operations Multiway Trees left high has also become left high; B-Trees • right of right: a subtree of a tree that is right high has also become right high; • right of left: a subtree of a tree that is left high has become right high; • left of right: a subtree of a tree that is right high has become left high; 8.13 AVL Trees, B-Trees Unbalanced tree cases Dr. Nguyen Ho Man Rang AVL Tree Concepts AVL Balance AVL Tree Operations Multiway Trees B-Trees (Source: Data Structures - A Pseudocode Approach with C++) 8.14 AVL Trees, B-Trees Unbalanced tree cases Dr. Nguyen Ho Man Rang AVL Tree Concepts AVL Balance AVL Tree Operations Multiway Trees B-Trees (Source: Data Structures - A Pseudocode Approach with C++) 8.15 AVL Trees, B-Trees Rotate Right Dr. Nguyen Ho Man Rang Algorithm rotateRight(ref root <pointer>) Exchanges pointers to rotate the tree right.
AVL Tree Concepts Pre: root is pointer to tree to be rotated AVL Balance Post: node rotated and root updated AVL Tree Operations Multiway Trees tempPtr = root->left B-Trees root->left = tempPtr->right tempPtr->right = root Return tempPtr End rotateRight 8.16 AVL Trees, B-Trees Rotate Right Dr. Nguyen Ho Man Rang AVL Tree Concepts AVL Balance AVL Tree Operations Multiway Trees B-Trees (Source: Data Structures - A Pseudocode Approach with C++) 8.17 AVL Trees, B-Trees Rotate Left Dr. Nguyen Ho Man Rang Algorithm rotateLeft(ref root <pointer>) Exchanges pointers to rotate the tree left. Pre: root is pointer to tree to be rotated AVL Tree Concepts Post: node rotated and root updated AVL Balance AVL Tree Operations tempPtr = root->right Multiway Trees B-Trees root->right = tempPtr->left tempPtr->left = root Return tempPtr End rotateLeft 8.18 AVL Trees, B-Trees Balancing Trees - Case 1: Left of Left Dr.
Nguyen Ho Man Rang Out of balance condition created by a left high subtree of a left high tree → balance the tree by rotating the out of balance node to the right. AVL Tree Concepts AVL Balance AVL Tree Operations Multiway Trees B-Trees (Source: Data Structures - A Pseudocode Approach with C++) 8.19 AVL Trees, B-Trees Balancing Trees - Case 1: Left of Left Dr. Nguyen Ho Man Rang AVL Tree Concepts AVL Balance AVL Tree Operations Multiway Trees B-Trees (Source: Data Structures - A Pseudocode Approach with C++) 8.20 AVL Trees, B-Trees Balancing Trees - Case 2: Right of Right Dr. Nguyen Ho Man Rang Out of balance condition created by a right high subtree of a right high tree → balance the tree by rotating the out of balance node to the left.
AVL Tree Concepts AVL Balance AVL Tree Operations Multiway Trees B-Trees (Source: Data Structures - A Pseudocode Approach with C++) 8.21 AVL Trees, B-Trees Balancing Trees - Case 2: Right of Right Dr. Nguyen Ho Man Rang AVL Tree Concepts AVL Balance AVL Tree Operations Multiway Trees B-Trees (Source: Data Structures - A Pseudocode Approach with C++) 8.22 AVL Trees, B-Trees Balancing Trees - Case 3: Right of Left Dr. Nguyen Ho Man Rang Out of balance condition created by a right high subtree of a left high tree → balance the tree by two steps: 1 rotating the left subtree to the left; AVL Tree Concepts AVL Balance 2 rotating the root to the right. AVL Tree Operations Multiway Trees B-Trees (Source: Data Structures - A Pseudocode Approach with C++) 8.23 AVL Trees, B-Trees Balancing Trees - Case 3: Right of Left Dr.
Nguyen Ho Man Rang AVL Tree Concepts AVL Balance AVL Tree Operations Multiway Trees B-Trees (Source: Data Structures - A Pseudocode Approach with C++) 8.24 AVL Trees, B-Trees Balancing Trees - Case 4: Left of Right Dr. Nguyen Ho Man Rang Out of balance condition created by a left high subtree of a right high tree → balance the tree by two steps: 1 rotating the right subtree to the right; AVL Tree Concepts AVL Balance 2 rotating the root to the left. AVL Tree Operations Multiway Trees B-Trees (Source: Data Structures - A Pseudocode Approach with C++) 8.25 AVL Trees, B-Trees Balancing Trees - Case 4: Left of Right Dr. Nguyen Ho Man Rang AVL Tree Concepts AVL Balance AVL Tree Operations Multiway Trees B-Trees (Source: Data Structures - A Pseudocode Approach with C++) 8.26 AVL Trees, B-Trees Dr.
Nguyen Ho Man Rang AVL Tree Concepts AVL Tree Operations AVL Balance AVL Tree Operations Multiway Trees B-Trees 8.27 AVL Trees, B-Trees AVL Tree Structure Dr. Nguyen Ho Man Rang node avlTree d a t a <dataType> r o o t <p o i n t e r > l e f t <p o i n t e r > end a v l T r e e r i g h t <p o i n t e r > AVL Tree Concepts b a l a n c e <b a l a n c e _ f a c t o r > AVL Balance end node AVL Tree Operations // G e n e r a l dataTye : Multiway Trees B-Trees dataType k e y <keyType> f i e l d 1 <. > end dataType Note: Array is not suitable for AVL Tree.28 AVL Trees, B-Trees AVL Tree Operations Dr. Nguyen Ho Man Rang • Search and retrieval are the same for any AVL Tree Concepts AVL Balance binary tree.
AVL Tree Operations • AVL Insert Multiway Trees • AVL Delete B-Trees 8.29 AVL Trees, B-Trees AVL Insert Dr. Nguyen Ho • Insert can make an out of balance condition. Man Rang AVL Tree Concepts AVL Balance AVL Tree Operations • Otherwise, some inserts can make an automatic Multiway Trees balancing.30 AVL Trees, B-Trees AVL Insert Algorithm Algorithm AVLInsert(ref root <pointer>, Dr. Nguyen Ho Man Rang val newPtr <pointer>, ref taller <boolean>) Using recursion, insert a node into an AVL tree.
AVL Tree Concepts AVL Balance AVL Tree Pre: root is a pointer to first node in AVL Operations Multiway Trees tree/subtree B-Trees newPtr is a pointer to new node to be inserted Post: taller is a Boolean: true indicating the subtree height has increased, false indicating same height Return root returned recursively up the 8.31 AVL Trees, B-Trees AVL Insert Algorithm Dr. Nguyen Ho Man Rang // Insert at root if root null then AVL Tree Concepts AVL Balance root = newPtr AVL Tree Operations taller = true Multiway Trees return root B-Trees end 8.32 AVL Trees, B-Trees AVL Insert Algorithm if newPtr->data.key < root->data. Nguyen Ho Man Rang then root->left = AVLInsert(root->left, newPtr, taller) // Left subtree is taller AVL Tree Concepts if taller then AVL Balance AVL Tree if root is LH then Operations Multiway Trees root = leftBalance(root, taller) B-Trees else if root is EH then root->balance = LH else root->balance = EH taller = false end 8.33 AVL Trees, B-Trees AVL Insert Algorithm Dr. Nguyen Ho else Man Rang root->right = AVLInsert(root->right, newPtr, taller) // Right subtree is taller if taller then if root is LH then AVL Tree Concepts root->balance = EH AVL Balance AVL Tree taller = false Operations else if root is EH then Multiway Trees root->balance = RH B-Trees else root = rightBalance(root, taller) end end end return root End AVLInsert 8.34 AVL Trees, B-Trees AVL Left Balance Algorithm Dr.