Chúng ta sẽ phát triển chỉ có một chức năng splaying có thể được sử dụng để thu hồi và cho phép chèn. Với một khóa mục tiêu, chức năng tìm kiếm thông qua cây chính, splaying như nó đi. Nếu nó tìm thấy chìa khóa, sau đó nó lấy nó, nếu không, sau đó chèn chức năng như một nút mới. | 568 Chapter 11 Multiway Trees REFERENCES FOR FURTHER STUDY One of the most thorough available studies of trees is in the series of books by Knuth. The correspondence from ordered trees to binary trees appears in Volume 1 pp. 332-347. Volume 3 pp. 471-505 discusses multiway trees B-trees and tries. Tries were first studied in Edward Fredkin Trie memory Communications of the ACM 3 1960 490-499. The original reference for B-trees is R. Bayer and E. McCreight Organization and maintenance of large ordered indexes Acta Informatica 1 1972 173-189. An interesting survey of applications and variations of B-trees is D. Comer The ubiquitous B-tree Computing Surveys 11 1979 121-137. For an alternative treatment of red-black trees including a removal algorithm see Thomas H. Cormen Charles E. Leiserson and Ronald L. Rivest Introduction to Algorithms . Press Cambridge Mass. and McGraw-Hill New York 1990 1028 pages. This book gives comprehensive coverage of many different kinds of algorithms. Another outline of a removal algorithm for red-black trees with more extensive mathematical analysis appears in Derick Wood Data Structures Algorithms and Performance Addison-Wesley Reading Mass. 1993 pages 353-366. Graphs 12 This chapter introduces important mathematical structures called graphs that have applications in subjects as diverse as sociology chemistry geography and electrical engineering. We shall study methods to represent graphs with the data structures available to us and shall construct several important algorithms for processing graphs. Finally we look at the possibility of using graphs themselves as data structures. Mathematical Background 570 Definitions and Examples 570 Undirected Graphs 571 Directed Graphs 571 Computer Representation 572 The Set Representation 572 Adjacency Lists 574 Information Fields 575 Graph Traversal 575 Methods 575 Depth-First Algorithm 577 Breadth-First Algorithm .
