{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,24]],"date-time":"2025-12-24T12:42:23Z","timestamp":1766580143852},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2019,5,21]],"date-time":"2019-05-21T00:00:00Z","timestamp":1558396800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,5,21]],"date-time":"2019-05-21T00:00:00Z","timestamp":1558396800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[2019,7]]},"DOI":"10.1007\/s00236-019-00335-9","type":"journal-article","created":{"date-parts":[[2019,5,22]],"date-time":"2019-05-22T11:15:59Z","timestamp":1558523759000},"page":"391-404","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Red\u2013black trees with constant update time"],"prefix":"10.1007","volume":"56","author":[{"given":"Amr","family":"Elmasry","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mostafa","family":"Kahla","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fady","family":"Ahdy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mahmoud","family":"Hashem","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,5,21]]},"reference":[{"key":"335_CR1","unstructured":"Adel\u2019son-Vel\u2019skii, G.M., Landis, E.M.: An algorithm for the organization of information. In: Proceedings of the USSR Academy of Sciences (1962)"},{"key":"335_CR2","doi-asserted-by":"crossref","unstructured":"Andersson, A.: Balanced search trees made simple. In: Proceedings of the 3rd Workshop on Algorithms and Data Structures, volume 709 of Lecture Notes in Computer Science, pp. 60\u201371. Springer (1993)","DOI":"10.1007\/3-540-57155-8_236"},{"key":"335_CR3","doi-asserted-by":"publisher","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, 290\u2013306 (1972)","journal-title":"Acta Inf."},{"key":"335_CR4","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1007\/BF00288683","volume":"1","author":"R Bayer","year":"1972","unstructured":"Bayer, R., McCreight, E.M.: Organization and maintenance of large ordered indices. Acta Inform. 1, 173\u2013189 (1972)","journal-title":"Acta Inform."},{"issue":"3","key":"335_CR5","doi-asserted-by":"publisher","first-page":"667","DOI":"10.1016\/S0022-0000(05)80075-3","volume":"49","author":"J Boyar","year":"1994","unstructured":"Boyar, J., Larsen, K.S.: Efficient rebalancing of chromatic search trees. J. Comput. Syst.Sci. 49(3), 667\u2013682 (1994)","journal-title":"J. Comput. Syst.Sci."},{"key":"335_CR6","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"1998","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press, Cambridge (1998)","edition":"3"},{"issue":"2","key":"335_CR7","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1142\/S0129054196000117","volume":"7","author":"R Fleischer","year":"1996","unstructured":"Fleischer, R.: A simple balanced search tree with O(1) worst-case update time. Int. J. Found. Comput. Sci. 7(2), 137\u2013150 (1996)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"335_CR8","doi-asserted-by":"crossref","unstructured":"Guibas, L.J., McCreight, E.M., Plass, M.F., Roberts, J.R.: A new representation for linear lists. In: Proceedings of the 9th Annual ACM Symposium on Theory of Computing, pp. 49\u201360 (1977)","DOI":"10.1145\/800105.803395"},{"key":"335_CR9","doi-asserted-by":"crossref","unstructured":"Guibas, L.J., Sedgewick, R.: A dichromatic framework for balanced trees. In: Proceedings of the 19th Annual Symposium on Foundations of Computer Science, pp. 8\u201321 (1978)","DOI":"10.1109\/SFCS.1978.3"},{"key":"335_CR10","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/BF00288968","volume":"17","author":"S Huddleston","year":"1982","unstructured":"Huddleston, S., Mehlhorn, K.: A new data structure for representing sorted lists. Acta Inform. 17, 157\u2013184 (1982)","journal-title":"Acta Inform."},{"key":"335_CR11","volume-title":"The Art of Computer Programming: Sorting and Searching","author":"DE Knuth","year":"1998","unstructured":"Knuth, D.E.: The Art of Computer Programming: Sorting and Searching, vol. 3, 2nd edn. Addison Wesley Longman Publishing Co., Boston (1998)","edition":"2"},{"issue":"10","key":"335_CR12","doi-asserted-by":"publisher","first-page":"859","DOI":"10.1007\/s002360050145","volume":"35","author":"KS Larsen","year":"1998","unstructured":"Larsen, K.S.: Amortized constant relaxed rebalancing using standard rotations. Acta Inform. 35(10), 859\u2013874 (1998)","journal-title":"Acta Inform."},{"issue":"10","key":"335_CR13","doi-asserted-by":"publisher","first-page":"743","DOI":"10.1007\/PL00013303","volume":"37","author":"KS Larsen","year":"2001","unstructured":"Larsen, K.S., Ottmann, T., Soisalon-Soininen, E.: Relaxed balance for search trees with local rebalancing. Acta Inform. 37(10), 743\u2013763 (2001)","journal-title":"Acta Inform."},{"issue":"3","key":"335_CR14","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF00299635","volume":"26","author":"C Levcopoulos","year":"1988","unstructured":"Levcopoulos, C., Overmars, M.H.: A balanced search tree with O(1) worst-case update time. Acta Inform. 26(3), 269\u2013277 (1988)","journal-title":"Acta Inform."},{"key":"335_CR15","doi-asserted-by":"crossref","unstructured":"Mulmuley, K.: Randomized multidimensional search trees: dynamic sampling (extended abstract). In: Proceedings of the 7th Annual Symposium on Computational Geometry, pp. 121\u2013131 (1991)","DOI":"10.1145\/109648.109662"},{"issue":"1","key":"335_CR16","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1137\/0202005","volume":"2","author":"J Nievergelt","year":"1973","unstructured":"Nievergelt, J., Reingold, E.M.: Binary search trees of bounded balance. SIAM J. Comput. 2(1), 33\u201343 (1973)","journal-title":"SIAM J. Comput."},{"key":"335_CR17","doi-asserted-by":"crossref","unstructured":"Nurmi, O., Soisalon-Soininen, E.: Uncoupling updating and rebalancing in chromatic binary search trees. In: Proceedings of the 10th ACM Symposium on Principles of Database Systems, pp. 192\u2013198 (1991)","DOI":"10.1145\/113413.113430"},{"issue":"6","key":"335_CR18","doi-asserted-by":"publisher","first-page":"547","DOI":"10.1007\/s002360050057","volume":"33","author":"O Nurmi","year":"1996","unstructured":"Nurmi, O., Soisalon-Soininen, E.: Chromatic binary search trees. A structure for concurrent rebalancing. Acta Inform. 33(6), 547\u2013557 (1996)","journal-title":"Acta Inform."},{"issue":"4","key":"335_CR19","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1017\/S0956796899003494","volume":"9","author":"C Okasaki","year":"1999","unstructured":"Okasaki, C.: Red\u2013black trees in a functional setting. J. Funct. Program. 9(4), 471\u2013477 (1999)","journal-title":"J. Funct. Program."},{"key":"335_CR20","first-page":"27","volume":"18","author":"MH Overmars","year":"1982","unstructured":"Overmars, M.H.: A O(1) average time update scheme for balanced search trees. Bull. EATCS 18, 27\u201329 (1982)","journal-title":"Bull. EATCS"},{"key":"335_CR21","series-title":"Lecture Notes in Computer Science","volume-title":"The Design of Dynamic Data Structures","author":"MH Overmars","year":"1983","unstructured":"Overmars, M.H.: The Design of Dynamic Data Structures. Lecture Notes in Computer Science, vol. 156. Springer, Berlin (1983)"},{"key":"335_CR22","unstructured":"Sedgewick, R.: Left-leaning red\u2013black trees. Technical report, Princeton University (2008)"},{"issue":"5","key":"335_CR23","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1016\/0020-0190(83)90099-6","volume":"16","author":"RE Tarjan","year":"1983","unstructured":"Tarjan, R.E.: Updating a balanced search tree in O(1) rotations. Info. Process. Lett. 16(5), 253\u2013257 (1983)","journal-title":"Info. Process. Lett."}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-019-00335-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00236-019-00335-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-019-00335-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,19]],"date-time":"2020-05-19T23:20:05Z","timestamp":1589930405000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00236-019-00335-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,5,21]]},"references-count":23,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2019,7]]}},"alternative-id":["335"],"URL":"https:\/\/doi.org\/10.1007\/s00236-019-00335-9","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"value":"0001-5903","type":"print"},{"value":"1432-0525","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,5,21]]},"assertion":[{"value":"21 December 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 May 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 May 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}