Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
This chapter provides knowledge of splay trees. Data structures and algorithms in java provides an introduction to data structures and algorithms, including their design, analysis, and implementation. | Splay 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 Splay Trees v 6 8 3 4 © 2013 Goodrich, Tamassia, Goldwasser z Splay Trees 1 Slide by Matt Dickerson Splay Trees are Binary Search Trees all the keys in the blue region are ≥ 20 (20,Z) note that two keys of equal value may be wellseparated (10,A) (35,R) ! BST Rules: n n n entries stored only at internal nodes keys stored at nodes in the left subtree of v are less than or equal to the key stored at v keys stored at nodes in the right subtree of v are greater than or equal to the key stored at v (7,T) (1,Q) (1,C) (21,O) (8,N) (5,H) (2,R) return the keys in order (5,I) Splay Trees (7,P) (36,L) (37,P) (40,X) (10,U) all the keys in the yellow region are ≤ 20 (5,G) ! An inorder traversal will © 2013 Goodrich, Tamassia, Goldwasser (14,J) (6,Y) 2 1 Splay Trees 3/20/14 Searching in a Splay Tree: Starts the Same as in a BST Slide by Matt Dickerson (20,Z) ! Search proceeds down the tree to found item or an external node. ! Example: Search for time with key 11. (10,A) (14,J) (7,T) (1,Q) (1,C) (35,R) (8,N) (5,H) (36,L) (37,P) (40,X) (10,U) (7,P) (2,R) (5,G) (6,Y) (5,I) © 2013 Goodrich, Tamassia, Goldwasser (21,O) Splay Trees 3 Example Searching in a BST, continued Slide by Matt Dickerson (20,Z) ! search for key 8, ends at an internal node. (10,A) (7,T) (1,Q) (1,C) (5,H) (21,O) (7,P) (36,L) (37,P) (40,X) (10,U) (5,G) (5,I) Splay Trees (14,J) (8,N) (2,R) © 2013 Goodrich, Tamassia, Goldwasser (35,R) (6,Y) 4 2 Splay Trees 3/20/14 Splay Trees do Rotations after Every Operation (Even Search) ! new operation: splay n splaying moves a node to the root using rotations right rotation n n n left rotation makes the left child x of a node y into y’s parent; y becomes the right child of x y n makes the
