{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,14]],"date-time":"2024-08-14T11:07:35Z","timestamp":1723633655778},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[1990,2,1]],"date-time":"1990-02-01T00:00:00Z","timestamp":633830400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[1990,2]]},"DOI":"10.1007\/bf01237235","type":"journal-article","created":{"date-parts":[[2005,2,25]],"date-time":"2005-02-25T23:47:12Z","timestamp":1109375232000},"page":"165-178","source":"Crossref","is-referenced-by-count":8,"title":["Binary search trees of almost optimal height"],"prefix":"10.1007","volume":"28","author":[{"given":"Arne","family":"Andersson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christian","family":"Icking","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rolf","family":"Klein","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"Ottmann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"2","key":"CR1","first-page":"1259","volume":"146","author":"G.M. Adelson-Velskii","year":"1962","unstructured":"Adelson-Velskii, G.M., Landis, E.M.: An algorithm for the organization of information. Dokl. Akad. Nauk SSSR146(2), 1259?1262 (1962)","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"CR2","volume-title":"Data structures and algorithms","author":"A.V. Aho","year":"1983","unstructured":"Aho, A.V., Hopcroft, J.E., Ullman, J.D.: Data structures and algorithms. Reading MA: Addison-Wesley 1983"},{"issue":"4","key":"CR3","doi-asserted-by":"crossref","first-page":"290","DOI":"10.1007\/BF00289509","volume":"1","author":"R. Bayer","year":"1972","unstructured":"Bayer, R.: Symmetric binary B-trees: Data structure and maintenance algorithms. Acta Inf.1(4), 290?306 (1972)","journal-title":"Acta Inf."},{"key":"CR4","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1007\/BF00288683","volume":"1","author":"R. Bayer","year":"1972","unstructured":"Bayer, R., McCreight, E.: Organization and maintenance of large ordered indexes. Acta Inf.1, 173?189 (1972)","journal-title":"Acta Inf."},{"issue":"7","key":"CR5","doi-asserted-by":"crossref","first-page":"695","DOI":"10.1145\/358105.358191","volume":"27","author":"H. Chang","year":"1984","unstructured":"Chang, H., Iynegar, S.S.: Efficient algorithms to globally balance a binary search tree. Commun. ACM27(7), 695?702 (1984)","journal-title":"Commun. ACM"},{"issue":"4","key":"CR6","doi-asserted-by":"crossref","first-page":"360","DOI":"10.1093\/comjnl\/19.4.360","volume":"19","author":"A.C. Day","year":"1976","unstructured":"Day, A.C.: Balancing a binary tree. Comput. J.19(4), 360?361 (1976)","journal-title":"Comput. J."},{"key":"CR7","volume-title":"Handbook of algorithms and data structures","author":"G.H. Gonnet","year":"1983","unstructured":"Gonnet, G.H.: Handbook of algorithms and data structures. Reading, MA: Addison-Wesley 1983"},{"key":"CR8","doi-asserted-by":"crossref","unstructured":"Guibas, L.J., Sedgewick, R.: A dichromatic framework for balanced trees. In: Proc. 19th Ann. IEEE Symp. on Foundations of Computer Science, pp. 8?21, 1978","DOI":"10.1109\/SFCS.1978.3"},{"key":"CR9","series-title":"Lect. Notes Comput. Sci.","first-page":"84","volume-title":"Graphtheoretic concepts in computer science","author":"C. Icking","year":"1987","unstructured":"Icking, C., Klein, R., Ottmann, T.: Priority search trees in secondary memory. In: G\u00f6ttler, H., Schneider, H.J. (eds.) Graphtheoretic concepts in computer science. (Lect. Notes Comput. Sci., vol. 314, pp. 84?93). Berlin Heidelberg New York: Springer 1987"},{"issue":"2","key":"CR10","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1145\/361254.361259","volume":"15","author":"W.A. Martin","year":"1972","unstructured":"Martin, W.A., Ness, D.N.: Optimizing binary trees grown with a sorting algorithm. Commun. ACM15(2), 88?93 (1972)","journal-title":"Commun. ACM"},{"issue":"1","key":"CR11","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1016\/0020-0190(76)90094-6","volume":"5","author":"H.A. Mauer","year":"1976","unstructured":"Mauer, H.A., Ottmann, T., Six, H.W.: Implementing dictionaries using binary trees of very small height. Inf. Process. Lett.5(1), 11?14 (1976)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"CR12","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1137\/0214021","volume":"14","author":"E.M. McCreight","year":"1985","unstructured":"McCreight, E.M.: Priority search trees. SIAM J. Comput.14(2), 257?276 (1985)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"CR13","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1137\/0202005","volume":"2","author":"J. Nievergelt","year":"1973","unstructured":"Nievergelt, J., Reingold, E.M.: Binary trees of bounded balance. SIAM J. Comput.2(1), 33?43 (1973)","journal-title":"SIAM J. Comput."},{"key":"CR14","unstructured":"Olivie, H.J.: A study of balanced binary trees and balanced one-two-trees. Ph. D. Thesis, Dept of Mathematics, University of Antwerp, 1980"},{"key":"CR15","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1051\/ita\/1982160100511","volume":"16","author":"H.J. Olivie","year":"1982","unstructured":"Olivie, H.J.: A new class of balanced search trees: Half-balanced binary search trees. RAIRO Inf Theor Appl.16, 51?71 (1982)","journal-title":"RAIRO Inf Theor Appl."},{"key":"CR16","unstructured":"Ottmann, Th., Wood, D.: Updating binary trees with constant linkage cost. In: Proceedings of the 2nd Scandinavian Workshop on Algorithm Theory, SWAT '90, Bergen, 1990"},{"key":"CR17","series-title":"Lect. Notes Comput. Sci.","volume-title":"The design of dynamic data structures","author":"M.H. Overmars","year":"1983","unstructured":"Overmars, M.H.: The design of dynamic data structures. (Lect. Notes Comput. Sci., vol. 156). Berlin Heidelberg New York: Springer 1983"},{"issue":"7","key":"CR18","doi-asserted-by":"crossref","first-page":"669","DOI":"10.1145\/6138.6151","volume":"29","author":"N. Sarmak","year":"1986","unstructured":"Sarmak, N., Tarjan, R.E.: Planar point location using persistent search trees. Commun. ACM29(7), 669?679 (1986)","journal-title":"Commun. ACM"},{"issue":"9","key":"CR19","doi-asserted-by":"crossref","first-page":"902","DOI":"10.1145\/6592.6599","volume":"29","author":"Q.F. Stout","year":"1986","unstructured":"Stout, Q.F., Warren, B.L.: Tree rebalancing in optimal time and space. Commun. ACM29(9), 902?908 (1986)","journal-title":"Commun. ACM"},{"key":"CR20","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1016\/0020-0190(83)90099-6","volume":"16","author":"R.E. Tarjan","year":"1983","unstructured":"Tarjan, R.E.: Updating a balanced search tree inO(1) rotations. Inf. Process. Lett.16, 253?257 (1983)","journal-title":"Inf. Process. Lett."},{"key":"CR21","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1007\/BF00289574","volume":"18","author":"J. Leeuwen van","year":"1983","unstructured":"Leeuwen, J. van, Overmars, M.H.: Stratified balanced search trees. Acta Inf.18, 345?359 (1983)","journal-title":"Acta Inf."}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01237235.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01237235\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01237235","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,2]],"date-time":"2019-05-02T10:07:03Z","timestamp":1556791623000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01237235"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990,2]]},"references-count":21,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1990,2]]}},"alternative-id":["BF01237235"],"URL":"https:\/\/doi.org\/10.1007\/bf01237235","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"value":"0001-5903","type":"print"},{"value":"1432-0525","type":"electronic"}],"subject":[],"published":{"date-parts":[[1990,2]]}}}