{"entities":{"Q1901709":{"pageid":1912451,"ns":120,"title":"Item:Q1901709","lastrevid":71114238,"modified":"2026-04-13T19:34:30Z","type":"item","id":"Q1901709","labels":{"en":{"language":"en","value":"Chromatic binary search trees: A structure for concurrent rebalancing"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 814159"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1901709$6258D815-E875-49A8-8E7C-08699763EED2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"653866cb61a18f3f036095cbd87a71f279f2b6d6","datavalue":{"value":{"text":"Chromatic binary search trees: A structure for concurrent rebalancing","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1901709$3B2EB6D8-9736-4C15-B354-EC9DB37974D3","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d1274a9225597ec07c3fda87cf54fbbd4f6bd7a2","datavalue":{"value":"0849.68026","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1901709$1F987539-BDC5-4F89-81D7-DBCC57DB6AE3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c3a0c7889cbfc58615c80f78ba461272b4749430","datavalue":{"value":{"entity-type":"item","numeric-id":1825633,"id":"Q1825633"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1901709$8262A35B-C7E1-4A25-9936-3C88F6C5EEEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7f5ae3c40a239b0d91d4aa09f8b879d76f3f35d9","datavalue":{"value":{"entity-type":"item","numeric-id":199234,"id":"Q199234"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1901709$48F40B6E-2829-414D-8298-BFBBAE94819A","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"7d0f02e85530cd06ceb2c58a40dc9c2e0258e194","datavalue":{"value":{"entity-type":"item","numeric-id":161641,"id":"Q161641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1901709$96D9F068-B9A9-45B2-AD92-365971DB922B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d00fe8bfda3ed2cfe20a514de7a7e433b0f6c2b5","datavalue":{"value":{"time":"+1995-11-19T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1901709$04CE19C6-BED0-4081-A05F-32BF9E148C7A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"eb6f053369b90108dc2209956658f7cf0b575501","datavalue":{"value":"We propose a new rebalancing method for binary search trees that allows rebalancing and updating to be uncoupled. In this way we obtain fast updates and, whenever the search tree is accessed by multiple users, a high degree of concurrency. The trees we use are obtained by relaxing the balance conditions of red-black trees. The relaxed red-black trees, called chromatic trees, contain information of possible imbalance such that the rebalancing can be done gradually as a shadow process, or it can be performed separately when no urgent operations are present.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1901709$7ADB83DC-D8DD-41A3-96C4-D7DEA841D40A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f97694d44af155a68434cb72eabc6a4d5dd5227","datavalue":{"value":"68P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1901709$022D06C9-4C25-4F5F-8661-258A8B8E8A1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"14cf74de25853c940589b125137b792dfb2d092b","datavalue":{"value":"68P05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1901709$FD765446-5329-4682-B30B-0E5529B2350A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35bbdcbda53152c249a7f99650e19b5ef62999f2","datavalue":{"value":"68Q10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1901709$F2882A00-7B1F-4901-A73B-73C5AFAD5ACE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"bf2726c5c2109371cc10358eaa69bc4df711caf7","datavalue":{"value":"68P15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1901709$AAACF450-9629-41D8-8A67-AA41279148B9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e0e48179b0d1fbb7fd566ab83cd81fe3216ba58e","datavalue":{"value":"814159","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1901709$EFCDE01C-F08B-4F99-A45D-56767D33E8D2","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e22f3a113575edfbd123e335487b18a37bfe2d4f","datavalue":{"value":"binary search trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1901709$90F051BE-D7C6-44E4-A5B4-5D80BBCE4759","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"672982baf4a04dc399970f41e376f05376f850dc","datavalue":{"value":"rebalancing","type":"string"},"datatype":"string"},"type":"statement","id":"Q1901709$8BA3F25F-CF35-422F-9D0C-B778D2C6282F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"204ec06a742963eec55bac70698ac68ae86e0986","datavalue":{"value":"updating","type":"string"},"datatype":"string"},"type":"statement","id":"Q1901709$F1E6DF20-3C19-47E9-B1C0-7EE0F49C5864","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"445a4fbc6b6bbba6e3c2169de8e334950d4f0826","datavalue":{"value":"concurrency","type":"string"},"datatype":"string"},"type":"statement","id":"Q1901709$006324C8-3680-4A0A-A103-570B4DB279A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c403d6c612382360b759151849f8e9d41d3869c6","datavalue":{"value":"chromatic trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1901709$5FF12F84-70B6-4316-B101-D4019B8A39D9","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1901709$53DBFC42-F48A-4592-879C-B5F87E6FBB36","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"4644c41f0a4cc4123daa68cda2d445ae031a85a6","datavalue":{"value":"https://doi.org/10.1007/s002360050057","type":"string"},"datatype":"url"},"type":"statement","id":"Q1901709$6F8D1051-721A-4496-A69F-B5881E02BC5D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"4235176f719fe97198e365b69a353b79c78ad4fe","datavalue":{"value":"W4241183800","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1901709$4FFBCE1C-0541-4E1D-84C8-041F5C181DDF","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"bc38e666939dc1a21bbb5c318cceddc9f6fa0665","datavalue":{"value":"10.1007/S002360050057","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1901709$901F4B7E-597C-4B3A-A085-FDC1E34C3D7B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8ccce557d36bf044b7b1addc7b086c5417233687","datavalue":{"value":{"entity-type":"item","numeric-id":5056137,"id":"Q5056137"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"101cccf81fe087dea3f461ea632e32c96301eaad","datavalue":{"value":{"amount":"+0.8978720307350159","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1901709$E8D08C06-861A-41B9-B7D4-F0E82FAA46B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b049aa1391a74e3ac6c236021e72e5826403facf","datavalue":{"value":{"entity-type":"item","numeric-id":5057441,"id":"Q5057441"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ae1a0e2333e052e0e59c64f70d79fb5d66d429bd","datavalue":{"value":{"amount":"+0.8635276556015015","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1901709$41BECC89-2BC8-4EE1-AC14-A19D13C62906","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"96b6c8dd92a7c906c8cc332e4af9be06fd1fb168","datavalue":{"value":{"entity-type":"item","numeric-id":1384535,"id":"Q1384535"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b219b7a66361eabdadf6c67e08cc9c66aec6abb1","datavalue":{"value":{"amount":"+0.8632463216781616","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1901709$95C22F9E-B6FF-4FC2-9A4D-7341E794EE02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c3f6f1cc472098d4b84a639b25798dcc541ead3f","datavalue":{"value":{"entity-type":"item","numeric-id":4336276,"id":"Q4336276"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"34785e40ac8f5320569fab12320429ac413ba550","datavalue":{"value":{"amount":"+0.824654221534729","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1901709$16D18F59-9861-44BE-AE01-D9028537F998","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b786d1795dc7b3c859be121736990d3a88b19cbc","datavalue":{"value":{"entity-type":"item","numeric-id":4886316,"id":"Q4886316"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"34785e40ac8f5320569fab12320429ac413ba550","datavalue":{"value":{"amount":"+0.824654221534729","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1901709$B0B2F3A7-678C-4682-BE5C-955B452213B6","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Chromatic binary search trees: A structure for concurrent rebalancing","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Chromatic_binary_search_trees:_A_structure_for_concurrent_rebalancing"}}}}}