AVL Trees, B-Trees Luong The Nhan, Tran Giang Son Chapter 7 AVL Trees, B-Trees AVL Tree Concepts AVL Balance Data Structures and Algorithms AVL Tree Operations Multiway Trees B-Trees Luong The Nhan, Tran Giang Son Faculty of Computer Science and Engineering University of Technology, VNU-HCM 7.1 AVL Trees, B-Trees Outcomes Luong The Nhan, Tran Giang Son • 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 Luong The Nhan, Tran Giang Son • 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 AVL Balance • L.8 - Analyze the complexity and develop 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 Luong The Nhan, Tran Giang Son 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 7.4 AVL Trees, B-Trees Luong The Nhan, Tran Giang Son AVL Tree Concepts AVL Tree Concepts AVL Balance AVL Tree Operations Multiway Trees B-Trees 7.5 AVL Trees, B-Trees AVL Tree Luong The Nhan, Tran Giang Son 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 Luong The Nhan, Tran Giang Son 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 Luong The Nhan, Tran Giang Son Balance factor AVL Tree Concepts • left_higher (LH): HL = HR + 1 AVL Balance AVL Tree • equal_height (EH): HL = HR Operations Multiway Trees • right_higher (RH): HR = HL + 1 B-Trees (HL , HR : the heights of left and right subtrees) 7.8 AVL Trees, B-Trees AVL Trees Luong The Nhan, Tran Giang Son 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 7.9 AVL Trees, B-Trees Non-AVL Trees Luong The Nhan, Tran Giang Son 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 7.10 AVL Trees, B-Trees Why AVL Trees? Luong The Nhan, Tran Giang Son • 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 inscrease in height.
• AVL trees ensure that the complexity of search is O(log2 n).11 AVL Trees, B-Trees Luong The Nhan, Tran Giang Son AVL Tree Concepts AVL Balance AVL Balance AVL Tree Operations Multiway Trees B-Trees 7.12 AVL Trees, B-Trees Balancing Trees Luong The Nhan, • When we insert a node into a tree or delete Tran Giang Son 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; 7.13 AVL Trees, B-Trees Unbalanced tree cases Luong The Nhan, Tran Giang Son AVL Tree Concepts AVL Balance AVL Tree Operations Multiway Trees B-Trees (Source: Data Structures - A Pseudocode Approach with C++) 7.14 AVL Trees, B-Trees Unbalanced tree cases Luong The Nhan, Tran Giang Son AVL Tree Concepts AVL Balance AVL Tree Operations Multiway Trees B-Trees (Source: Data Structures - A Pseudocode Approach with C++) 7.15 AVL Trees, B-Trees Rotate Right Luong The Nhan, Tran Giang Son Algorithm rotateRight(ref root <pointer>) Exchanges pointers to rotate the tree right. 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->left Multiway Trees B-Trees root->left = tempPtr->right tempPtr->right = root Return tempPtr End rotateRight 7.16 AVL Trees, B-Trees Rotate Right Luong The Nhan, Tran Giang Son AVL Tree Concepts AVL Balance AVL Tree Operations Multiway Trees B-Trees (Source: Data Structures - A Pseudocode Approach with C++) 7.17 AVL Trees, B-Trees Rotate Left Luong The Nhan, Tran Giang Son 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 7.18 AVL Trees, B-Trees Balancing Trees - Case 1: Left of Left Luong The Nhan, Tran Giang Son 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++) 7.19 AVL Trees, B-Trees Balancing Trees - Case 1: Left of Left Luong The Nhan, Tran Giang Son AVL Tree Concepts AVL Balance AVL Tree Operations Multiway Trees B-Trees (Source: Data Structures - A Pseudocode Approach with C++) 7.20 AVL Trees, B-Trees Balancing Trees - Case 2: Right of Right Luong The Nhan, Tran Giang Son 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++) 7.21 AVL Trees, B-Trees Balancing Trees - Case 2: Right of Right Luong The Nhan, Tran Giang Son AVL Tree Concepts AVL Balance AVL Tree Operations Multiway Trees B-Trees (Source: Data Structures - A Pseudocode Approach with C++) 7.22 AVL Trees, B-Trees Balancing Trees - Case 3: Right of Left Luong The Nhan, Tran Giang Son 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++) 7.23 AVL Trees, B-Trees Balancing Trees - Case 3: Right of Left Luong The Nhan, Tran Giang Son AVL Tree Concepts AVL Balance AVL Tree Operations Multiway Trees B-Trees (Source: Data Structures - A Pseudocode Approach with C++) 7.24 AVL Trees, B-Trees Balancing Trees - Case 4: Left of Right Luong The Nhan, Tran Giang Son 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++) 7.25 AVL Trees, B-Trees Balancing Trees - Case 4: Left of Right Luong The Nhan, Tran Giang Son AVL Tree Concepts AVL Balance AVL Tree Operations Multiway Trees B-Trees (Source: Data Structures - A Pseudocode Approach with C++) 7.26 AVL Trees, B-Trees Luong The Nhan, Tran Giang Son AVL Tree Concepts AVL Tree Operations AVL Balance AVL Tree Operations Multiway Trees B-Trees 7.27 AVL Trees, B-Trees AVL Tree Structure Luong The Nhan, Tran Giang Son 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 Luong The Nhan, Tran Giang Son • 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 7.29 AVL Trees, B-Trees AVL Insert Luong The Nhan, • Insert can make an out of balance condition. Tran Giang Son 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 Luong The Nhan, Tran Giang Son Algorithm AVLInsert(ref root <pointer>, val newPtr <pointer>, ref taller <boolean>) Using recursion, insert a node into an AVL tree.
AVL Tree Concepts AVL Balance Pre: root is a pointer to first node in AVL AVL Tree tree/subtree Operations Multiway Trees newPtr is a pointer to new node to be inserted B-Trees Post: taller is a Boolean: true indicating the subtree height has increased, false indicating same height Return root returned recursively up the tree 7.31 AVL Trees, B-Trees AVL Insert Algorithm Luong The Nhan, Tran Giang Son // 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 7.32 AVL Trees, B-Trees AVL Insert Algorithm Luong The Nhan, if newPtr->data.key < root->data.key then Tran Giang Son root->left = AVLInsert(root->left, newPtr, taller) // Left subtree is taller if taller then AVL Tree Concepts AVL Balance if root is LH then AVL Tree root = leftBalance(root, taller) Operations Multiway Trees else if root is EH then B-Trees root->balance = LH else root->balance = EH taller = false end end 7.