tailieunhanh - Lecture Data structures and algorithms in Java (6th edition): Chapter 11.1 - Goodrich, Tamassia, Goldwasser

This chapter provides knowledge of trees. Data structures and algorithms in java provides an introduction to data structures and algorithms, including their design, analysis, and implementation. | (2,4) Trees 3/20/14 Presentation for use with the textbook Data Structures and Algorithms in Java, 6th edition, by M. T. Goodrich, R. Tamassia, and M. H. Goldwasser, Wiley, 2014 (2,4) Trees 9 2 5 7 © 2014 Goodrich, Tamassia, Goldwasser 10 14 (2,4) Trees 1 Multi-Way Search Tree ! A multi-way search tree is an ordered tree such that n   n   Each internal node has at least two children and stores d -1 key-element items (ki, oi), where d is the number of children For a node with children v1 v2 vd storing keys k1 k2 kd-1 w   keys in the subtree of v1 are less than k1 w   keys in the subtree of vi are between ki-1 and ki (i = 2, , d - 1) w   keys in the subtree of vd are greater than kd-1 n   The leaves store no items and serve as placeholders 11 2 6 8 24 15 27 32 30 © 2014 Goodrich, Tamassia, Goldwasser (2,4) Trees 2 1 (2,4) Trees 3/20/14 Multi-Way Inorder Traversal ! We can extend the notion of inorder traversal from binary trees ! ! to multi-way search trees Namely, we visit item (ki, oi) of node v between the recursive traversals of the subtrees of v rooted at children vi and vi + 1 An inorder traversal of a multi-way search tree visits the keys in increasing order 11 24 8 2 6 8 2 1 4 3 6 5 12 15 27 7 9 32 14 10 18 30 11 13 15 © 2014 Goodrich, Tamassia, Goldwasser 19 16 17 (2,4) Trees 3 Multi-Way Searching ! Similar to search in a binary search tree ! A each internal node with children v1 v2 vd and keys k1 k2 kd-1 n   n   n   n   k = ki (i = 1, , d - 1): the search terminates successfully k kd-1: we continue the search in child vd ! Reaching an external node terminates the search unsuccessfully ! Example: search for 30 11 2 6 8 24 15 27 32 30 © 2014 Goodrich, Tamassia, Goldwasser (2,4) Trees 4 2 (2,4) Trees 3/20/14 (2,4) Trees ! A (2,4) tree (also called 2-4 tree or 2-3-4 tree) is a multi-way search with the following properties n   n   Node-Size Property: every internal node has at most four .