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. | Bài giảng Cấu trúc dữ liệu và giải thuật: Balanced search trees - Văn Chí Nam, Nguyễn Thị Hồng Nhung, Đặng Nguyễn Đức Tiến 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 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 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 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 .
