{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T14:27:13Z","timestamp":1725460033229},"publisher-location":"Boston","reference-count":23,"publisher":"Kluwer Academic Publishers","isbn-type":[{"type":"print","value":"1402081405"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/1-4020-8141-3_25","type":"book-chapter","created":{"date-parts":[[2006,2,21]],"date-time":"2006-02-21T15:15:11Z","timestamp":1140534911000},"page":"307-316","source":"Crossref","is-referenced-by-count":4,"title":["Adaptive Sorting with AVL Trees"],"prefix":"10.1007","author":[{"given":"Amr","family":"Elmasry","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"25_CR1","doi-asserted-by":"crossref","unstructured":"A. Andersson and T. W. Lai. Fast updating of well-balanced trees. Scandinavian Workshop on Algorithm Theory (1990), 111\u2013121.","DOI":"10.1007\/3-540-52846-6_82"},{"key":"25_CR2","first-page":"263","volume":"146","author":"G. Adelson-Velskii","year":"1962","unstructured":"G. Adelson-Velskii and E. Landis. On an information organization algorithm. Doklady Akademia Nauk SSSR, 146(1962), 263\u2013266.","journal-title":"Doklady Akademia Nauk SSSR"},{"key":"25_CR3","doi-asserted-by":"publisher","first-page":"594","DOI":"10.1137\/0209045","volume":"9","author":"M. Brown","year":"1980","unstructured":"M. Brown and R. Tarjan. Design and analysis of data structures for representing sorted lists. SIAM J. Comput. 9 (1980), 594\u2013614.","journal-title":"SIAM J. Comput."},{"key":"25_CR4","doi-asserted-by":"publisher","first-page":"629","DOI":"10.1007\/BF01190160","volume":"9","author":"S. Carlsson","year":"1993","unstructured":"S. Carlsson, C. Levcopoulos and O. Petersson. Sublinear merging and natural Mergesort. Algorithmica 9 (1993), 629\u2013648.","journal-title":"Algorithmica"},{"key":"25_CR5","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1137\/S009753979732699X","volume":"30","author":"R. Cole","year":"2000","unstructured":"R. Cole. On the dynamic finger conjecture for splay trees. Part II: The proof. SIAM J. Comput. 30 (2000), 44\u201385.","journal-title":"SIAM J. Comput."},{"key":"25_CR6","unstructured":"A. Elmasry. Priority queues, pairing and adaptive sorting. 29th Int. Colloquium for Automata, Languages and Programming. In LNCS 2380 (2002), 183\u2013194."},{"key":"25_CR7","doi-asserted-by":"crossref","unstructured":"A. Elmasry and M. Fredman. Adaptive sorting and the information theoretic lower bound. Symp. on Theoret.Aspect. Comput. Sc. In LNCS 2607 (2003), 654\u2013662.","DOI":"10.1007\/3-540-36494-3_57"},{"key":"25_CR8","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1016\/0890-5401(89)90050-3","volume":"83","author":"V. Estivill-Castro","year":"1989","unstructured":"V. Estivill-Castro and D. Wood. A new measure of presortedness. Infor. and Comput. 83 (1989), 111\u2013119.","journal-title":"Infor. and Comput."},{"key":"25_CR9","first-page":"49","volume":"9","author":"L. Guibas","year":"1977","unstructured":"L. Guibas, E. McCreight, M. Plass and J. Roberts. A new representation of linear lists. ACM Symp. on Theory of Computing 9 (1977), 49\u201360.","journal-title":"ACM Symp. on Theory of Computing"},{"key":"25_CR10","doi-asserted-by":"crossref","unstructured":"L. Guibas and R. Sedgewick. A dichromatic framework for balanced trees. Foundations of Computer Science (1978), 8\u201321.","DOI":"10.1109\/SFCS.1978.3"},{"issue":"1","key":"25_CR11","first-page":"23","volume":"19","author":"P. Karlton","year":"1976","unstructured":"P. Karlton, S. Fuller, R. Scroggs and E. Kaehler. Performance of height-balanced trees. Information Retrieval and Language Processing 19(1) (1976), 23\u201328.","journal-title":"Information Retrieval and Language Processing"},{"key":"25_CR12","unstructured":"D. Knuth. The art of Computer programming. Vol III: Sorting and Searching. Addison-wesley, second edition (1998)."},{"key":"25_CR13","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0020-0190(91)90181-G","volume":"39","author":"C. Levcopoulos","year":"1991","unstructured":"C. Levcopoulos and O. Petersson. Splitsort-An adaptive sorting algorithm. Information Processing Letters 39 (1991), 205\u2013211.","journal-title":"Information Processing Letters"},{"key":"25_CR14","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1006\/jagm.1993.1021","volume":"14","author":"C. Levcopoulos","year":"1993","unstructured":"C. Levcopoulos and O. Petersson. Adaptive Heapsort. J. Alg. 14 (1993), 395\u2013413.","journal-title":"J. Alg."},{"key":"25_CR15","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1016\/0304-3975(95)00256-1","volume":"163","author":"C. Levcopoulos","year":"1996","unstructured":"C. Levcopoulos and O. Petersson. Exploiting few inversions when sorting: Sequential and parallel algorithms. Theoret. Comput. Science 163 (1996), 211\u2013238.","journal-title":"Theoret. Comput. Science"},{"key":"25_CR16","doi-asserted-by":"crossref","first-page":"318","DOI":"10.1109\/TC.1985.5009382","volume":"C-34","author":"H. Mannila","year":"1985","unstructured":"H. Mannila. Measures of presortedness and optimal sorting algorithms. IEEE Trans. Comput. C-34 (1985), 318\u2013325.","journal-title":"IEEE Trans. Comput."},{"key":"25_CR17","volume-title":"Data structures and algorithms. Vol.1. Sorting and Searching","author":"K. Mehlhorn","year":"1984","unstructured":"K. Mehlhorn. Data structures and algorithms. Vol.1. Sorting and Searching. Springer-Verlag, Berlin\/Heidelberg. (1984)"},{"key":"25_CR18","doi-asserted-by":"crossref","unstructured":"K. Mehlhorn. Sorting presorted files. 4th GI Conference on Theory of Computer Science. In LNCS 67 (1979), 199\u2013212.","DOI":"10.1007\/3-540-09118-1_22"},{"issue":"7","key":"25_CR19","doi-asserted-by":"crossref","first-page":"781","DOI":"10.1002\/(SICI)1097-024X(199607)26:7<781::AID-SPE35>3.0.CO;2-B","volume":"126","author":"A. Moffat","year":"1996","unstructured":"A. Moffat, G. Eddy and O. Petersson. Splaysort: fast, verstile, practical. Softw. Pract. and Exper. 126(7) (1996), 781\u2013797.","journal-title":"Softw. Pract. and Exper."},{"key":"25_CR20","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/0166-218X(93)E0160-Z","volume":"59","author":"O. Petersson","year":"1995","unstructured":"O. Petersson and A. Moffat. A framework for adaptive sorting. Discrete App. Math. 59 (1995), 153\u2013179.","journal-title":"Discrete App. Math"},{"issue":"3","key":"25_CR21","doi-asserted-by":"publisher","first-page":"652","DOI":"10.1145\/3828.3835","volume":"32","author":"D. Sleator","year":"1985","unstructured":"D. Sleator and R. Tarjan. Self-adjusting binary search trees. J. ACM 32(3) (1985), 652\u2013686.","journal-title":"J. ACM"},{"key":"25_CR22","doi-asserted-by":"crossref","first-page":"306","DOI":"10.1137\/0606031","volume":"6","author":"R. Tarjan","year":"1985","unstructured":"R. Tarjan. Amortized computational complexity. SIAM J. Alg. Disc. Meth. 6 (1985), 306\u2013318.","journal-title":"SIAM J. Alg. Disc. Meth"},{"key":"25_CR23","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1016\/S0019-9958(85)80034-6","volume":"67","author":"A. Tsakalidis","year":"1985","unstructured":"A. Tsakalidis. AVL-trees for localized search. Inf. and Cont. 67 (1985), 173\u2013194.","journal-title":"Inf. and Cont"}],"container-title":["IFIP International Federation for Information Processing","Exploring New Frontiers of Theoretical Informatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/1-4020-8141-3_25.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T20:28:14Z","timestamp":1619555294000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/1-4020-8141-3_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["1402081405"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/1-4020-8141-3_25","relation":{},"subject":[]}}