{"entities":{"Q1114387":{"pageid":1125136,"ns":120,"title":"Item:Q1114387","lastrevid":42885071,"modified":"2025-07-15T17:24:20Z","type":"item","id":"Q1114387","labels":{"en":{"language":"en","value":"A balanced search tree O(1) worst-case update time"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4082948"}},"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":"Q1114387$E89CDCEA-C239-42D2-9053-32051C048F62","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1834f39d389a7cd9f4b65b0b7ab3391d57b49c5a","datavalue":{"value":{"text":"A balanced search tree O(1) worst-case update time","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1114387$6E16F93F-7EA0-42BE-9D2C-89CC59DB2B69","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7f2aff8f0772ac43dc0c2bed159b8d79fbb0e9d0","datavalue":{"value":"0662.68016","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114387$CE450AE6-D30B-4A68-A8CB-543C4BA9BF46","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"97706438ed7821f918a257a35aedc0d6627d7d3f","datavalue":{"value":"10.1007/BF00299635","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114387$D7067276-6731-4ACB-B918-894DC8A7C002","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d0dc835d004d9da5bffbf23ad19f48702adc4590","datavalue":{"value":{"entity-type":"item","numeric-id":582112,"id":"Q582112"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114387$D2B00E7E-AFF1-42FA-8B59-6EF686EE34E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3f813421ca1324eea7267dc8879260a77170dbb2","datavalue":{"value":{"entity-type":"item","numeric-id":419362,"id":"Q419362"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114387$38A72474-CBC7-4846-B415-D1C511CE6BAC","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":"Q1114387$F739593B-242E-4152-9270-7AD1ACED71B1","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1114387$639769CA-4812-4C44-B3EF-F386510CB66B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8b7a803b6163fef93ac9d1d3db8f798a0dea5f85","datavalue":{"value":"A new data structure is described for performing member and neighbor queries in O(log n) time that allows for O(1) worst-case update time once the position of the inserted or deleted element is known. In this way previous solutions that achieved only O(1) amortized time or \\(O(\\log^* n)\\) worst-case time are improved. The method is based on a combinatorial result on the height of piles that are split after some fixed number of insertions. This combinatorial result is interesting in its own right and might have other applications as well.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1114387$2E7115EA-BE99-4EAE-8B6E-C1C7883311C1","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"14cf74de25853c940589b125137b792dfb2d092b","datavalue":{"value":"68P05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114387$BF419A17-55B5-4A40-8711-FF69613A5931","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a762d1a2468ec8882180d0d1124f12b94f8eb1b0","datavalue":{"value":"68P20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114387$A440F18A-773A-43FD-A952-D50C99C0C677","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f97694d44af155a68434cb72eabc6a4d5dd5227","datavalue":{"value":"68P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114387$CAFE0B2F-9FB3-495D-AE79-B035FE8F03AB","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"31eb7f7ae120760acc786820835129fd0e1cee5f","datavalue":{"value":"4082948","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114387$14304515-7004-4E1A-92AD-3324E7165BAF","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6db9f1f9961d0d84031a4d201e390d9544ddc6ad","datavalue":{"value":"balanced search tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1114387$4F89199E-BB96-4699-A5DF-93283F2F3DEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c25bc710e4a99b4ad5c06b7d722ebbdb9259ca1e","datavalue":{"value":"data structure","type":"string"},"datatype":"string"},"type":"statement","id":"Q1114387$7CA52299-44D4-4D6E-B1CE-2FC0F6A408B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9b93dfab7e91c6559099602980675388530c1acf","datavalue":{"value":"member and neighbor queries","type":"string"},"datatype":"string"},"type":"statement","id":"Q1114387$C8F51941-F5E2-4BCF-A301-9B4B9A95131C","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":"Q1114387$75D165C4-6D63-40E6-B982-3154CA0F3640","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"930d7570125da587fe649883184a2012330be574","datavalue":{"value":{"entity-type":"item","numeric-id":1162362,"id":"Q1162362"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114387$9B49A1DB-783E-44DC-9DFC-513F3D81F636","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1cd1462286ac5df294dbd58d9be71779e0279c3c","datavalue":{"value":{"entity-type":"item","numeric-id":797269,"id":"Q797269"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114387$DD8A9890-1E54-43AC-88DF-F27E6F740D70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"900ec59125add65ef1a4c201cf6caf4bd0bcc622","datavalue":{"value":{"entity-type":"item","numeric-id":1152223,"id":"Q1152223"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114387$837E592C-A7C2-433F-89D5-0BACF5420B6D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"64b985bfd5531cc3535629951536c00a1d49f53d","datavalue":{"value":"https://doi.org/10.1007/bf00299635","type":"string"},"datatype":"url"},"type":"statement","id":"Q1114387$3372A52D-77C4-41D3-B2E0-63159AA013D7","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"45aaa99b02e1f56d31f94725c6407a410765a231","datavalue":{"value":"W2134458085","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114387$89B17769-9BBA-4057-805E-132DC163ADA1","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"48bc45e02be7c3bc403aec70be75d1d9d1d8544c","datavalue":{"value":{"entity-type":"item","numeric-id":4886313,"id":"Q4886313"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f0592ce19464176569f566848162038ab179d992","datavalue":{"value":{"amount":"+0.98270845","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1114387$82974C85-08B9-48B1-85BB-0A7C4493D51A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"06d97212ee05da277f1e70830f0cbf8425226e17","datavalue":{"value":{"entity-type":"item","numeric-id":4820871,"id":"Q4820871"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"224ca5f71b0d135b11703b7c9c1a21dced0519c9","datavalue":{"value":{"amount":"+0.92087466","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1114387$98A677A0-1AE8-45EE-9907-2B768CD373B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"529d39eb6372a5d97db735795daa713c260ad93b","datavalue":{"value":{"entity-type":"item","numeric-id":3325056,"id":"Q3325056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b70ea642d79d92b42a5dbd765a0caba22b9994dc","datavalue":{"value":{"amount":"+0.88345754","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1114387$711BEBBC-0F6B-4E72-B067-1593B1B23C6A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"84d64d3f08009d0c323f4b8f31e60b8b304e2a62","datavalue":{"value":{"entity-type":"item","numeric-id":4291545,"id":"Q4291545"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a4bc8b12fc1a6bb5d47efa6801b70ffa2aeaeaa1","datavalue":{"value":{"amount":"+0.8630674","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1114387$8D43E10C-1092-47BE-BC04-AA43DEBA28B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"53fdf9401368b6b07334c9d5700935048e5e7bdc","datavalue":{"value":{"entity-type":"item","numeric-id":5056096,"id":"Q5056096"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"422c8f4b99639d85dadbf83cf9057e1be721e70b","datavalue":{"value":{"amount":"+0.86018264","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1114387$C9B90AE3-2653-4575-BBE5-043B6B27C540","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f56a59ba863431bed6562238e3eb211ddd14ed1e","datavalue":{"value":{"entity-type":"item","numeric-id":3569877,"id":"Q3569877"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"95d9a62e3e342c62e78b6095eee68019d23ae864","datavalue":{"value":{"amount":"+0.8562837","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1114387$3C708D3A-599D-4520-BC68-94F717BF77E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6e285e24390602478c4aed06c61752d0510ec51c","datavalue":{"value":{"entity-type":"item","numeric-id":4535040,"id":"Q4535040"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"009447ede90ff31a7955d62cb5a4aaeecd675911","datavalue":{"value":{"amount":"+0.8548546","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1114387$BC33E926-4095-4105-8D79-6EA780C47901","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2ccd6b07a668507ed2db1d7beadd5ed1f44fda75","datavalue":{"value":{"entity-type":"item","numeric-id":5249052,"id":"Q5249052"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"74711bc8b039e3cbdf1abf5c7d645738a68f5b92","datavalue":{"value":{"amount":"+0.8539543","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1114387$6A543BC9-5600-460A-993B-A63CD5578083","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"245727bb294e1da3b214ba19f81f4fbc8240474e","datavalue":{"value":{"entity-type":"item","numeric-id":5482923,"id":"Q5482923"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6eb9ee4de96197b024ba1b0447b9131c014e93bf","datavalue":{"value":{"amount":"+0.84543675","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1114387$6D95654A-F637-4E87-884B-DCB647FD9D78","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1114387","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1114387"}}}}}