tailieunhanh - Bài giảng Cấu trúc dữ liệu & giải thuật: Balanced search trees

Bài giảng "Cấu trúc dữ liệu và giải thuật: Balanced search trees" cung cấp cho người học các kiến thức: Balanced search trees, 2-3 Trees, 2-3-4 Trees. Đây là một tài liệu hữu ích dành cho các bạn sinh viên ngành Công nghệ thông tin và những ai quan tâm dùng làm tài liệu học tập và nghiên cứu. | 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 https 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 https 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 https 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 https 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 .