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

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

• Cơ sở dữ liệu
• Splay trees
• Data structures
• Data structures and algorithms
• Computer science
• Design of data structures
• Algorithms in Java
• The binary heap
• Merging priority queues
• The disjoint set class
• Linked lists
• Binary search trees
• Java primer 1
• The java compiler
• Analysis of algorithms
• Analyzing recursive algorithms
• AVL trees
• Red black trees
• Dynamic programming
• Shortest path
• Sorting lower bound
• Memory management
• IO methods
• Control flow
• Object oriented programming
• Using arrays
• Doubly linked lists
• Singly linked lists
• Arrays
• rrayLists
• Basic Sorting Algorithms
• Advanced Algorithms
• Graph Algorithms
• HashTable Class
• Recursive algorithms
• Nonnumerical recursive algorithms
• Object oriented programming with Java
• Programming language
• Java programming language
• Bài giảng ngôn ngữ lập trình Java
• Recursion and advanced algorithms
• The selection sort
• The sorting objects