Data Structure Concepts: AVL Trees and B-Trees

The content covers important concepts related to AVL trees and B-trees, including the representation of an AVL node, insertion operations, rotations for balancing, and definitions of B-trees. AVL trees are self-balancing binary search trees used to maintain balance during insertions and deletions, while B-trees are commonly used for organizing data on external storage to minimize disk accesses. The material provides insights into the structure and functionality of these tree data structures.

• Data Structures
• AVL Trees
• B-Trees
• Insertion Operations
• Balancing

jac_bu Follow

Uploaded on Oct 07, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. Representation of an AVL Node class AVLNode { < declarations for info stored in node, e.g. int info; > AVLnode left; AVLnode right; int height; int height(AVLNode T) { return T == null? -1 : T.height; } }; COSC 2P03 Week 5 1

2. AVL insert AVLNode insert(AVLNode T, AVLNode newNode) { if(T == null) T = newNode; else if(newNode.info < T.info) { T.left = insert(T.left, newNode); if(height(T.left) - height(T.right) == 2) if(newNode.info < T.left.info) //left subtree of T.left T = rotateWithLeftChild(T); else T = doubleWithLeftChild(T); } else { T.right = insert(T.right, newNode); if(height(T.right) - height(T.left) == 2) if(newNode.info > T.right.info) // right subtree of T.right T = rotateWithRightChild(T); else T = doubleWithRightChild(T); } T.height = max(height(T.left), height(T.right)) + 1; return T; } // insert in left subtree //right subtree of T.left // insert in right subtree // left subtree of T.right COSC 2P03 Week 5 2

3. Single rotation left-left Insertion in left subtree of k2.left caused an imbalance at k2: need to rebalance from k2 down. AVLNode rotateWithLeftChild(AVLNode k2) { AVLNode k1 = k2.left; k2.left = k1.right; k1.right = k2; k2.height = max(height(k2.left, height(k2.right)) + 1; k1.height = max(height(k1.left), k2.height) + 1; return k1; } Note: right-right case is symmetric to above (left right). COSC 2P03 Week 5 3

4. Double rotation right-left Insertion in right subtree of left child caused imbalance at k3: need to rebalance from k3 down. AVLNode doubleWithLeftChild(AVLNode k3) { k3.left = rotateWithRightChild(k3.left); return rotateWithLeftChild(k3); } Note: left-right case is symmetric to above (left right). COSC 2P03 Week 5 4

5. B Trees (section 4.7 of textbook) Commonly used for organizing data on external storage (e.g. disk) Disk access time (time to read/write a block) dominates cost Very important to minimize number of disk accesses Some notes on terminology: This textbook uses the name B tree, but elsewhere they are known as B+ trees In this textbook, the order of a B tree is the maximum number of children per index node. Elsewhere, order refers to the minimum number of children in index nodes other than the root. COSC 2P03 Week 5 5

6. B tree definitions A B-tree of order M is an M-ary tree such that: 1. Data items are only in the leaves 2. Non-leaf (index) nodes store up to M-1 keys: key i determines the smallest possible key in subtree i+1. 3. The root is either a leaf or has between 2 and M children Every node other than the root is at least half-full: 4. All non-leaf nodes (except root) have at least M/2 children 5. All leaves are at the same depth and have between L/2 and L records. COSC 2P03 Week 5 6

7. B tree and Binary Search Tree comparison Binary search trees: nodes have 0, 1 or 2 children and 1 key B-trees: non-leaf nodes have up to M children: a node with d keys has d+1 children Binary search trees: data is stored in both leaf and non-leaf nodes, and for every given index node N: N s left subtree contains only items with keys < N s key N s right subtree contains only items with keys > N s key B-trees: data is stored only in leaf nodes. Non-leaf nodes contain up to M-1 keys (k1, , kM-1): Subtree to left of k1 contains only items with keys <k1 Subtree between ki and ki+1 contains only items with keys <ki+1and ki Subtree to right of kM-1contains only items with keys kM-1 COSC 2P03 Week 5 7

8. B-tree Example M=5 and L=3 100 150 200 10 30 50 110 120 130 160 180 220 240 260 3 7 10 15 20 30 35 50 80 90 100 105 110 115 120 125 130 140 150 155 160 165 170 180 190 200 210 220 225 230 240 250 260 270 275 COSC 2P03 Week 5 8

9. B-tree example: insert 40 100 150 200 10 30 50 110 120 130 160 180 220 240 260 3 7 10 15 20 30 35 40 50 80 90 100 105 110 115 120 125 130 140 150 155 160 165 170 180 190 200 210 220 225 230 240 250 260 270 275 COSC 2P03 Week 5 9

10. B-tree example: insert 70 100 150 200 10 30 50 80 110 120 130 160 180 220 240 260 50 70 80 90 3 7 10 15 20 30 35 40 100 105 110 115 120 125 130 140 150 155 160 165 170 180 190 200 210 220 225 230 240 250 260 270 275 COSC 2P03 Week 5 10

11. B-tree example: insert 25 30 100 150 200 10 20 50 80 110 120130 160 180 220 240 260 10 15 20 25 3 7 30 35 40 50 70 80 90 100 105 110 115 120 125 130 140 150 155 160 165 170 180 190 200 220 240 260 210 225 250 270 230 275 COSC 2P03 Week 5 11

12. B-tree example: insert 235 30 100 150 200 220 230 240260 10 20 50 80 110 120130 160 180 200 220 230 240 260 210 225 235 250 270 3 7 10 15 20 25 30 35 40 50 70 80 90 100 105 110 115 120 125 130 140 150 155 160 180 165 190 170 275 COSC 2P03 Week 5 12

13. B-tree example: insert 280 150 30 100 200 240 220230 260275 10 20 50 80 110120130 160180 240 260 275 250 270 280 3 7 10 15 20 25 30 35 40 50 70 80 90 100 110 120 130 105 115 125 140 150 160 180 155 165 190 170 200 220 230 210 225 235 COSC 2P03 Week 5 13

14. Heaps A heap is a binary tree that satisfies all of the following properties: Structure property: It is a complete binary tree Heap-order property: Every node satisfies the heap condition: The key of every node n must be smaller than (or equal to) the keys of its children, i.e. n.info n.left.info and n.info n.right.info COSC 2P03 Week 5 14