Nội dung

2    Balanced Search Trees 2-3 Trees 2-3-4 Trees Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013 CuuDuongThanCong.com https://fb.com/tailieudientucntt 1 3  Height of a binary search tree sensitive to order of insertions and removals  Minimum = log2 (n + 1)  Maximum = n  Various search trees can retain balance despite insertions and removals Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013 4  FIGURE 19-1 (a) A binary search tree of maximum height; (b) a binary search tree of minimum height Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013 CuuDuongThanCong.com https://fb.com/tailieudientucntt 2 5  A 2-3 tree not a binary tree  A 2-3 tree never taller than a minimum-height binary tree Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013 6  Placing data items in nodes of a 2-3 tree  A 2-node (has two children) must contain single data item greater than left child’s item(s) and less than right child’s item(s)  A 3-node (has three children) must contain two data items, S and L , such that S is greater than left child’s item(s) and less than middle child’s item(s);  L is greater than middle child’s item(s) and less than right child’s item(s).  Leaf may contain either one or two data items. Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013 CuuDuongThanCong.com https://fb.com/tailieudientucntt 3 7  FIGURE 19-3 Nodes in a 2-3 tree: (a) a 2-node; (b) a 3-node Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013` 8 A 2-3 tree Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013 CuuDuongThanCong.com https://fb.com/tailieudientucntt 4 9  Traverse 2-3 tree in sorted order by performing analogue of inorder traversal on binary tree: Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013 10  Retrieval operation for 2-3 tree similar to retrieval operation for binary search tree Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013 CuuDuongThanCong.com https://fb.com/tailieudientucntt 5 11 Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013 12  Possible to search 2-3 tree and shortest binary search tree with approximately same efficiency, because:  Binary search tree with n nodes cannot be shorter than log2 (n + 1)  2-3 tree with n nodes cannot be taller than log2 (n + 1)  Node in a 2-3 tree has at most two items Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013 CuuDuongThanCong.com https://fb.com/tailieudientucntt 6 13 A balanced binary search tree Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013 14 A 2-3 tree with the same entries Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013 CuuDuongThanCong.com https://fb.com/tailieudientucntt 7 16 After inserting 39 into the tree Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013 17 The steps for inserting 38 into the tree: (a) The located node has no room; (b) the node splits; (c) the resulting tree Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013 CuuDuongThanCong.com https://fb.com/tailieudientucntt 8 18 After inserting 37 into the tree Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013 19 (a), (b), (c) The steps for inserting 36 into the tree Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013 CuuDuongThanCong.com https://fb.com/tailieudientucntt 9 20 (d) the resulting tree Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013 21 The tree after the insertion of 35, 34, and 33 Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013 CuuDuongThanCong.com https://fb.com/tailieudientucntt 10