{"id":298823,"date":"2020-02-17T21:00:13","date_gmt":"2020-02-17T21:00:13","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=298823"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=298823","title":{"rendered":"\u0421\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0434\u0430\u043d\u043d\u044b\u0445: \u0441\u043f\u0438\u0441\u043e\u043a, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0443\u043c\u0435\u0435\u0442 \u0432\u0441\u0451*"},"content":{"rendered":"\n<div class=\"post__text post__text-html\" id=\"post-content-body\" data-io-article-url=\"https:\/\/habr.com\/ru\/post\/488778\/\"><i>* \u041f\u043e\u0434 \u0432\u0441\u0451 \u0438\u043c\u0435\u0435\u0442\u0441\u044f \u0432 \u0432\u0438\u0434\u0443 \u043e\u0442\u043d\u043e\u0441\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0431\u044b\u0441\u0442\u0440\u043e\u0435 \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u0435 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u043d\u0430\u0434 \u0435\u0434\u0438\u043d\u0438\u0447\u043d\u044b\u043c \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u043c \u043c\u0430\u0441\u0441\u0438\u0432\u0430.<\/i><\/p>\n<p>  \u0421\u0442\u0440\u0443\u043a\u0442\u0443\u0440 \u0434\u0430\u043d\u043d\u044b\u0445, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0440\u0435\u0430\u043b\u0438\u0437\u0443\u044e\u0442 \u0441\u043f\u0438\u0441\u043e\u043a \u043f\u043e\u043b\u043d\u043e. \u0423 \u0432\u0441\u0435\u0445 \u0435\u0441\u0442\u044c \u0441\u0432\u043e\u0438 \u0434\u043e\u0441\u0442\u043e\u0438\u043d\u0441\u0442\u0432\u0430 \u0438 \u043d\u0435\u0434\u043e\u0441\u0442\u0430\u0442\u043a\u0438. \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440 \u0432 \u043c\u0438\u0440\u0435 Java \u2014 \u0432 \u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u0438 \u043e\u0442 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u044b\u0445 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u2014 \u043c\u043e\u0436\u043d\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c:  <\/p>\n<ul>\n<li>add(obj), get(obj), set(index, obj): \u0431\u0430\u0437\u043e\u0432\u044b\u0439 \u043d\u0430\u0431\u043e\u0440 \u043f\u043e\u0447\u0442\u0438 \u0432\u0441\u0435\u0445 \u0441\u043f\u0438\u0441\u043a\u043e\u0432, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440 ArrayList. <\/li>\n<li>add(index, obj): \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0432 \u0432\u0438\u0434\u0435 \u0434\u0435\u0440\u0435\u0432\u0430, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440 TreeList \u0438\u0437 apache common-collections. <\/li>\n<li>remove(index): \u0442\u043e \u0436\u0435, \u0447\u0442\u043e \u0438 \u0432\u044b\u0448\u0435. <\/li>\n<li>contains(obj), indexOf(obj): \u043c\u043e\u0436\u043d\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0441\u0432\u044f\u0437\u043a\u0443 ArrayList \u0438 HashMap. <\/li>\n<li>remove(obj): \u2026 \u0437\u0430\u0442\u0440\u0443\u0434\u043d\u044f\u044e\u0441\u044c \u043e\u0442\u0432\u0435\u0442\u0438\u0442\u044c. \u0412 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0441\u043b\u0443\u0447\u0430\u044f\u0445 \u043c\u043e\u0436\u043d\u043e \u043e\u0431\u043e\u0439\u0442\u0438\u0441\u044c LinkedHashSet. \u0420\u0435\u0448\u0430\u0435\u0442\u0441\u044f \u0442\u0440\u0438\u0432\u0438\u0430\u043b\u044c\u043d\u043e \u043f\u0440\u0438 \u043d\u0430\u043b\u0438\u0447\u0438\u0438 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0438\u0445 \u0434\u0432\u0443\u0445 \u043f\u0443\u043d\u043a\u0442\u043e\u0432, \u043d\u043e \u043a\u0430\u043a\u0438\u0435 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u043c\u043e\u0433\u0443\u0442 \u0438 \u0442\u043e \u0438 \u0434\u0440\u0443\u0433\u043e\u0435 \u0431\u044b\u0441\u0442\u0440\u043e? <\/li>\n<\/ul>\n<p>  \u041a\u043e\u0433\u0434\u0430 \u043c\u043d\u0435 \u043f\u043e\u043d\u0430\u0434\u043e\u0431\u0438\u043b\u0430\u0441\u044c \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u0441 \u0431\u044b\u0441\u0442\u0440\u044b\u043c\u0438 add(obj), get(index), remove(index) \u0438 indexOf(obj), \u0442\u043e google \u043d\u0435 \u0434\u0430\u043b \u043e\u0442\u0432\u0435\u0442\u0430. \u041d\u0438 \u043f\u0440\u0438\u043c\u0435\u0440\u043e\u0432 \u043a\u043e\u0434\u0430, \u043d\u0438 \u043e\u043f\u0438\u0441\u0430\u043d\u0438\u044f \u043f\u043e\u0434\u043e\u0431\u043d\u044b\u0445 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440 \u044f \u043d\u0435 \u043d\u0430\u0448\u0435\u043b. \u0412\u043e\u0437\u043c\u043e\u0436\u043d\u043e \u043d\u0435 \u0442\u0430\u043c \u0438\u0441\u043a\u0430\u043b, \u043f\u0440\u0438\u0448\u043b\u043e\u0441\u044c \u0432\u044b\u0434\u0443\u043c\u044b\u0432\u0430\u0442\u044c \u0441\u0430\u043c\u043e\u043c\u0443. \u041d\u043e \u0435\u0441\u043b\u0438 \u043a\u0442\u043e-\u0442\u043e \u0441\u043a\u0438\u043d\u0435\u0442 \u0441\u0441\u044b\u043b\u043a\u0443 \u0432 \u043a\u043e\u043c\u043c\u0435\u043d\u0442\u0430\u0440\u0438\u044f\u0445, \u0442\u043e \u0431\u0443\u0434\u0443 \u0432\u0435\u0441\u044c\u043c\u0430 \u043f\u0440\u0438\u0437\u043d\u0430\u0442\u0435\u043b\u0435\u043d.<\/p>\n<p>  \u0412\u043e\u0437\u043c\u043e\u0436\u043d\u043e, \u043a\u0442\u043e-\u0442\u043e \u0434\u043e\u0433\u0430\u0434\u0430\u043b\u0441\u044f, \u0447\u0442\u043e \u043c\u043e\u0436\u043d\u043e \u0432\u0437\u044f\u0442\u044c TreeList, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0443\u043c\u0435\u0435\u0442 \u0431\u044b\u0441\u0442\u0440\u043e \u0432\u0441\u0442\u0430\u0432\u043b\u044f\u0442\u044c\/\u0443\u0434\u0430\u043b\u044f\u0442\u044c \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0432 \u0441\u0435\u0440\u0435\u0434\u0438\u043d\u0435 \u0441\u043f\u0438\u0441\u043a\u0430 \u0438 \u0434\u043e\u0431\u0430\u0432\u0438\u0442\u044c \u043a \u043d\u0435\u043c\u0443 HashMap \u0438\u0437 \u043e\u0431\u044a\u0435\u043a\u0442\u0430 \u0432 \u0438\u043d\u0434\u0435\u043a\u0441 \u0432 TreeList \u0434\u043b\u044f \u0431\u044b\u0441\u0442\u0440\u043e\u0433\u043e \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u044f indexOf(obj). \u0418 \u044d\u0442\u043e \u0431\u0443\u0434\u0435\u0442 \u043f\u0440\u043e\u0441\u0442\u043e\u0435, \u0438\u0437\u044f\u0449\u043d\u043e\u0435, \u043d\u043e \u043d\u0435\u0432\u0435\u0440\u043d\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435. \u0412\u0435\u0434\u044c \u043f\u0440\u0438 \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u0438 \u0432 \u0441\u0435\u0440\u0435\u0434\u0438\u043d\u0443 \u0438\u043b\u0438 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u0438 \u0438\u0437 \u0441\u0435\u0440\u0435\u0434\u0438\u043d\u044b \u043d\u0443\u0436\u043d\u043e \u0431\u0443\u0434\u0435\u0442 \u043f\u0435\u0440\u0435\u0441\u0447\u0438\u0442\u0430\u0442\u044c \u0438\u043d\u0434\u0435\u043a\u0441\u044b, \u0432 \u0441\u0440\u0435\u0434\u043d\u0435\u043c, \u0434\u043b\u044f \u043f\u043e\u043b\u043e\u0432\u0438\u043d\u044b \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432. \u042d\u0442\u043e \u0443\u0445\u0443\u0434\u0448\u0438\u0442 \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u0434\u043e O(n).<\/p>\n<p>  \u0414\u0430\u043b\u044c\u0448\u0435 \u044f \u0440\u0430\u0441\u0441\u043a\u0430\u0436\u0443 \u043e \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0435 \u0434\u0430\u043d\u043d\u044b\u0445, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043c\u043e\u0436\u0435\u0442 \u0432\u0441\u0451 \u0438\u0437 \u043f\u0435\u0440\u0435\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u043e\u0433\u043e \u0432\u044b\u0448\u0435. \u041a\u043e\u0442\u043e\u0440\u0430\u044f \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442 \u043b\u044e\u0431\u0443\u044e \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044e \u043d\u0430\u0434 \u043e\u0434\u043d\u0438\u043c \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u043c \u0437\u0430 O(log(n)) \u0432\u0440\u0435\u043c\u0435\u043d\u0438. \u041d\u0443 \u043f\u043e\u0447\u0442\u0438 \u2014 \u0437\u0430 \u043b\u043e\u0433\u0430\u0440\u0438\u0444\u043c \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442\u0441\u044f \u0432 \u0442\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435, \u043a\u043e\u0433\u0434\u0430 \u0432\u0441\u0435 \u043e\u0431\u044a\u0435\u043a\u0442\u044b \u0432 \u0441\u043f\u0438\u0441\u043a\u0435 \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b. \u0415\u0441\u043b\u0438 \u0432 \u0441\u043f\u0438\u0441\u043a\u0435 \u0435\u0441\u0442\u044c \u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u044b\u0435 \u043e\u0431\u044a\u0435\u043a\u0442\u044b, \u0442\u043e \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e \u043f\u0440\u043e\u0441\u0435\u0434\u0430\u043d\u0438\u0435 \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u0432\u043f\u043b\u043e\u0442\u044c \u0434\u043e O(log(n) ^ 2).<br \/>  <a name=\"habracut\"><\/a><\/p>\n<p>  \u041f\u0440\u0435\u0434\u0443\u043f\u0440\u0435\u0436\u0443 \u0441\u0440\u0430\u0437\u0443, \u0447\u0442\u043e \u044f \u043d\u0435 \u0431\u0443\u0434\u0443 \u0437\u0434\u0435\u0441\u044c \u0440\u0430\u0441\u043f\u0438\u0441\u044b\u0432\u0430\u0442\u044c \u043a\u043e\u0434. \u041e\u043d \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u0441\u043b\u043e\u0436\u0435\u043d \u0434\u043b\u044f \u0441\u0442\u0430\u0442\u044c\u0438. \u041d\u043e \u043e\u043d \u0435\u0441\u0442\u044c, \u043d\u0430\u043f\u0438\u0441\u0430\u043d \u043d\u0430 Java. \u0417\u0430 \u043e\u0441\u043d\u043e\u0432\u0443 \u0432\u0437\u044f\u0442 \u043a\u043b\u0430\u0441\u0441 TreeList \u0438\u0437 apache common-collections. Pull request \u0443\u0436\u0435 \u0435\u0441\u0442\u044c, \u043d\u043e \u043d\u0430 \u043c\u043e\u043c\u0435\u043d\u0442 \u043d\u0430\u043f\u0438\u0441\u0430\u043d\u0438\u044f \u0441\u0442\u0430\u0442\u044c\u0438 \u0435\u0449\u0451 \u043d\u0435 \u0432\u043b\u0438\u0442.<\/p>\n<p>  \u0422\u0430\u043a\u0436\u0435 \u044f \u043d\u0435 \u0431\u0443\u0434\u0443 \u043e\u043f\u0438\u0441\u044b\u0432\u0430\u0442\u044c \u043e\u0431\u0449\u0435\u0438\u0437\u0432\u0435\u0441\u0442\u043d\u044b\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b. \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u043e\u0432\u043a\u0438 \u0434\u0435\u0440\u0435\u0432\u0430. \u0411\u043e\u043b\u044c\u0448\u0438\u043d\u0441\u0442\u0432\u0443 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u043f\u0440\u0438\u043d\u044f\u0442\u044c \u043d\u0430 \u0432\u0435\u0440\u0443 \u0442\u043e\u0442 \u0444\u0430\u043a\u0442, \u0447\u0442\u043e \u0434\u0435\u0440\u0435\u0432\u043e \u043c\u043e\u0436\u043d\u043e \u0434\u0435\u0440\u0436\u0430\u0442\u044c \u0441\u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u043c. \u041d\u0430 \u043f\u043e\u043d\u0438\u043c\u0430\u043d\u0438\u0435 \u043e\u0431\u0449\u0435\u0439 \u0438\u0434\u0435\u0438 \u044d\u0442\u043e \u043d\u0438\u043a\u0430\u043a \u043d\u0435 \u0432\u043b\u0438\u044f\u0435\u0442. \u0422\u0435, \u043a\u0442\u043e \u0437\u0430\u0445\u043e\u0442\u044f\u0442 \u0443\u0437\u043d\u0430\u0442\u044c \u0431\u043e\u043b\u044c\u0448\u0435, \u0431\u0435\u0437 \u043f\u0440\u043e\u0431\u043b\u0435\u043c \u043d\u0430\u0439\u0434\u0443\u0442 \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u044e. \u041d\u043e \u043e \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0431\u0430\u0437\u043e\u0432\u044b\u0445 \u0432\u0435\u0449\u0430\u0445 \u043e\u0447\u0435\u043d\u044c \u043a\u043e\u0440\u043e\u0442\u043a\u043e \u0440\u0430\u0441\u0441\u043a\u0430\u0436\u0443, \u0442. \u043a. \u0431\u0435\u0437 \u0437\u043d\u0430\u043d\u0438\u044f \u043e\u0441\u043d\u043e\u0432 \u043d\u0435\u043b\u044c\u0437\u044f \u0431\u0443\u0434\u0435\u0442 \u043f\u043e\u043d\u044f\u0442\u044c \u043c\u043d\u043e\u0433\u0438\u0435 \u043a\u043b\u044e\u0447\u0435\u0432\u044b\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b.<\/p>\n<p>  \u0421\u0441\u044b\u043b\u043a\u0438 \u0431\u0443\u0434\u0443\u0442 \u0432 \u043a\u043e\u043d\u0446\u0435.<\/p>\n<h2>\u0417\u0430\u0447\u0435\u043c \u044d\u0442\u043e \u043d\u0443\u0436\u043d\u043e<\/h2>\n<p>  \u0412 \u0441\u0430\u043c\u043e\u043c \u0434\u0435\u043b\u0435, \u043d\u0435 \u0442\u0430\u043a-\u0442\u043e \u043f\u0440\u043e\u0441\u0442\u043e \u043f\u0440\u0438\u0434\u0443\u043c\u0430\u0442\u044c \u0441\u0438\u0442\u0443\u0430\u0446\u0438\u0438, \u043a\u043e\u0433\u0434\u0430 \u043e\u0442 \u0441\u043f\u0438\u0441\u043a\u0430 \u043d\u0443\u0436\u043d\u043e \u0432\u043e\u0442 \u043f\u0440\u044f\u043c \u0432\u043e\u043e\u0431\u0449\u0435 \u0432\u0441\u0451. \u0412\u0440\u044f\u0434 \u043b\u0438 \u044d\u0442\u043e \u043a\u0430\u043a\u0430\u044f-\u0442\u043e \u0441\u0443\u043f\u0435\u0440 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u0430\u044f \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430, \u0438\u043d\u0430\u0447\u0435 \u043e \u043d\u0435\u0439 \u0437\u043d\u0430\u043b\u0438 \u0431\u044b \u0432\u0441\u0435. \u041e\u0434\u043d\u0430\u043a\u043e \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u043f\u0440\u0438\u043c\u0435\u0440\u043e\u0432, \u0433\u0434\u0435 \u0442\u0430\u043a\u043e\u0439 \u0441\u043f\u0438\u0441\u043e\u043a \u043c\u043e\u0433 \u0431\u044b\u0442\u044c \u043f\u043e\u043b\u0435\u0437\u0435\u043d \u043c\u043e\u0436\u043d\u043e \u043f\u0440\u0438\u0432\u0435\u0441\u0442\u0438.<\/p>\n<p>  \u042f \u043e\u0441\u043e\u0437\u043d\u0430\u044e, \u0447\u0442\u043e \u043c\u043d\u043e\u0433\u0438\u0435 \u0438\u0437 \u043f\u0440\u0438\u043c\u0435\u0440\u043e\u0432 \u043d\u0430\u0434\u0443\u043c\u0430\u043d\u043d\u044b\u0435. \u0412\u0441\u0451 \u0438\u043b\u0438 \u043f\u043e\u0447\u0442\u0438 \u0432\u0441\u0451 \u043c\u043e\u0436\u043d\u043e \u0440\u0435\u0448\u0438\u0442\u044c \u0434\u0440\u0443\u0433\u0438\u043c \u0441\u043f\u043e\u0441\u043e\u0431\u043e\u043c.<\/p>\n<h3>\u041a\u044d\u0448\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435 \u0438 \u0441\u0436\u0430\u0442\u0438\u0435<\/h3>\n<p>  \u041c\u043e\u044f \u043f\u0435\u0440\u0432\u043e\u043d\u0430\u0447\u0430\u043b\u044c\u043d\u0430\u044f \u0437\u0430\u0434\u0430\u0447\u0430, \u0438\u0437-\u0437\u0430 \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u044f \u043d\u0430\u0447\u0430\u043b \u0438\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u044c \u0432\u043e\u043f\u0440\u043e\u0441. \u0418\u0433\u0440\u0430\u043b\u0441\u044f \u0441\u043e \u0441\u0436\u0430\u0442\u0438\u0435\u043c \u0441\u043f\u0435\u0446\u0438\u0444\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u0434\u0430\u043d\u043d\u044b\u0445 \u0438 \u043f\u043e\u043d\u0430\u0434\u043e\u0431\u0438\u043b\u0441\u044f \u0441\u043f\u0438\u0441\u043e\u043a \u0434\u043b\u044f \u043a\u044d\u0448\u0430 \u043e\u0431\u044a\u0435\u043a\u0442\u043e\u0432. <\/p>\n<p>  \u0418\u0434\u0435\u044f \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0430\u044f: \u043f\u0440\u0438 \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u043a\u0435 \u043e\u0447\u0435\u0440\u0435\u0434\u043d\u043e\u0433\u043e \u043e\u0431\u044a\u0435\u043a\u0442\u0430 \u0438\u0449\u0435\u043c \u0435\u0433\u043e \u0432 \u0441\u043f\u0438\u0441\u043a\u0435. \u0415\u0441\u043b\u0438 \u043d\u0435 \u043d\u0430\u0448\u043b\u0438 \u2014 \u0441\u043e\u0445\u0440\u0430\u043d\u044f\u0435\u043c \u043e\u0431\u044a\u0435\u043a\u0442 \u0438 \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c \u0435\u0433\u043e \u0432 \u043d\u0430\u0447\u0430\u043b\u043e \u0441\u043f\u0438\u0441\u043a\u0430. \u0415\u0441\u043b\u0438 \u043d\u0430\u0448\u043b\u0438, \u0442\u043e \u0431\u0435\u0440\u0451\u043c \u0435\u0433\u043e \u0438\u043d\u0434\u0435\u043a\u0441 \u0432 \u0441\u043f\u0438\u0441\u043a\u0435 \u0438 \u0432\u043c\u0435\u0441\u0442\u043e \u043e\u0431\u044a\u0435\u043a\u0442\u0430 \u0441\u043e\u0445\u0440\u0430\u043d\u044f\u0435\u043c \u0442\u043e\u043b\u044c\u043a\u043e \u0435\u0433\u043e \u0438\u043d\u0434\u0435\u043a\u0441, \u043f\u043e\u0441\u043b\u0435 \u0447\u0435\u0433\u043e \u043f\u0435\u0440\u0435\u043c\u0435\u0449\u0430\u0435\u043c \u043e\u0431\u044a\u0435\u043a\u0442 \u0432 \u043d\u0430\u0447\u0430\u043b\u043e \u0441\u043f\u0438\u0441\u043a\u0430. \u0422\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, \u043e\u0431\u044a\u0435\u043a\u0442\u044b, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0432\u0441\u0442\u0440\u0435\u0447\u0430\u044e\u0442\u0441\u044f \u0447\u0430\u0441\u0442\u043e \u0431\u0443\u0434\u0443\u0442 \u043f\u043e\u043b\u0443\u0447\u0430\u0442\u044c \u043c\u0430\u043b\u0435\u043d\u044c\u043a\u0438\u0435 \u0438\u043d\u0434\u0435\u043a\u0441\u044b, \u0430 \u043e\u0431\u044a\u0435\u043a\u0442\u044b, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0432\u0441\u0442\u0440\u0435\u0442\u0438\u043b\u0438\u0441\u044c \u0432\u0441\u0435\u0433\u043e \u043e\u0434\u0438\u043d \u0440\u0430\u0437, \u0441\u043e \u0432\u0440\u0435\u043c\u0435\u043d\u0435\u043c \u043f\u0435\u0440\u0435\u043c\u0435\u0449\u0430\u044e\u0442\u0441\u044f \u0432 \u043a\u043e\u043d\u0435\u0446 \u0441\u043f\u0438\u0441\u043a\u0430 \u0438 \u0443\u0434\u0430\u043b\u044f\u044e\u0442\u0441\u044f.<\/p>\n<h3>\u041e\u0447\u0435\u0440\u0435\u0434\u044c<\/h3>\n<p>  \u0415\u0441\u043b\u0438 \u0432\u043c\u0435\u0441\u0442\u043e \u043e\u0431\u044b\u0447\u043d\u043e\u0439 FIFO \u043e\u0447\u0435\u0440\u0435\u0434\u0438 \u0434\u043b\u044f \u043a\u0430\u043a\u0438\u0445-\u0442\u043e \u0437\u0430\u0434\u0430\u0447 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u043f\u043e\u0434\u043e\u0431\u043d\u0443\u044e \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0443, \u0442\u043e \u043c\u043e\u0436\u043d\u043e \u0434\u0435\u043b\u0430\u0442\u044c \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0435 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438:  <\/p>\n<ul>\n<li>\u041e\u0442\u0432\u0435\u0447\u0430\u0442\u044c \u043d\u0430 \u0432\u043e\u043f\u0440\u043e\u0441: \u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0437\u0430\u0434\u0430\u0447 \u0432 \u043e\u0447\u0435\u0440\u0435\u0434\u0438 \u043f\u0435\u0440\u0435\u0434 \u0434\u0430\u043d\u043d\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0435\u0439. <\/li>\n<li>\u0423\u0434\u0430\u043b\u044f\u0442\u044c \u0437\u0430\u0434\u0430\u0447\u0438 \u0438\u0437 \u043e\u0447\u0435\u0440\u0435\u0434\u0438. <\/li>\n<\/ul>\n<p>  \u041f\u0440\u0438\u043c\u0435\u0440\u043d\u043e \u043a\u0430\u043a \u0432 \u0441\u0443\u043f\u0435\u0440\u043c\u0430\u0440\u043a\u0435\u0442\u0435. \u0415\u0441\u043b\u0438 \u0432\u044b \u043f\u0440\u0438\u0448\u043b\u0438 \u0437\u0430 \u0448\u043e\u043a\u043e\u043b\u0430\u0434\u043a\u043e\u0439, \u043d\u043e \u0432\u0438\u0434\u0438\u0442\u0435, \u0447\u0442\u043e \u043e\u0447\u0435\u0440\u0435\u0434\u044c \u0434\u0432\u0438\u0433\u0430\u0435\u0442\u0441\u044f \u043c\u0435\u0434\u043b\u0435\u043d\u043d\u043e, \u0442\u043e, \u043c\u043e\u0436\u0435\u0442, \u0448\u043e\u043a\u043e\u043b\u0430\u0434\u043a\u0430 \u043d\u0435 \u0442\u0430\u043a \u0443\u0436 \u0441\u0438\u043b\u044c\u043d\u043e \u0438 \u043d\u0443\u0436\u043d\u0430? \ud83d\ude42<\/p>\n<h3>\u0422\u0430\u0431\u043b\u0438\u0446\u0430 \u0440\u0435\u043a\u043e\u0440\u0434\u043e\u0432<\/h3>\n<p>  \u0414\u043e\u043f\u0443\u0441\u0442\u0438\u043c, \u043c\u044b \u0445\u043e\u0442\u0438\u043c \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u0432\u0440\u0435\u043c\u044f, \u0437\u0430 \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u0438\u0433\u0440\u043e\u043a\u0438 \u043f\u0440\u043e\u0445\u043e\u0434\u044f\u0442 \u0443\u0440\u043e\u0432\u0435\u043d\u044c \u0432 \u043a\u0430\u043a\u043e\u0439-\u0442\u043e \u0438\u0433\u0440\u0435. \u0418\u0433\u0440\u043e\u043a\u043e\u0432 \u043c\u043d\u043e\u0433\u043e \u0438 \u0432\u0441\u0435 \u043e\u043d\u0438 \u0441\u043e\u0440\u0435\u0432\u043d\u0443\u044e\u0442\u0441\u044f, \u043f\u044b\u0442\u0430\u044f\u0441\u044c \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u044c \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u0432\u0440\u0435\u043c\u044f. \u0414\u0430\u043d\u043d\u044b\u0435 \u0438\u0433\u0440\u043e\u043a\u043e\u0432 \u043c\u043e\u0436\u043d\u043e \u043f\u043e\u043b\u043e\u0436\u0438\u0442\u044c \u0432 \u043c\u0430\u0441\u0441\u0438\u0432 \u0438 \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u043f\u043e \u0432\u0440\u0435\u043c\u0435\u043d\u0438. \u041f\u043e\u043b\u044c\u0437\u0443\u044f\u0441\u044c \u0434\u0430\u043d\u043d\u043e\u0439 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u043e\u0439 \u043c\u043e\u0436\u043d\u043e:  <\/p>\n<ul>\n<li>\u041f\u0435\u0440\u0435\u043c\u0435\u0449\u0430\u0442\u044c \u0438\u0433\u0440\u043e\u043a\u043e\u0432 \u0432\u044b\u0448\u0435 \u043f\u043e \u0441\u043f\u0438\u0441\u043a\u0443, \u0435\u0441\u043b\u0438 \u043e\u043d\u0438 \u043f\u043e\u043a\u0430\u0437\u0430\u043b\u0438 \u043b\u0443\u0447\u0448\u0438\u0439 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442, \u0447\u0435\u043c \u0440\u0430\u043d\u044c\u0448\u0435. <\/li>\n<li>\u0423\u0434\u0430\u043b\u044f\u0442\u044c \u0438\u0433\u0440\u043e\u043a\u043e\u0432 \u0438\u0437 \u0441\u043f\u0438\u0441\u043a\u0430, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0432 \u0441\u043b\u0443\u0447\u0430\u0435 \u0431\u0430\u043d\u0430 \u0437\u0430 \u0447\u0438\u0442\u0435\u0440\u0441\u0442\u0432\u043e. <\/li>\n<li>\u041f\u043e\u043a\u0430\u0437\u044b\u0432\u0430\u0442\u044c \u043a\u0430\u0436\u0434\u043e\u043c\u0443 \u0438\u0433\u0440\u043e\u043a\u0443 \u043d\u0430 \u043a\u0430\u043a\u043e\u043c \u043e\u043d \u043c\u0435\u0441\u0442\u0435. <\/li>\n<li>\u041f\u043e\u0441\u0442\u0440\u0430\u043d\u0438\u0447\u043d\u043e \u043f\u043e\u043a\u0430\u0437\u044b\u0432\u0430\u0442\u044c \u0442\u0430\u0431\u043b\u0438\u0446\u0443 \u0440\u0435\u043a\u043e\u0440\u0434\u043e\u0432. <\/li>\n<li>\u041f\u043e\u043a\u0430\u0437\u044b\u0432\u0430\u0442\u044c \u0440\u0430\u0437\u0440\u0435\u0436\u0435\u043d\u043d\u0443\u044e \u0442\u0430\u0431\u043b\u0438\u0446\u0443 \u043f\u043e \u043c\u0435\u0441\u0442\u0430\u043c, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440 \u0432\u0440\u0435\u043c\u044f 1, 2, 3, 5, 10, 20, 50, 100, 1000, 10000 \u043c\u0435\u0441\u0442\u0430. <\/li>\n<\/ul>\n<h2>\u0421\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u0434\u0430\u043d\u043d\u044b\u0445<\/h2>\n<p>  \u0421\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u0430 \u043d\u0430 \u0434\u0435\u0440\u0435\u0432\u0435 \u0441 \u043d\u0435\u044f\u0432\u043d\u044b\u043c \u043a\u043b\u044e\u0447\u043e\u043c. \u0418\u043c\u0435\u043d\u043d\u043e \u043d\u0430 \u044d\u0442\u043e\u043c \u043f\u043e\u0434\u0445\u043e\u0434\u0435 \u043e\u0441\u043d\u043e\u0432\u0430\u043d, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, TreeList \u0432 apache common-collections. \u0414\u043b\u044f \u0442\u043e\u0433\u043e \u0447\u0442\u043e\u0431\u044b \u0434\u0432\u0438\u0433\u0430\u0442\u044c\u0441\u044f \u0434\u0430\u043b\u044c\u0448\u0435, \u043d\u0430\u0434\u043e \u043f\u043e\u043d\u044f\u0442\u044c \u043a\u0430\u043a \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u044d\u0442\u0430 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430.<\/p>\n<h3>\u0414\u0435\u0440\u0435\u0432\u043e \u0441 \u043d\u0435\u044f\u0432\u043d\u044b\u043c \u043a\u043b\u044e\u0447\u043e\u043c<\/h3>\n<p>  \u0414\u0435\u0440\u0435\u0432\u043e \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0438\u0437 \u0443\u0437\u043b\u043e\u0432 (Nodes). \u041a\u0430\u0436\u0434\u044b\u0439 \u0443\u0437\u0435\u043b \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u0441\u0441\u044b\u043b\u043a\u0443 \u043d\u0430 \u043e\u0431\u044a\u0435\u043a\u0442, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0445\u0440\u0430\u043d\u0438\u0442\u0441\u044f \u0432 \u0443\u0437\u043b\u0435 \u0438 2 \u0441\u0441\u044b\u043b\u043a\u0438 \u043d\u0430 \u0434\u0440\u0443\u0433\u0438\u0435 \u0443\u0437\u043b\u044b: \u043b\u0435\u0432\u044b\u0439 \u0438 \u043f\u0440\u0430\u0432\u044b\u0439. \u0421\u0430\u043c\u044b\u0439 \u0432\u0435\u0440\u0445\u043d\u0438\u0439 \u0443\u0437\u0435\u043b \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u043a\u043e\u0440\u043d\u0435\u0432\u044b\u043c. \u0412 \u0441\u0430\u043c\u043e\u043c \u043f\u0440\u043e\u0441\u0442\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u0443\u0437\u0435\u043b \u0432\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u043f\u0440\u0438\u043c\u0435\u0440\u043d\u043e \u0442\u0430\u043a:  <\/p>\n<pre><code class=\"kotlin\">class Node&lt;T&gt; {   obj: T   left: Node&lt;T&gt;   right: Node&lt;T&gt; } <\/code><\/pre>\n<p>  \u0412 \u043a\u043b\u0430\u0441\u0441\u0438\u0447\u0435\u0441\u043a\u043e\u043c \u0431\u0438\u043d\u0430\u0440\u043d\u043e\u043c \u0434\u0435\u0440\u0435\u0432\u0435 \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0443\u0437\u043b\u0430 \u0432 \u043b\u0435\u0432\u043e\u043c \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u0435 \u0432\u0441\u0435 \u043e\u0431\u044a\u0435\u043a\u0442\u044b \u043c\u0435\u043d\u044c\u0448\u0438\u0435, \u0447\u0435\u043c \u0432 \u0442\u0435\u043a\u0443\u0449\u0435\u043c \u0443\u0437\u043b\u0435, \u0430 \u0432 \u043f\u0440\u0430\u0432\u043e\u043c \u2014 \u0431\u043e\u043b\u044c\u0448\u0438\u0435. \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440:  <\/p>\n<pre><code class=\"plaintext\">                             [ element: 25 ]                            \/                 \\                           \/                   \\           [ element: 14 ]                       [ element: 45 ]            \/          \\                           \/          \\           \/            \\                         \/            \\ [ element: 10 ]    [ element: 22 ]     [ element: 27 ]    [ element: 90 ]                     \/          \\                            \/                    \/            \\                          \/             [ element: 17 ] [ element: 23 ]         [ element: 80 ] <\/code><\/pre>\n<p>  \u041d\u043e \u0434\u043b\u044f \u043d\u0430\u0448\u0435\u0439 \u0446\u0435\u043b\u0438 \u0442\u0430\u043a\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e \u043d\u0435 \u043f\u043e\u0434\u0445\u043e\u0434\u0438\u0442. \u041d\u0430\u043c \u043d\u0435 \u043d\u0430\u0434\u043e \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u043e\u0431\u044a\u0435\u043a\u0442\u044b \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u043c\u0438, \u043d\u043e \u043d\u0430\u0434\u043e \u0438\u043c\u0435\u0442\u044c \u043a \u043d\u0438\u043c \u0434\u043e\u0441\u0442\u0443\u043f \u043f\u043e \u0438\u043d\u0434\u0435\u043a\u0441\u0443, \u043a\u0430\u043a \u0432 \u043c\u0430\u0441\u0441\u0438\u0432\u0435. <\/p>\n<p>  \u041a\u0430\u043a \u043c\u043e\u0436\u043d\u043e \u043f\u043e\u043c\u0435\u0441\u0442\u0438\u0442\u044c \u043c\u0430\u0441\u0441\u0438\u0432 \u0432 \u0434\u0435\u0440\u0435\u0432\u043e? \u0414\u0430\u0432\u0430\u0439\u0442\u0435 \u0432\u044b\u0431\u0435\u0440\u0435\u043c \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0441 \u0438\u043d\u0434\u0435\u043a\u0441\u043e\u043c i \u0438\u0437 \u0441\u0435\u0440\u0435\u0434\u0438\u043d\u044b \u043c\u0430\u0441\u0441\u0438\u0432\u0430. \u041f\u043e\u043c\u0435\u0441\u0442\u0438\u043c \u0432 \u043a\u043e\u0440\u043d\u0435\u0432\u043e\u0439 \u0443\u0437\u0435\u043b i-\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0438\u0437 \u043c\u0430\u0441\u0441\u0438\u0432\u0430. \u0418\u0437 \u043a\u043e\u0440\u043d\u0435\u0432\u043e\u0433\u043e \u0443\u0437\u043b\u0430 \u0432\u044b\u0445\u043e\u0434\u044f\u0442 2 \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u0430. \u0412 \u043b\u0435\u0432\u043e\u0435 \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u043e \u043f\u043e\u043c\u0435\u0449\u0430\u0435\u043c \u043f\u043e\u043b\u043e\u0432\u0438\u043d\u0443 \u043c\u0430\u0441\u0441\u0438\u0432\u0430 \u0441 \u0438\u043d\u0434\u0435\u043a\u0441\u043e\u043c &lt; i, \u0430 \u0432 \u043f\u0440\u0430\u0432\u0443\u044e \u0441 \u0438\u043d\u0434\u0435\u043a\u0441\u043e\u043c &gt; i. \u041a\u0430\u043a \u044d\u0442\u043e \u0441\u0434\u0435\u043b\u0430\u0442\u044c? \u0422\u043e\u0447\u043d\u043e \u0442\u0430\u043a \u0436\u0435: \u0432\u044b\u0431\u0438\u0440\u0430\u0435\u043c \u0432 \u043f\u043e\u0434\u043c\u0430\u0441\u0441\u0438\u0432\u0435 \u043a\u0430\u043a\u043e\u0439-\u0442\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0438\u0437 \u0441\u0435\u0440\u0435\u0434\u0438\u043d\u044b, \u043f\u043e\u043c\u0435\u0449\u0430\u0435\u043c \u044d\u0442\u043e\u0442 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0432 \u0443\u0437\u0435\u043b, \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u043c \u0435\u0449\u0435 2 \u043f\u043e\u0434\u043c\u0430\u0441\u0441\u0438\u0432\u0430 \u043f\u043e\u043c\u0435\u043d\u044c\u0448\u0435. \u0418 \u0442\u0430\u043a \u043f\u043e\u043a\u0430 \u043d\u0435 \u043f\u043e\u043c\u0435\u0441\u0442\u0438\u043c \u0432\u0441\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u043c\u0430\u0441\u0441\u0438\u0432\u0430 \u0432 \u0443\u0437\u043b\u044b \u0434\u0435\u0440\u0435\u0432\u0430.<\/p>\n<p>  \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0442\u0430\u043a \u043c\u043e\u0436\u0435\u0442 \u0432\u044b\u0433\u043b\u044f\u0434\u0435\u0442\u044c \u043c\u0430\u0441\u0441\u0438\u0432 \u0441 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430\u043c\u0438 [\u201cq\u201d, \u201cw\u201d, \u201ce\u201d, \u201cr\u201d, \u201ct\u201d, \u201cy\u201d, \u201cu\u201d]:  <\/p>\n<pre><code class=\"plaintext\">                            [el: r,  size: 7]                            \/        :        \\                           \/         :         \\          [el: w, size: 3]           :           [el: y, size: 3]            \/     :    \\             :             \/    :     \\           \/      :     \\            :            \/     :      \\ [el: q, size: 1] : [el: e, size: 1] : [el: t, size: 1] : [el: u, size: 1]         :        :         :        :         :        :         :         :        :         :        :         :        :         :        [q]      [w]       [e]      [r]       [t]      [y]       [u]  Index:  0        1         2        3         4        5         6<\/code><\/pre>\n<p>  \u0421\u0440\u0435\u0434\u043d\u0438\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0432 \u043c\u0430\u0441\u0441\u0438\u0432\u0435 \u201cr\u201d, \u0435\u0433\u043e \u043f\u043e\u043c\u0435\u0449\u0430\u0435\u043c \u0432 \u043a\u043e\u0440\u043d\u0435\u0432\u043e\u0439 \u0443\u0437\u0435\u043b. \u0414\u0432\u0430 \u043f\u043e\u0434\u043c\u0430\u0441\u0441\u0438\u0432\u0430 [\u201cq\u201d, \u201cw\u201d, \u201ce\u201d] \u0438 [\u201ct\u201d, \u201cy\u201d, \u201cu\u201d] \u043f\u043e\u043c\u0435\u0449\u0430\u044e\u0442\u0441\u044f \u0432 \u043b\u0435\u0432\u043e\u0435 \u0438 \u043f\u0440\u0430\u0432\u043e\u0435 \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u043e. \u0414\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u0438\u0437 \u043f\u043e\u0434\u043c\u0430\u0441\u0441\u0438\u0432\u043e\u0432 \u0432\u044b\u0431\u0438\u0440\u0430\u044e\u0442\u0441\u044f \u0446\u0435\u043d\u0442\u0440\u0430\u043b\u044c\u043d\u044b\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b, \u0432 \u043d\u0430\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u044d\u0442\u043e \u201cw\u201d \u0438 \u201cy\u201d, \u043e\u043d\u0438 \u0438 \u043f\u043e\u043f\u0430\u0434\u0430\u044e\u0442 \u0432 \u0443\u0437\u043b\u044b \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0433\u043e \u0443\u0440\u043e\u0432\u043d\u044f. \u0418 \u0442. \u0434.<\/p>\n<p>  \u0412 \u043d\u0430\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u0434\u0435\u0440\u0435\u0432\u043e \u0441\u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u043e\u0432\u0430\u043d\u043e, \u0433\u043b\u0443\u0431\u0438\u043d\u0430 \u0432\u0441\u0435\u0445 \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u044c\u0435\u0432 \u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u0430\u044f. \u041d\u043e \u044d\u0442\u043e \u043d\u0435 \u043e\u0431\u044f\u0437\u0430\u0442\u0435\u043b\u044c\u043d\u043e \u0434\u043e\u043b\u0436\u043d\u043e \u0431\u044b\u0442\u044c \u0442\u0430\u043a. <\/p>\n<p>  \u041d\u0430 \u043a\u0430\u0440\u0442\u0438\u043d\u043a\u0435 \u0432\u044b\u0448\u0435 \u043a\u0430\u0436\u0434\u044b\u0439 \u0443\u0437\u0435\u043b \u043f\u043e\u043c\u0438\u043c\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u0438 \u0441\u0441\u044b\u043b\u043e\u043a \u043d\u0430 \u043b\u0435\u0432\u044b\u0439 \u0438 \u043f\u0440\u0430\u0432\u044b\u0435 \u0443\u0437\u043b\u044b \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0432\u0441\u0435\u0433\u043e \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u0430. \u042d\u0442\u0443 \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u044e \u043d\u0430\u0434\u043e \u043f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u043e \u043e\u0431\u043d\u043e\u0432\u043b\u044f\u0442\u044c \u043f\u0440\u0438 \u0438\u0437\u043c\u0435\u043d\u0435\u043d\u0438\u0438 \u0434\u0435\u0440\u0435\u0432\u0430.<\/p>\n<p>  \u0414\u0430\u0432\u0430\u0439\u0442\u0435 \u043f\u043e\u0441\u043c\u043e\u0442\u0440\u0438\u043c, \u043a\u0430\u043a \u0432 \u0442\u0430\u043a\u043e\u043c \u0434\u0435\u0440\u0435\u0432\u0435 \u043d\u0430\u0439\u0442\u0438, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0441 index = 4. <br \/>  \u041c\u044b \u043d\u0430\u0447\u0438\u043d\u0430\u0435\u043c \u043e\u0431\u0445\u043e\u0434 \u0441 \u043a\u043e\u0440\u043d\u0435\u0432\u043e\u0433\u043e \u0443\u0437\u043b\u0430 (root, \u0432 \u043d\u0430\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u0441 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u043c \u201cr\u201d). \u0423 \u043d\u0430\u0441 \u0435\u0441\u0442\u044c 3 \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u0430: \u043c\u044b \u0443\u0436\u0435 \u043d\u0430\u0445\u043e\u0434\u0438\u043c\u0441\u044f \u043d\u0430 \u043d\u0443\u0436\u043d\u043e\u043c \u0443\u0437\u043b\u0435, \u043d\u0443\u0436\u043d\u044b\u0439 \u0443\u0437\u0435\u043b \u0441\u043b\u0435\u0432\u0430, \u043d\u0443\u0436\u043d\u044b\u0439 \u0443\u0437\u0435\u043b \u0441\u043f\u0440\u0430\u0432\u0430. \u0414\u043b\u044f \u0442\u043e\u0433\u043e \u0447\u0442\u043e\u0431\u044b \u043f\u043e\u043d\u044f\u0442\u044c, \u0433\u0434\u0435 \u0438\u0441\u043a\u0430\u0442\u044c \u043d\u0443\u0436\u043d\u044b\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442, \u043d\u0443\u0436\u043d\u043e \u0441\u0440\u0430\u0432\u043d\u0438\u0442\u044c \u0440\u0430\u0437\u043c\u0435\u0440 \u043b\u0435\u0432\u043e\u0433\u043e \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u0430 (\u0432 \u043d\u0430\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435 left.size = 3) \u0438 \u0442\u0435\u043a\u0443\u0449\u0438\u0439 \u0438\u043d\u0434\u0435\u043a\u0441 (\u0432 \u043d\u0430\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435 4). \u0415\u0441\u043b\u0438 \u044d\u0442\u0438 2 \u0447\u0438\u0441\u043b\u0430 \u0440\u0430\u0432\u043d\u044b, \u0442\u043e \u043c\u044b \u043d\u0430\u0448\u043b\u0438 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u044b\u0439 \u0443\u0437\u0435\u043b \u0438 \u0438\u0441\u043a\u043e\u043c\u044b\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0432 \u043d\u0451\u043c. \u0415\u0441\u043b\u0438 \u0440\u0430\u0437\u043c\u0435\u0440 \u043b\u0435\u0432\u043e\u0433\u043e \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u0430 \u0431\u043e\u043b\u044c\u0448\u0435, \u0442\u043e \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u044b\u0439 \u0443\u0437\u0435\u043b \u0432 \u043b\u0435\u0432\u043e\u043c \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u0435. \u0415\u0441\u043b\u0438 \u043c\u0435\u043d\u044c\u0448\u0435, \u0442\u043e \u043d\u0430\u0434\u043e \u0438\u0441\u043a\u0430\u0442\u044c \u0432 \u043f\u0440\u0430\u0432\u043e\u043c \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u0435, \u043d\u043e \u043d\u0443\u0436\u043d\u043e \u0443\u043c\u0435\u043d\u044c\u0448\u0438\u0442\u044c \u0438\u0441\u043a\u043e\u043c\u044b\u0439 \u0438\u043d\u0434\u0435\u043a\u0441: index = index \u2014 left.size \u2014 1.<br \/>  \u041f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 \u0432 \u043d\u0430\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435 left.size &lt; index, \u0442\u043e \u043c\u044b \u0438\u0449\u0435\u043c \u0432 \u043f\u0440\u0430\u0432\u043e\u043c \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0441 \u043d\u043e\u0432\u044b\u043c \u0438\u043d\u0434\u0435\u043a\u0441\u043e\u043c 4 \u2014 3 \u2014 1 = 0. \u041f\u0435\u0440\u0435\u043c\u0435\u0449\u0430\u0435\u043c\u0441\u044f \u043a \u0443\u0437\u043b\u0443 \u0441 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u043c \u201cy\u201d.<br \/>  \u0414\u0430\u043b\u044c\u0448\u0435 \u0434\u0435\u043b\u0430\u0435\u043c \u0442\u043e \u0436\u0435 \u0441\u0430\u043c\u043e\u0435, \u0447\u0442\u043e \u0434\u0435\u043b\u0430\u043b\u0438 \u0432 \u043a\u043e\u0440\u043d\u0435\u0432\u043e\u043c \u0443\u0437\u043b\u0435. \u0421\u0440\u0430\u0432\u043d\u0438\u0432\u0430\u0435\u043c left.size \u0438 index. \u041f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 1 &gt; 0 \u0442\u043e \u0438\u0449\u0435\u043c \u0432 \u043b\u0435\u0432\u043e\u043c \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u0435, \u043f\u0435\u0440\u0435\u043c\u0435\u0449\u0430\u0435\u043c\u0441\u044f \u043a \u0443\u0437\u043b\u0443 \u0441 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u043c \u201ct\u201d.<br \/>  \u0412 \u044d\u0442\u043e\u043c \u0443\u0437\u043b\u0435 \u043d\u0435\u0442 \u043b\u0435\u0432\u043e\u0433\u043e \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u0430, \u0438 \u0435\u0433\u043e \u0440\u0430\u0437\u043c\u0435\u0440 \u0440\u0430\u0432\u0435\u043d 0. index = left.size, \u0430 \u0437\u043d\u0430\u0447\u0438\u0442 \u043c\u044b \u043d\u0430\u0448\u043b\u0438 \u0443\u0437\u0435\u043b \u0441 \u0438\u043d\u0434\u0435\u043a\u0441\u043e\u043c 4 \u0438 \u043c\u043e\u0436\u0435\u043c \u0434\u043e\u0441\u0442\u0430\u0442\u044c \u0438\u0437 \u043d\u0435\u0433\u043e \u0438\u0441\u043a\u043e\u043c\u044b\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u201ct\u201d.<\/p>\n<p>  \u0412 \u043f\u0441\u0435\u0432\u0434\u043e\u043a\u043e\u0434\u0435 \u044d\u0442\u043e \u0432\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u043f\u0440\u0438\u043c\u0435\u0440\u043d\u043e \u0442\u0430\u043a:  <\/p>\n<pre><code class=\"kotlin\">function get(node: Node&lt;T&gt;, index: int): T {   val leftSize: int = (node.left == null) ? 0 : node.left.size;   if (leftSize == index) {     return node.obj;   } else if (leftSize &gt; index) {     return get(node.left, index);   } else {     return get(node.right, index \u2014 leftSize \u2014 1);   } }<\/code><\/pre>\n<p>  \u042f \u043f\u043e\u0441\u0442\u0430\u0440\u0430\u043b\u0441\u044f \u043e\u043f\u0438\u0441\u0430\u0442\u044c \u043a\u043b\u044e\u0447\u0435\u0432\u043e\u0439 \u043f\u0440\u0438\u043d\u0446\u0438\u043f \u043a\u0430\u043a \u043f\u043e\u043c\u0435\u0441\u0442\u0438\u0442\u044c \u043c\u0430\u0441\u0441\u0438\u0432 \u0432 \u0434\u0435\u0440\u0435\u0432\u043e. \u0420\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u0442\u0430\u043a\u0430\u044f \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430, \u043a\u043e\u043d\u0435\u0447\u043d\u043e, \u043c\u0435\u0434\u043b\u0435\u043d\u043d\u0435\u0435 \u043a\u043b\u0430\u0441\u0441\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u043c\u0430\u0441\u0441\u0438\u0432\u0430, \u0437\u0430 O(log(n)) \u043f\u0440\u043e\u0442\u0438\u0432 O(1). \u041d\u043e \u0443 \u043d\u0435\u0451 \u0435\u0441\u0442\u044c \u0432\u0430\u0436\u043d\u043e\u0435 \u043f\u0440\u0435\u0438\u043c\u0443\u0449\u0435\u0441\u0442\u0432\u043e: \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u0432 \u0441\u0435\u0440\u0435\u0434\u0438\u043d\u0443 \u0438\u043b\u0438 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u0435 \u0438\u0437 \u0441\u0435\u0440\u0435\u0434\u0438\u043d\u044b \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u0442\u043e\u0436\u0435 \u0437\u0430 O(log(n)) \u043f\u0440\u043e\u0442\u0438\u0432 O(n) \u0443 \u043c\u0430\u0441\u0441\u0438\u0432\u0430. \u041a\u043e\u043d\u0435\u0447\u043d\u043e, \u043f\u0440\u0438 \u0443\u0441\u043b\u043e\u0432\u0438\u0438, \u0447\u0442\u043e \u0434\u0435\u0440\u0435\u0432\u043e \u0431\u043e\u043b\u0435\u0435-\u043c\u0435\u043d\u0435\u0435 \u0441\u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u043e\u0432\u0430\u043d\u043e. \u0421\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u043c\u043d\u043e\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432 \u043f\u043e\u0434\u0434\u0435\u0440\u0436\u0430\u043d\u0438\u044f \u0434\u0435\u0440\u0435\u0432\u0430 \u0432 \u043f\u043e\u0447\u0442\u0438 \u0441\u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u043c \u0432\u0438\u0434\u0435. \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u043a\u0440\u0430\u0441\u043d\u043e-\u0447\u0451\u0440\u043d\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e, AVL \u0434\u0435\u0440\u0435\u0432\u043e, \u0414\u0435\u043a\u0430\u0440\u0442\u043e\u0432\u043e \u0434\u0435\u0440\u0435\u0432\u043e. \u042f \u043d\u0435 \u0431\u0443\u0434\u0443 \u0440\u0430\u0441\u043f\u0438\u0441\u044b\u0432\u0430\u0442\u044c \u043f\u043e\u0434\u0440\u043e\u0431\u043d\u043e\u0441\u0442\u0438 \u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u043e\u0432\u043a\u0438 \u0434\u0435\u0440\u0435\u0432\u0430, \u0434\u043b\u044f \u043d\u0430\u0441 \u043f\u043e\u0434\u043e\u0439\u0434\u0451\u0442 \u043b\u044e\u0431\u043e\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c. \u0414\u0430\u0432\u0430\u0439\u0442\u0435 \u043f\u0440\u043e\u0441\u0442\u043e \u0441\u0447\u0438\u0442\u0430\u0442\u044c, \u0447\u0442\u043e \u0434\u0435\u0440\u0435\u0432\u043e \u0432 \u0441\u0440\u0435\u0434\u043d\u0435\u043c \u0441\u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u043e\u0432\u0430\u043d\u043e \u0438 \u0435\u0433\u043e \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u0430\u044f \u0433\u043b\u0443\u0431\u0438\u043d\u0430 \u043d\u0435 \u0441\u0438\u043b\u044c\u043d\u043e \u043e\u0442\u043b\u0438\u0447\u0430\u0435\u0442\u0441\u044f \u043e\u0442 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0439.<\/p>\n<h3>\u041d\u0435\u0431\u043e\u043b\u044c\u0448\u0430\u044f \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u044f<\/h3>\n<p>  \u041f\u043e\u0434\u0445\u043e\u0434 \u043e\u043f\u0438\u0441\u0430\u043d\u043d\u044b\u0439 \u0432\u044b\u0448\u0435, \u0441 \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u043e\u0439 \u0440\u0430\u0437\u043c\u0435\u0440\u0430 \u0434\u0435\u0440\u0435\u0432\u0430 \u0441\u043b\u0435\u0432\u0430 \u0443\u0434\u043e\u0431\u0435\u043d \u0434\u043b\u044f \u0432\u043e\u0441\u043f\u0440\u0438\u044f\u0442\u0438\u044f, \u043d\u043e \u043c\u043e\u0436\u043d\u043e \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u0447\u0443\u0442\u044c \u0431\u043e\u043b\u0435\u0435 \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u043e. \u0414\u043b\u044f \u0442\u043e\u0433\u043e, \u0447\u0442\u043e\u0431\u044b \u043d\u0435 \u0437\u0430\u0433\u043b\u044f\u0434\u044b\u0432\u0430\u0442\u044c \u043a\u0430\u0436\u0434\u044b\u0439 \u0440\u0430\u0437 \u0432 \u043b\u0435\u0432\u043e\u0435 \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u043e \u043c\u043e\u0436\u043d\u043e \u0432\u043c\u0435\u0441\u0442\u043e \u0440\u0430\u0437\u043c\u0435\u0440\u0430 \u0434\u0435\u0440\u0435\u0432\u0430 \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u0432 \u0443\u0437\u043b\u0435 \u0435\u0433\u043e \u043f\u043e\u0437\u0438\u0446\u0438\u044e \u043e\u0442\u043d\u043e\u0441\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u043f\u043e\u0437\u0438\u0446\u0438\u0438 \u0435\u0433\u043e \u0443\u0437\u043b\u0430-\u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044f. \u041a\u043e\u0440\u043d\u0435\u0432\u043e\u0439 \u0443\u0437\u0435\u043b \u0445\u0440\u0430\u043d\u0438\u0442 \u0430\u0431\u0441\u043e\u043b\u044e\u0442\u043d\u0443\u044e \u043f\u043e\u0437\u0438\u0446\u0438\u044e, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0441\u043e\u0432\u043f\u0430\u0434\u0430\u0435\u0442 \u0441 \u0440\u0430\u0437\u043c\u0435\u0440\u043e\u043c \u043b\u0435\u0432\u043e\u0433\u043e \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u0430.  <\/p>\n<pre><code class=\"plaintext\">                             [el: r, pos: 3]                            \/        :        \\                           \/         :         \\          [el: w, pos: -2]           :           [el: y, pos: +2]            \/     :    \\             :             \/    :     \\           \/      :     \\            :            \/     :      \\ [el: q, pos: -1] : [el: e, pos: +1] : [el: t, pos: -1] : [el: u, pos: +1]         :        :         :        :         :        :         :         :        :         :        :         :        :         :        [q]      [w]       [e]      [r]       [t]      [y]       [u]  Index:  0        1         2        3         4        5         6<\/code><\/pre>\n<p>  \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u043a\u043e\u0440\u043d\u0435\u0432\u043e\u0439 \u0443\u0437\u0435\u043b \u201cr\u201d \u0438\u043c\u0435\u0435\u0442 \u043f\u043e\u0437\u0438\u0446\u0438\u044e 3. \u0423\u0437\u0435\u043b \u201cw\u201d \u0438\u043c\u0435\u0435\u0442 \u043f\u043e\u0437\u0438\u0446\u0438\u044e -2 \u043e\u0442\u043d\u043e\u0441\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u0441\u043a\u043e\u0433\u043e \u0443\u0437\u043b\u0430 \u0438\u043b\u0438 \u0430\u0431\u0441\u043e\u043b\u044e\u0442\u043d\u0443\u044e \u043f\u043e\u0437\u0438\u0446\u0438\u044e 3 + (-2) = 1. \u0410\u043d\u0430\u043b\u043e\u0433\u0438\u0447\u043d\u043e \u043c\u043e\u0436\u043d\u043e \u0441\u043f\u0443\u0441\u0442\u0438\u0442\u044c\u0441\u044f \u0435\u0449\u0451 \u043d\u0430 \u043e\u0434\u0438\u043d \u0443\u0440\u043e\u0432\u0435\u043d\u044c, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440 \u0443\u0437\u0435\u043b \u201ce\u201d \u0438\u043c\u0435\u0435\u0442 \u043f\u043e\u0437\u0438\u0446\u0438\u044e 3 + (-2) + (+1) = 2. \u0422.\u0435. \u0438\u043d\u0434\u0435\u043a\u0441 \u0443\u0437\u043b\u0430 \u2014 \u044d\u0442\u043e \u0441\u0443\u043c\u043c\u0430 \u043f\u043e\u0437\u0438\u0446\u0438\u0439 \u043e\u0442 \u043a\u043e\u0440\u043d\u044f \u0434\u0435\u0440\u0435\u0432\u0430 \u0434\u043e \u044d\u0442\u043e\u0433\u043e \u0443\u0437\u043b\u0430.<\/p>\n<p>  \u042d\u0442\u0430 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u044f \u043f\u043e\u043c\u0438\u043c\u043e \u0431\u043e\u043b\u0435\u0435 \u0431\u044b\u0441\u0442\u0440\u043e\u0433\u043e \u043f\u043e\u0438\u0441\u043a\u0430 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u0432 \u0441\u043f\u0438\u0441\u043a\u0435 \u0434\u0430\u0441\u0442 \u0431\u043e\u043b\u0435\u0435 \u0431\u044b\u0441\u0442\u0440\u044b\u0439 \u0438 \u043f\u0440\u043e\u0441\u0442\u043e\u0439 \u043f\u043e\u0438\u0441\u043a \u0438\u043d\u0434\u0435\u043a\u0441\u0430 \u0443 \u0443\u0437\u043b\u0430. \u041d\u043e, \u043a\u043e\u043d\u0435\u0447\u043d\u043e, \u043f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u043e \u043e\u0431\u043d\u043e\u0432\u043b\u044f\u0442\u044c \u043f\u043e\u0437\u0438\u0446\u0438\u044e \u043f\u0440\u0438 \u0438\u0437\u043c\u0435\u043d\u0435\u043d\u0438\u0438 \u0434\u0435\u0440\u0435\u0432\u0430 \u0441\u0442\u0430\u043b\u043e \u0447\u0443\u0442\u044c \u0441\u043b\u043e\u0436\u043d\u0435\u0435.<\/p>\n<h3>\u0414\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c \u0438\u043d\u0434\u0435\u043a\u0441\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435<\/h3>\n<p>  \u0418\u0442\u0430\u043a, \u0432 \u0434\u0435\u0440\u0435\u0432\u0435 \u043c\u044b \u0443\u043c\u0435\u0435\u043c \u0431\u0440\u0430\u0442\u044c \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u043f\u043e \u0438\u043d\u0434\u0435\u043a\u0441\u0443, \u043c\u0435\u043d\u044f\u0442\u044c \u0435\u0433\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435, \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0442\u044c \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0432 \u0441\u0435\u0440\u0435\u0434\u0438\u043d\u0443 \u0438 \u0443\u0434\u0430\u043b\u044f\u0442\u044c. \u041f\u043e \u0441\u0443\u0442\u0438, \u043d\u0430\u043c \u043e\u0441\u0442\u0430\u043b\u043e\u0441\u044c \u0434\u043e\u0431\u0430\u0432\u0438\u0442\u044c \u0431\u044b\u0441\u0442\u0440\u044b\u0439 \u043f\u043e\u0438\u0441\u043a \u0438\u043d\u0434\u0435\u043a\u0441\u0430 \u043f\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044e, indexOf(obj). \u0422\u043e\u0433\u0434\u0430 contains(obj) \u0438 remove(obj) \u0431\u0443\u0434\u0443\u0442 \u0440\u0435\u0448\u0430\u0442\u044c\u0441\u044f \u0442\u0440\u0438\u0432\u0438\u0430\u043b\u044c\u043d\u043e.<\/p>\n<p>  \u041d\u043e \u0434\u043b\u044f \u043d\u0430\u0447\u0430\u043b\u0430 \u0434\u0430\u0432\u0430\u0439\u0442\u0435 \u043d\u0435\u043c\u043d\u043e\u0433\u043e \u0443\u043f\u0440\u043e\u0441\u0442\u0438\u043c \u0437\u0430\u0434\u0430\u0447\u0443. \u0414\u0430\u0432\u0430\u0439\u0442\u0435 \u0441\u0434\u0435\u043b\u0430\u0435\u043c \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0443, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0445\u0440\u0430\u043d\u0438\u0442 \u0442\u043e\u043b\u044c\u043a\u043e \u0443\u043d\u0438\u043a\u0430\u043b\u044c\u043d\u044b\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b. <\/p>\n<p>  \u0414\u043b\u044f \u0442\u043e\u0433\u043e \u0447\u0442\u043e\u0431\u044b \u0447\u0442\u043e-\u0442\u043e \u0431\u044b\u0441\u0442\u0440\u043e \u0438\u0441\u043a\u0430\u0442\u044c \u043e\u0431\u044b\u0447\u043d\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044e\u0442 \u0442\u0430\u0431\u043b\u0438\u0446\u0443. \u0412 \u043c\u0438\u0440\u0435 Java \u0442\u0430\u0431\u043b\u0438\u0446\u044b \u043d\u0430\u0437\u044b\u0432\u0430\u044e\u0442\u0441\u044f Map, \u0443 \u043d\u0435\u0451 \u0435\u0441\u0442\u044c 2 \u043e\u0441\u043d\u043e\u0432\u043d\u044b\u0435 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438: HashMap \u0438 TreeMap. \u041a\u043b\u044e\u0447\u043e\u043c \u0442\u0430\u0431\u043b\u0438\u0446\u044b \u0431\u0443\u0434\u0435\u0442 \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u043e\u0431\u044a\u0435\u043a\u0442, \u0430 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435\u043c \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u0435\u0433\u043e \u0443\u0437\u0435\u043b:  <\/p>\n<pre><code class=\"kotlin\">class IndexedTreeListSet&lt;T&gt; {   root: Node&lt;T&gt;   indexMap: Map&lt;T, Node&lt;T&gt;&gt; }<\/code><\/pre>\n<p>  \u0422.\u0435. \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0438\u0437 \u0434\u0432\u0443\u0445 \u0447\u0430\u0441\u0442\u0435\u0439: \u0441\u0430\u043c\u043e \u0434\u0435\u0440\u0435\u0432\u043e-\u0441\u043f\u0438\u0441\u043e\u043a \u0438 \u0442\u0430\u0431\u043b\u0438\u0446\u0430 \u0441\u043e \u0441\u0441\u044b\u043b\u043a\u0430\u043c\u0438 \u043d\u0430 \u043e\u0431\u044a\u0435\u043a\u0442\u044b \u0438 \u0443\u0437\u043b\u044b \u044d\u0442\u043e\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430. \u041f\u0440\u0438 \u043e\u0431\u043d\u043e\u0432\u043b\u0435\u043d\u0438\u0438 \u0434\u0435\u0440\u0435\u0432\u0430 \u043d\u0430\u0434\u043e \u043e\u0431\u043d\u043e\u0432\u043b\u044f\u0442\u044c \u0438 \u0442\u0430\u0431\u043b\u0438\u0446\u0443. \u0414\u0435\u0442\u0430\u043b\u044c\u043d\u043e \u0440\u0430\u0441\u043f\u0438\u0441\u044b\u0432\u0430\u0442\u044c \u043f\u0440\u043e\u0446\u0435\u0441\u0441 \u043d\u0435 \u0431\u0443\u0434\u0443. \u0418\u043d\u0442\u0443\u0438\u0442\u0438\u0432\u043d\u043e \u043e\u043d \u0434\u043e\u043b\u0436\u0435\u043d \u0431\u044b\u0442\u044c \u043f\u043e\u043d\u044f\u0442\u0435\u043d: \u0434\u043e\u0431\u0430\u0432\u0438\u043b\u0438 \u0443\u0437\u0435\u043b \u2014 \u043f\u043e\u043b\u043e\u0436\u0438\u043b\u0438 \u0435\u0433\u043e \u0436\u0435 \u0432 \u0442\u0430\u0431\u043b\u0438\u0446\u0443, \u0443\u0434\u0430\u043b\u0438\u043b\u0438 \u0443\u0437\u0435\u043b \u2014 \u0443\u0434\u0430\u043b\u0438\u043b\u0438 \u0438\u0437 \u0442\u0430\u0431\u043b\u0438\u0446\u044b. \u041d\u0430 \u043f\u0440\u0430\u043a\u0442\u0438\u043a\u0435 \u0436\u0435 \u0435\u0441\u0442\u044c \u043d\u044e\u0430\u043d\u0441\u044b \u0441 \u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u043e\u0432\u043a\u043e\u0439 \u0434\u0435\u0440\u0435\u0432\u0430: \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0434\u043e\u043b\u0436\u0435\u043d \u043c\u0435\u043d\u044f\u0442\u044c \u0441\u0441\u044b\u043b\u043a\u0438 \u043c\u0435\u0436\u0434\u0443 \u0443\u0437\u043b\u0430\u043c\u0438, \u0430 \u043d\u0435 \u043f\u0435\u0440\u0435\u043c\u0435\u0449\u0430\u0442\u044c \u043e\u0431\u044a\u0435\u043a\u0442\u044b \u043c\u0435\u0436\u0434\u0443 \u0443\u0437\u043b\u0430\u043c\u0438. \u0418\u043d\u0430\u0447\u0435 \u043f\u0440\u0438\u0434\u0451\u0442\u0441\u044f \u0434\u0435\u043b\u0430\u0442\u044c \u043c\u043d\u043e\u0433\u043e \u043e\u0431\u043d\u043e\u0432\u043b\u0435\u043d\u0438\u0439 \u0432 \u0442\u0430\u0431\u043b\u0438\u0446\u0435 \u0438 \u0443\u043f\u0430\u0434\u0451\u0442 \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c.<\/p>\n<p>  \u041e\u043a, \u0431\u0443\u0434\u0435\u043c \u0441\u0447\u0438\u0442\u0430\u0442\u044c, \u0447\u0442\u043e \u043c\u044b \u0443\u043c\u0435\u0435\u043c \u0431\u044b\u0441\u0442\u0440\u043e \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u044c \u0443\u0437\u0435\u043b \u043f\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0443, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0432 \u043d\u0451\u043c \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442\u0441\u044f. \u0418 \u0447\u0442\u043e? \u041d\u0430\u043c \u043d\u0443\u0436\u043d\u043e \u043d\u0430\u0439\u0442\u0438 \u0435\u0433\u043e \u0438\u043d\u0434\u0435\u043a\u0441, \u0430 \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u044d\u0442\u043e\u0433\u043e \u043f\u043e\u043a\u0430 \u043d\u0435\u043b\u044c\u0437\u044f. \u041d\u043e \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u0443\u0441\u043b\u043e\u0436\u043d\u0438\u0442\u044c \u043a\u043b\u0430\u0441\u0441 \u0443\u0437\u043b\u0430 \u0442\u0430\u043a, \u0447\u0442\u043e\u0431\u044b \u043e\u043d \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u043b \u043d\u0435 \u0442\u043e\u043b\u044c\u043a\u043e \u0441\u0441\u044b\u043b\u043a\u0438 \u043d\u0430 \u043b\u0435\u0432\u044b\u0439 \u0438 \u043f\u0440\u0430\u0432\u044b\u0439 \u0443\u0437\u043b\u044b, \u043d\u043e \u0438 \u043d\u0430 \u0441\u0432\u043e\u0435\u0433\u043e \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044f:  <\/p>\n<pre><code class=\"kotlin\">class Node&lt;T&gt; {   obj: T   left: Node&lt;T&gt;   right: Node&lt;T&gt;   parent: Node&lt;T&gt;   pos: int }<\/code><\/pre>\n<p>  \u041a\u043e\u043d\u0435\u0447\u043d\u043e, \u043e\u0431\u043d\u043e\u0432\u043b\u0435\u043d\u0438\u0435 \u0434\u0435\u0440\u0435\u0432\u0430 \u0435\u0449\u0451 \u043d\u0435\u043c\u043d\u043e\u0433\u043e \u0443\u0441\u043b\u043e\u0436\u043d\u044f\u0435\u0442\u0441\u044f, \u0432\u0435\u0434\u044c \u043d\u0430\u043c \u0442\u0435\u043f\u0435\u0440\u044c \u043d\u0443\u0436\u043d\u043e \u0430\u043a\u043a\u0443\u0440\u0430\u0442\u043d\u043e \u043e\u0431\u043d\u043e\u0432\u043b\u044f\u0442\u044c \u0441\u0441\u044b\u043b\u043a\u0443 \u043d\u0430 \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044f. \u0417\u0430\u0442\u043e \u0442\u0435\u043f\u0435\u0440\u044c, \u0437\u043d\u0430\u044f \u0443\u0437\u0435\u043b, \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u043f\u0440\u043e\u0439\u0442\u0438 \u043f\u043e \u0434\u0435\u0440\u0435\u0432\u0443 \u0432\u0432\u0435\u0440\u0445 \u0438 \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u044c \u0438\u043d\u0434\u0435\u043a\u0441 \u043b\u044e\u0431\u043e\u0433\u043e \u0443\u0437\u043b\u0430. \u0415\u0441\u043b\u0438 \u043c\u044b \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043b\u0438 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u044e \u0438\u0437 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0435\u0439 \u0433\u043b\u0430\u0432\u044b, \u0442\u043e \u043d\u0430\u043c \u043d\u0430\u0434\u043e \u043f\u0440\u043e\u0441\u0442\u043e \u043f\u043e\u0441\u0447\u0438\u0442\u0430\u0442\u044c \u0441\u0443\u043c\u043c\u0443 \u043f\u043e\u0437\u0438\u0446\u0438\u0439 \u043e\u0442 \u0442\u0435\u043a\u0443\u0449\u0435\u0433\u043e \u0443\u0437\u043b\u0430 \u0434\u043e \u043a\u043e\u0440\u043d\u0435\u0432\u043e\u0433\u043e.<\/p>\n<p>  \u0414\u043b\u044f \u0441\u043f\u0438\u0441\u043a\u0430, \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0449\u0435\u0433\u043e \u0443\u043d\u0438\u043a\u0430\u043b\u044c\u043d\u044b\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0437\u0430\u0434\u0430\u0447\u0443 \u043c\u043e\u0436\u043d\u043e \u0441\u0447\u0438\u0442\u0430\u0442\u044c \u0440\u0435\u0448\u0435\u043d\u043d\u043e\u0439.<\/p>\n<p>  \u041f\u0440\u0430\u0432\u0434\u0430, \u0443 \u043d\u0430\u0441 \u043f\u043e\u044f\u0432\u0438\u043b\u0430\u0441\u044c \u043d\u0435\u0431\u043e\u043b\u044c\u0448\u0430\u044f \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u043a\u0430. \u0414\u043e\u043f\u0443\u0441\u0442\u0438\u043c, \u043c\u044b \u0432\u044b\u0437\u044b\u0432\u0430\u0435\u043c set(index, obj). \u041c\u044b \u043c\u043e\u0436\u0435\u043c \u043b\u0435\u0433\u043a\u043e \u0437\u0430\u043c\u0435\u043d\u0438\u0442\u044c \u043e\u0434\u0438\u043d \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0432 \u0443\u0437\u043b\u0435 \u043d\u0430 \u0434\u0440\u0443\u0433\u043e\u0439, \u043d\u043e \u0442\u043e\u043b\u044c\u043a\u043e \u0432 \u0442\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435, \u0435\u0441\u043b\u0438 \u043d\u043e\u0432\u043e\u0433\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u0432 \u0441\u043f\u0438\u0441\u043a\u0435 \u0435\u0449\u0435 \u043d\u0435\u0442. \u0410 \u0435\u0441\u043b\u0438 \u0435\u0441\u0442\u044c, \u0442\u043e \u0447\u0442\u043e \u0434\u0435\u043b\u0430\u0442\u044c? \u0423\u0434\u0430\u043b\u0438\u0442\u044c \u043b\u0438\u0448\u043d\u0438\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0438\u0437 \u0441\u0442\u0430\u0440\u043e\u0439 \u043f\u043e\u0437\u0438\u0446\u0438\u0438 \u0438 \u043f\u043e\u043b\u043e\u0436\u0438\u0442\u044c \u0432 \u043d\u043e\u0432\u0443\u044e? \u0418\u043b\u0438 \u043d\u0430\u043e\u0431\u043e\u0440\u043e\u0442, \u0441\u043d\u0430\u0447\u0430\u043b\u0430 \u0434\u043e\u0431\u0430\u0432\u0438\u0442\u044c, \u0430 \u043f\u043e\u0442\u043e\u043c \u0443\u0434\u0430\u043b\u0438\u0442\u044c? \u0420\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u0440\u0430\u0437\u043d\u044b\u043c. \u0410 \u043c\u043e\u0436\u043d\u043e \u0432\u043e\u043e\u0431\u0449\u0435 \u043d\u0438\u0447\u0435\u0433\u043e \u043d\u0435 \u0434\u0435\u043b\u0430\u0442\u044c \u0438\u043b\u0438 \u0431\u0440\u043e\u0441\u0430\u0442\u044c \u0438\u0441\u043a\u043b\u044e\u0447\u0435\u043d\u0438\u0435. \u0418\u0434\u0435\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u043d\u0435\u0442.<\/p>\n<p>  \u041e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0441\u0442\u0430\u043d\u0434\u0430\u0440\u0442\u043d\u044b\u043c\u0438 \u043c\u0435\u0442\u043e\u0434\u0430\u043c\u0438 \u0442\u0430\u043a\u043e\u0439 \u0441\u043f\u0438\u0441\u043e\u043a \u0442\u043e\u0436\u0435, \u0441\u043a\u043e\u0440\u0435\u0435 \u0432\u0441\u0435\u0433\u043e, \u043d\u0435 \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u0441\u044f. \u0412\u0435\u0434\u044c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0438 \u043d\u0435 \u0431\u0443\u0434\u0435\u0442 \u0437\u043d\u0430\u0442\u044c \u043f\u0440\u043e \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e\u0441\u0442\u044c \u0443\u043d\u0438\u043a\u0430\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u043e\u0431\u044a\u0435\u043a\u0442\u043e\u0432 \u0438 \u043f\u0440\u0438 \u043f\u0435\u0440\u0435\u043c\u0435\u0449\u0435\u043d\u0438\u0438 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0432 \u0441\u043f\u0438\u0441\u043a\u0435 \u0431\u0443\u0434\u0435\u0442 \u0441\u043e\u0437\u0434\u0430\u0432\u0430\u0442\u044c \u0434\u0443\u0431\u043b\u0438\u043a\u0430\u0442\u044b.<\/p>\n<h3>\u0423\u0431\u0438\u0440\u0430\u0435\u043c \u0443\u043d\u0438\u043a\u0430\u043b\u044c\u043d\u043e\u0441\u0442\u044c<\/h3>\n<p>  \u041e\u043a, \u0443\u0441\u043b\u043e\u0436\u043d\u044f\u0435\u043c \u0435\u0449\u0451, \u0440\u0430\u0437\u0440\u0435\u0448\u0438\u043c \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u044b\u0435 \u043e\u0431\u044a\u0435\u043a\u0442\u044b. \u041e\u0447\u0435\u0432\u0438\u0434\u043d\u043e, \u0447\u0442\u043e \u043d\u0430\u0434\u043e \u0447\u0442\u043e-\u0442\u043e \u0434\u0435\u043b\u0430\u0442\u044c \u0441 \u0442\u0430\u0431\u043b\u0438\u0446\u0435\u0439. \u041f\u0435\u0440\u0432\u0430\u044f \u0438\u0434\u0435\u044f \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u0432 \u043d\u0435\u0439 \u0441\u043f\u0438\u0441\u043e\u043a \u0443\u0437\u043b\u043e\u0432 \u043a\u0430\u0436\u0435\u0442\u0441\u044f \u043d\u0435 \u043e\u0447\u0435\u043d\u044c \u0445\u043e\u0440\u043e\u0448\u0435\u0439: \u0441 \u0443\u0432\u0435\u043b\u0438\u0447\u0435\u043d\u0438\u0435\u043c \u0434\u043b\u0438\u043d\u044b \u0441\u043f\u0438\u0441\u043a\u0430 \u0431\u0443\u0434\u0435\u0442 \u0443\u0445\u0443\u0434\u0448\u0430\u0442\u044c\u0441\u044f \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c. \u0412\u043f\u043b\u043e\u0442\u044c \u0434\u043e O(n), \u0435\u0441\u043b\u0438 \u0432\u0441\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0441\u043f\u0438\u0441\u043a\u0430 \u0431\u0443\u0434\u0443\u0442 \u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u044b\u043c\u0438. <\/p>\n<p>  \u0422\u043e\u0433\u0434\u0430 \u0434\u0430\u0432\u0430\u0439\u0442\u0435 \u043f\u043e\u043f\u0440\u043e\u0431\u0443\u0435\u043c \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u0432 \u0442\u0430\u0431\u043b\u0438\u0446\u0435 \u0432\u043c\u0435\u0441\u0442\u043e \u0441\u043f\u0438\u0441\u043a\u0430 \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e \u0443\u0437\u043b\u043e\u0432. \u041e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0435 \u043f\u043e \u043f\u043e\u0437\u0438\u0446\u0438\u0438 \u0432 \u0441\u043f\u0438\u0441\u043a\u0435.  <\/p>\n<pre><code class=\"kotlin\">class IndexedTreeList&lt;T&gt; {   root: Node&lt;T&gt;   indexMap: Map&lt;T, TreeSet&lt;Node&lt;T&gt;&gt;&gt; }<\/code><\/pre>\n<p>  \u0422\u043e\u0433\u0434\u0430 \u0432\u0441\u0442\u0430\u0432\u043a\u0430\/\u0443\u0434\u0430\u043b\u0435\u043d\u0438\u0435 \u0432\/\u0438\u0437 TreeSet&lt;Node&gt; \u0440\u0430\u0437\u043c\u0435\u0440\u0430 m \u0431\u0443\u0434\u0435\u0442 \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u0442\u044c \u0437\u0430 log(m) \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0439 \u043f\u043e\u0437\u0438\u0446\u0438\u0439 \u0443\u0437\u043b\u043e\u0432, \u0430 \u043a\u0430\u0436\u0434\u043e\u0435 \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0435 \u0431\u0443\u0434\u0435\u0442 \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u0442\u044c \u0437\u0430 log(n) \u0432\u0440\u0435\u043c\u0435\u043d\u0438. \u0418\u0442\u043e\u0433\u043e\u0432\u0430\u044f \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0432\u0441\u0442\u0430\u0432\u043a\u0438 \u0438\u043b\u0438 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044f \u0432 \u043f\u043e\u0434\u043e\u0431\u043d\u0443\u044e \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0443 \u0431\u0443\u0434\u0435\u0442 \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u0442\u044c \u0437\u0430 O(log(n) * (1 + log(m))), \u0433\u0434\u0435 n \u044d\u0442\u043e \u043e\u0431\u0449\u0435\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0432 \u0441\u043f\u0438\u0441\u043a\u0435, \u0430 m \u044d\u0442\u043e \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0432 \u0441\u043f\u0438\u0441\u043a\u0435 \u0440\u0430\u0432\u043d\u044b\u0445 \u0432\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u043c\u043e\u043c\u0443\/\u0443\u0434\u0430\u043b\u044f\u0435\u043c\u043e\u043c\u0443. \u0412 \u0445\u0443\u0434\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435, \u043a\u043e\u0433\u0434\u0430 \u0432\u0441\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0440\u0430\u0432\u043d\u044b \u0434\u0440\u0443\u0433 \u0434\u0440\u0443\u0433\u0443, \u043f\u043e\u043b\u0443\u0447\u0438\u043c \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c O(log(n) ^ 2).<\/p>\n<p>  \u0412\u043d\u0438\u043c\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0439 \u0447\u0438\u0442\u0430\u0442\u0435\u043b\u044c \u043d\u0430\u0432\u0435\u0440\u043d\u044f\u043a\u0430 \u0432\u043e\u0437\u0440\u0430\u0437\u0438\u0442: \u0430 \u043a\u0430\u043a \u0436\u0435 \u0438\u043c\u043c\u0443\u0442\u0430\u0431\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c? \u041c\u044b \u0432\u0435\u0434\u044c \u043d\u0435 \u043c\u043e\u0436\u0435\u043c \u0438\u0437\u043c\u0435\u043d\u044f\u0442\u044c \u043e\u0431\u044a\u0435\u043a\u0442\u044b, \u0435\u0441\u043b\u0438 \u043e\u043d\u0438 \u044f\u0432\u043b\u044f\u044e\u0442\u0441\u044f \u043a\u043b\u044e\u0447\u0430\u043c\u0438 \u0442\u0430\u0431\u043b\u0438\u0446\u044b? \u0412 \u043e\u0431\u0449\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u0442\u0430\u043a \u0438 \u0435\u0441\u0442\u044c. \u041e\u0434\u043d\u0430\u043a\u043e \u0434\u043b\u044f \u0434\u0435\u0440\u0435\u0432\u0430, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u0445\u0440\u0430\u043d\u0438\u0442 \u0432 \u043a\u043b\u044e\u0447\u0430\u0445 \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0435 \u043e\u0431\u044a\u0435\u043a\u0442\u044b, \u043f\u043e\u043c\u0438\u043c\u043e \u0441\u0442\u0430\u043d\u0434\u0430\u0440\u0442\u043d\u044b\u0445 \u043f\u0440\u0430\u0432\u0438\u043b \u0434\u043b\u044f \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0439, \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u0441\u043e\u0445\u0440\u0430\u043d\u044f\u0442\u044c \u0438\u043d\u0432\u0430\u0440\u0438\u0430\u043d\u0442: \u0435\u0441\u043b\u0438 a &lt; b, \u0442\u043e \u044d\u0442\u043e \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u043e \u043d\u0435 \u0434\u043e\u043b\u0436\u043d\u043e \u0438\u0437\u043c\u0435\u043d\u044f\u0442\u044c\u0441\u044f \u0441\u043e \u0432\u0440\u0435\u043c\u0435\u043d\u0435\u043c. \u042d\u0442\u043e \u043a\u0430\u043a \u0440\u0430\u0437 \u043d\u0430\u0448 \u0441\u043b\u0443\u0447\u0430\u0439: \u0435\u0441\u043b\u0438 \u043f\u043e\u0437\u0438\u0446\u0438\u044f \u043e\u0434\u043d\u043e\u0433\u043e \u0443\u0437\u043b\u0430 \u043c\u0435\u043d\u044c\u0448\u0435 \u043f\u043e\u0437\u0438\u0446\u0438\u0438 \u0434\u0440\u0443\u0433\u043e\u0433\u043e \u0443\u0437\u043b\u0430, \u0442\u043e \u044d\u0442\u043e \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u043e \u0431\u0443\u0434\u0435\u0442 \u0441\u043e\u0445\u0440\u0430\u043d\u044f\u0442\u044c\u0441\u044f \u043d\u0435\u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e \u043e\u0442 \u0442\u043e\u0433\u043e, \u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0443\u0437\u043b\u043e\u0432 \u043c\u0435\u0436\u0434\u0443 \u043d\u0438\u043c\u0438 \u0431\u044b\u043b\u043e \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u043e \u0438\u043b\u0438 \u0443\u0434\u0430\u043b\u0435\u043d\u043e.<\/p>\n<h2>\u041c\u043e\u0436\u043d\u043e \u043b\u0438 \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0443 \u043f\u0435\u0440\u0441\u0438\u0441\u0442\u0435\u043d\u0442\u043d\u043e\u0439?<\/h2>\n<p>  \u041a\u043e\u0440\u043e\u0442\u043a\u0438\u0439 \u043e\u0442\u0432\u0435\u0442: \u043d\u0435\u0442, \u043d\u0435\u043b\u044c\u0437\u044f. \u0418\u0437-\u0437\u0430 \u0434\u0432\u0443\u0441\u0432\u044f\u0437\u043d\u043e\u0441\u0442\u0438 \u0434\u0435\u0440\u0435\u0432\u0430, \u043e\u0442 \u043a\u043e\u0440\u043d\u044f \u043a \u043b\u0438\u0441\u0442\u044c\u044f\u043c \u0438 \u043e\u0431\u0440\u0430\u0442\u043d\u043e, \u0443 \u043d\u0430\u0441 \u043a\u0430\u0436\u0434\u044b\u0439 \u0443\u0437\u0435\u043b \u0434\u0435\u0440\u0435\u0432\u0430 \u0441\u0432\u044f\u0437\u0430\u043d \u0441 \u043a\u0430\u0436\u0434\u044b\u043c. \u041f\u0435\u0440\u0441\u0438\u0441\u0442\u0435\u043d\u0442\u043d\u043e\u0441\u0442\u044c \u0442\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c \u043d\u0435 \u0441\u0434\u0435\u043b\u0430\u0442\u044c, \u043f\u0440\u0438\u0434\u0451\u0442\u0441\u044f \u043f\u0435\u0440\u0435\u0441\u043e\u0437\u0434\u0430\u0432\u0430\u0442\u044c \u0432\u0441\u044e \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0443 \u043f\u0440\u0438 \u043b\u044e\u0431\u043e\u043c \u0438\u0437\u043c\u0435\u043d\u0435\u043d\u0438\u0438.<\/p>\n<p>  \u041d\u043e \u0443 \u043c\u0435\u043d\u044f \u0435\u0441\u0442\u044c \u043f\u043e\u043d\u0438\u043c\u0430\u043d\u0438\u0435 \u043a\u0430\u043a \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u0442\u044c \u043f\u0435\u0440\u0441\u0438\u0441\u0442\u0435\u043d\u0442\u043d\u0443\u044e \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0443 \u0434\u043b\u044f \u0441\u043b\u0443\u0447\u0430\u0435\u0432, \u043a\u043e\u0433\u0434\u0430 \u043d\u0430\u043c \u043d\u0435 \u043d\u0443\u0436\u043d\u043e \u0432\u0441\u0442\u0430\u0432\u043b\u044f\u0442\u044c \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0432 \u0441\u0435\u0440\u0435\u0434\u0438\u043d\u0443 \u0441\u043f\u0438\u0441\u043a\u0430. \u041c\u043e\u0436\u043d\u043e \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0442\u044c \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0432 \u043d\u0430\u0447\u0430\u043b\u043e \u0438\u043b\u0438 \u043a\u043e\u043d\u0435\u0446, \u0430 \u0443\u0434\u0430\u043b\u044f\u0442\u044c \u043c\u043e\u0436\u043d\u043e \u0438\u0437 \u0441\u0435\u0440\u0435\u0434\u0438\u043d\u044b. \u041e\u0441\u0442\u0430\u043b\u044c\u043d\u044b\u0435 \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u0430 \u0442\u0435 \u0436\u0435.<\/p>\n<p>  \u0415\u0441\u043b\u0438 \u0432\u0430\u043c \u0431\u0443\u0434\u0435\u0442 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u043e, \u0442\u043e \u044f \u043f\u043e\u0441\u0442\u0430\u0440\u0430\u044e\u0441\u044c \u043d\u0430\u043f\u0438\u0441\u0430\u0442\u044c \u0441\u0442\u0430\u0442\u044c\u044e \u043e\u0431 \u044d\u0442\u043e\u0439 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0435. \u0412\u043e\u0437\u043c\u043e\u0436\u043d\u043e, \u0434\u0430\u0436\u0435 \u0440\u0435\u0430\u043b\u0438\u0437\u0443\u044e \u0435\u0451 \u043d\u0430 Java, Kotlin \u0438\u043b\u0438 Scala. \u041d\u043e, \u0441\u043a\u043e\u0440\u0435\u0435 \u0432\u0441\u0435\u0433\u043e, \u044d\u0442\u043e \u0431\u0443\u0434\u0435\u0442 \u043d\u0435 \u0441\u043a\u043e\u0440\u043e.<\/p>\n<h2>\u041d\u0435\u043c\u043d\u043e\u0433\u043e \u043e\u0441\u043e\u0431\u0435\u043d\u043d\u043e\u0441\u0442\u0435\u0439 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438<\/h2>\n<p>  \u0422\u0443\u0442 \u044f \u0445\u043e\u0447\u0443 \u043e\u043f\u0438\u0441\u0430\u0442\u044c \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043e\u0441\u043e\u0431\u0435\u043d\u043d\u043e\u0441\u0442\u0438, \u0441 \u043a\u043e\u0442\u043e\u0440\u044b\u043c\u0438 \u043f\u0440\u0438\u0448\u043b\u043e\u0441\u044c \u0441\u0442\u043e\u043b\u043a\u043d\u0443\u0442\u044c\u0441\u044f.<br \/>  \u041f\u0440\u043e \u043e\u0434\u043d\u0443 \u0438\u0437 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0439 \u043f\u0440\u043e \u0445\u0440\u0430\u043d\u0435\u043d\u0438\u0435 \u043f\u043e\u0437\u0438\u0446\u0438\u0438 \u0443\u0437\u043b\u0430 \u0432 \u0441\u043f\u0438\u0441\u043a\u0435 \u044f \u043f\u0438\u0441\u0430\u043b \u0432\u044b\u0448\u0435. \u0422\u0443\u0442 \u043f\u0440\u043e\u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0441\u0438\u043b\u0430 Open Source: \u044f \u0432\u0437\u044f\u043b \u0433\u043e\u0442\u043e\u0432\u044b\u0439 \u043a\u043e\u0434 TreeList \u0438 \u043d\u0435 \u0432\u043d\u0438\u043a\u0430\u043b \u0432 \u0434\u0435\u0442\u0430\u043b\u0438 AVL \u0434\u0435\u0440\u0435\u0432\u0430, \u043f\u043e\u0432\u043e\u0440\u043e\u0442\u043e\u0432 \u0443\u0437\u043b\u043e\u0432, \u043e\u0431\u043d\u043e\u0432\u043b\u0435\u043d\u0438\u044f \u043f\u043e\u0437\u0438\u0446\u0438\u0439 \u0438 \u0442. \u043f.<\/p>\n<p>  \u0414\u0440\u0443\u0433\u0430\u044f \u043e\u0441\u043e\u0431\u0435\u043d\u043d\u043e\u0441\u0442\u044c, \u0434\u043e\u0441\u0442\u0430\u0432\u0448\u0430\u044f\u0441\u044f \u043e\u0442 TreeList, \u044d\u0442\u043e \u0441\u0441\u044b\u043b\u043a\u0438 \u043d\u0430 \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u044c\u044f \u0432 \u043b\u0438\u0441\u0442\u0430\u0445 \u0434\u0435\u0440\u0435\u0432\u044c\u0435\u0432. \u041a\u0430\u0436\u0434\u044b\u0439 \u0443\u0437\u0435\u043b \u0445\u0440\u0430\u043d\u0438\u0442 boolean leftIsPrevious \u0438 rightIsNext. \u042d\u0442\u0438 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0435 \u043e\u0431\u043e\u0437\u043d\u0430\u0447\u0430\u044e\u0442 \u043d\u0430\u043b\u0438\u0447\u0438\u0435 \u0438\u043b\u0438 \u043e\u0442\u0441\u0443\u0442\u0441\u0442\u0432\u0438\u0435 \u043b\u0435\u0432\u043e\u0433\u043e\/\u043f\u0440\u0430\u0432\u043e\u0433\u043e \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u0430. \u0415\u0441\u043b\u0438 \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u0430 \u043d\u0435\u0442, \u0442\u043e \u0432 left\/right \u0432\u043c\u0435\u0441\u0442\u043e \u0441\u0441\u044b\u043b\u043a\u0438 \u043d\u0430 \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u043e \u0445\u0440\u0430\u043d\u0438\u0442\u0441\u044f \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u0443\u0437\u0435\u043b, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u0435\u0442 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0435\u043c\u0443 \u0438\u043b\u0438 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u043c\u0443 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0443. \u0412 \u043d\u0430\u0448\u0435\u043c \u043f\u0440\u0438\u043c\u0435\u0440\u0435 [\u201cq\u201d, \u201cw\u201d, \u201ce\u201d, \u201cr\u201d, \u201ct\u201d, \u201cy\u201d, \u201cu\u201d] \u0443\u0437\u0435\u043b \u201ce\u201d \u043b\u0438\u0441\u0442\u043e\u0432\u043e\u0439, \u0443 \u043d\u0435\u0433\u043e \u043d\u0435\u0442 \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u044c\u0435\u0432. \u0421\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0435\u043d\u043d\u043e leftIsPrevious \u0438 rightIsNext \u0443 \u043d\u0435\u0433\u043e true, \u0430 left \u0438 right \u0443\u043a\u0430\u0437\u044b\u0432\u0430\u044e\u0442 \u043d\u0430 \u0443\u0437\u043b\u044b \u201cw\u201d \u0438 \u201cr\u201d \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0435\u043d\u043d\u043e. \u041f\u043e\u0434\u043e\u0431\u043d\u044b\u0439 \u043f\u043e\u0434\u0445\u043e\u0434 \u043f\u043e\u043c\u043e\u0433\u0430\u0435\u0442 \u0431\u044b\u0441\u0442\u0440\u0435\u0435 \u0438\u0442\u0435\u0440\u0438\u0440\u043e\u0432\u0430\u0442\u044c\u0441\u044f \u043f\u043e \u0441\u043f\u0438\u0441\u043a\u0443. \u0418 \u043c\u0435\u0448\u0430\u0435\u0442 \u043f\u0440\u0438 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0438 \u043d\u043e\u0432\u044b\u0445 \u0444\u0438\u0447\u0435\u0439 \ud83d\ude42<\/p>\n<p>  \u041d\u0435\u043c\u043d\u043e\u0433\u043e \u043e \u0440\u0430\u0431\u043e\u0442\u0435 \u0441 \u0442\u0430\u0431\u043b\u0438\u0446\u0435\u0439 \u043e\u0431\u044a\u0435\u043a\u0442 \u2192 \u0443\u0437\u0435\u043b. \u0412 \u0438\u0434\u0435\u0430\u043b\u0435, \u0432 \u0442\u0430\u0431\u043b\u0438\u0446\u0443 \u043d\u0443\u0436\u043d\u043e \u043e\u0434\u0438\u043d \u0440\u0430\u0437 \u043a\u043b\u0430\u0441\u0442\u044c \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u043f\u0440\u0438 \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u0438 \u0435\u0433\u043e \u0432 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0443 \u0438 \u043e\u0434\u0438\u043d \u0440\u0430\u0437 \u0443\u0434\u0430\u043b\u044f\u0442\u044c \u043f\u0440\u0438 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u0438 \u0438\u0437 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b. \u041d\u0430 \u043f\u0440\u0430\u043a\u0442\u0438\u043a\u0435 \u043c\u043d\u0435 \u044d\u0442\u043e\u0433\u043e \u0434\u043e\u0441\u0442\u0438\u0447\u044c \u043d\u0435 \u0443\u0434\u0430\u043b\u043e\u0441\u044c. \u041f\u0440\u0438 \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u0438 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u043e\u043d \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0432 \u0442\u0430\u0431\u043b\u0438\u0446\u0443, \u0432\u0441\u0451 \u043a\u0430\u043a \u043f\u043e\u043b\u043e\u0436\u0435\u043d\u043e. \u041e\u0434\u043d\u0430\u043a\u043e \u043f\u0440\u0438 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u0438 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u043e\u0432\u043a\u0438 \u0438\u043d\u043e\u0433\u0434\u0430 \u043f\u0435\u0440\u0435\u043c\u0435\u0449\u0430\u0435\u0442 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u043c\u0435\u0436\u0434\u0443 \u0443\u0437\u043b\u0430\u043c\u0438. \u0412 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0435 \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u0442\u0441\u044f \u0434\u0432\u0430 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044f \u0438 \u043e\u0434\u043d\u0430 \u0437\u0430\u043f\u0438\u0441\u044c \u0432 \u0442\u0430\u0431\u043b\u0438\u0446\u0443 \u0432\u043c\u0435\u0441\u0442\u043e \u043e\u0434\u043d\u043e\u0433\u043e \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044f. \u042d\u0442\u043e \u043c\u043e\u0436\u043d\u043e \u0438\u0441\u043f\u0440\u0430\u0432\u0438\u0442\u044c \u0435\u0441\u043b\u0438 \u0443\u0431\u0440\u0430\u0442\u044c \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u044e \u0441 leftIsPrevious \u0438 rightIsNext. \u0418 \u0434\u0430\u0436\u0435 \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u043d\u0435\u0431\u043e\u043b\u044c\u0448\u043e\u0439 \u0432\u044b\u0438\u0433\u0440\u044b\u0448 \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438, \u043f\u0440\u0438\u0447\u0451\u043c \u043d\u0435 \u0442\u043e\u043b\u044c\u043a\u043e \u043f\u0440\u0438 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u0438. \u0412 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0442\u0435\u0441\u0442\u0430\u0445 \u043f\u0440\u0438\u0440\u043e\u0441\u0442 \u0431\u044b\u043b 10-20%. \u041d\u043e \u0441\u043a\u043e\u0440\u043e\u0441\u0442\u044c \u0438\u0442\u0435\u0440\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u043f\u0430\u0434\u0430\u0435\u0442 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u043e, \u0440\u0430\u0437\u0430 \u0432 1.5-2.5 \u043d\u0430 \u043c\u043e\u0438\u0445 \u0442\u0435\u0441\u0442\u0430\u0445. \u041e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u044e \u0440\u0435\u0448\u0438\u043b \u043f\u043e\u043a\u0430 \u043e\u0441\u0442\u0430\u0432\u0438\u0442\u044c.<\/p>\n<p>  \u0412 Java \u043e\u0441\u043d\u043e\u0432\u043d\u044b\u0435 \u0442\u0438\u043f\u044b \u0442\u0430\u0431\u043b\u0438\u0446 HashMap \u0438 TreeMap. \u0414\u043b\u044f \u0442\u0430\u0431\u043b\u0438\u0446\u044b \u043e\u0431\u044a\u0435\u043a\u0442 \u2192 \u0443\u0437\u0435\u043b \u043f\u043e \u0443\u043c\u043e\u043b\u0447\u0430\u043d\u0438\u044e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f HashMap. \u041e\u0434\u043d\u0430\u043a\u043e \u043c\u043e\u0436\u043d\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0438 TreeMap \u0441\u043e \u0441\u043f\u0435\u0446\u0438\u0444\u0438\u0447\u0435\u0441\u043a\u0438\u043c \u0434\u043b\u044f \u0437\u0430\u0434\u0430\u0447\u0438 Comparator\u2019\u043e\u043c. \u0412 \u044d\u0442\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 indexOf(obj) \u0438 remove(obj) \u0431\u0443\u0434\u0435\u0442 \u0438\u0441\u043a\u0430\u0442\u044c\/\u0443\u0434\u0430\u043b\u044f\u0442\u044c \u0442\u043e\u0442 \u043e\u0431\u044a\u0435\u043a\u0442, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0440\u0430\u0432\u0435\u043d \u0443\u043a\u0430\u0437\u0430\u043d\u043d\u043e\u043c\u0443 \u043e\u0431\u044a\u0435\u043a\u0442\u0443 \u0441\u043e\u0433\u043b\u0430\u0441\u043d\u043e \u043a\u043e\u0434\u0443 Comparator\u2019\u0430. \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u043c\u044b \u0445\u0440\u0430\u043d\u0438\u043c \u0441\u043f\u0438\u0441\u043e\u043a \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u0435\u0439, \u0430 \u043a\u043e\u043c\u043f\u0430\u0440\u0430\u0442\u043e\u0440 \u0441\u0440\u0430\u0432\u043d\u0438\u0432\u0430\u0435\u0442 \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u0435\u0439 \u0442\u043e\u043b\u044c\u043a\u043e \u043f\u043e \u0438\u043c\u0435\u043d\u0438. \u0422\u043e\u0433\u0434\u0430 \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u043e\u0442\u0432\u0435\u0442\u0438\u0442\u044c \u043d\u0430 \u0432\u043e\u043f\u0440\u043e\u0441 \u201c\u0412 \u043a\u0430\u043a\u0438\u0445 \u043f\u043e\u0437\u0438\u0446\u0438\u044f\u0445 \u0441\u043f\u0438\u0441\u043a\u0430 \u043d\u0430\u0445\u043e\u0434\u044f\u0442\u0441\u044f \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u0438 \u0441 \u0438\u043c\u0435\u043d\u0435\u043c \u2018\u041d\u0430\u043f\u043e\u043b\u0435\u043e\u043d?\u2019\u201d. \u0418\u043b\u0438 \u0443\u0434\u0430\u043b\u0438\u0442\u044c \u0438\u0437 \u0441\u043f\u0438\u0441\u043a\u0430 \u0432\u0441\u0435\u0445 \u041d\u0430\u043f\u043e\u043b\u0435\u043e\u043d\u043e\u0432 :).<\/p>\n<p>  \u0421\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u043d\u0435 \u043f\u043e\u0434\u0434\u0435\u0440\u0436\u0438\u0432\u0430\u0435\u0442 null. \u0418\u0441\u043f\u0440\u0430\u0432\u0438\u0442\u044c \u043c\u043e\u0436\u043d\u043e, \u043d\u043e \u043d\u0435\u0442 \u043e\u0449\u0443\u0449\u0435\u043d\u0438\u044f \u0442\u043e\u0433\u043e, \u0447\u0442\u043e \u044d\u0442\u043e \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e.<\/p>\n<p>  \u041a\u0430\u0441\u0430\u0435\u043c\u043e \u0442\u043e\u0433\u043e, \u0447\u0442\u043e \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u00ab\u0443\u043c\u0435\u0435\u0442 \u0432\u0441\u0451\u00bb \u044f, \u043a\u043e\u043d\u0435\u0447\u043d\u043e, \u043d\u0435\u043c\u043d\u043e\u0433\u043e \u0441\u043b\u0443\u043a\u0430\u0432\u0438\u043b. \u041a\u043e\u043d\u0435\u0447\u043d\u043e, \u043f\u0440\u0438 \u0440\u0430\u0431\u043e\u0442\u0435 \u0441 \u0435\u0434\u0438\u043d\u0438\u0447\u043d\u044b\u043c\u0438 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430\u043c\u0438 \u0432\u0441\u0451 \u0445\u043e\u0440\u043e\u0448\u043e \u0438 \u043f\u0440\u0438 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u043d\u044b\u0445 \u0443\u0441\u043b\u043e\u0432\u0438\u044f\u0445 \u0434\u0430\u0436\u0435 \u0437\u0430 \u043b\u043e\u0433\u0430\u0440\u0438\u0444\u043c. \u041e\u0434\u043d\u0430\u043a\u043e \u043e\u043d\u0430 \u043d\u0435 \u0443\u043c\u0435\u0435\u0442 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0432\u0435\u0449\u0435\u0439, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0443\u043c\u0435\u044e\u0442 \u0434\u0440\u0443\u0433\u0438\u0435 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b. \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0414\u0435\u043a\u0430\u0440\u0442\u043e\u0432\u043e \u0434\u0435\u0440\u0435\u0432\u043e \u0441 \u043d\u0435\u044f\u0432\u043d\u044b\u043c \u043a\u043b\u044e\u0447\u043e\u043c, \u043e \u043d\u0451\u043c \u0431\u044b\u043b\u0438 \u0441\u0442\u0430\u0442\u044c\u0438 \u043d\u0430 \u0445\u0430\u0431\u0440\u0435. \u041e\u043d\u043e \u043d\u0435 \u0443\u043c\u0435\u0435\u0442 \u0431\u044b\u0441\u0442\u0440\u043e \u0434\u0435\u043b\u0430\u0442\u044c indexOf, \u043d\u043e \u0443\u043c\u0435\u0435\u0442 \u0437\u0430 \u043b\u043e\u0433\u0430\u0440\u0438\u0444\u043c (\u0432 \u0441\u0440\u0435\u0434\u043d\u0435\u043c, \u043d\u0435 \u0433\u0430\u0440\u0430\u043d\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043e) \u0434\u0435\u043b\u0430\u0442\u044c sublist \u0438 \u043a\u043e\u043d\u043a\u0430\u0442\u0435\u043d\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0434\u0432\u0430 \u0441\u043f\u0438\u0441\u043a\u0430 \u0432 \u043e\u0434\u0438\u043d, \u043f\u043b\u044e\u0441 \u0435\u0433\u043e \u043c\u043e\u0436\u043d\u043e \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u043f\u0435\u0440\u0441\u0438\u0441\u0442\u0435\u043d\u0442\u043d\u044b\u043c.<\/p>\n<h2>\u041f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c<\/h2>\n<p>  \u0412 \u0434\u0436\u0430\u0432\u0435 \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u043f\u0440\u0438\u043d\u044f\u0442\u043e \u0438\u0437\u043c\u0435\u0440\u044f\u0442\u044c \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u0444\u0440\u0435\u0439\u043c\u0432\u043e\u0440\u043a\u0430 jmh. \u0422\u0435\u0441\u0442\u044b \u043f\u0440\u043e\u0432\u043e\u0434\u0438\u043b\u0438\u0441\u044c \u043d\u0430 MacBook Pro 2017 \u0433\u043e\u0434\u0430 \u043f\u043e\u0434 Java11.<\/p>\n<p>  \u042f \u0441\u0440\u0430\u0432\u043d\u0438\u043b \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u0441\u0442\u0430\u043d\u0434\u0430\u0440\u0442\u043d\u043e\u0433\u043e ArrayList, TreeList \u0438\u0437 apache common-collections, \u0438 \u0434\u0432\u0430 \u0441\u0432\u043e\u0438\u0445 \u043a\u043b\u0430\u0441\u0441\u0430 IndexedTreeList \u0438 IndexedTreeListSet \u043d\u0430 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u0438\u0445 \u0441\u0446\u0435\u043d\u0430\u0440\u0438\u044f\u0445. \u0412 \u043a\u0430\u0436\u0434\u043e\u043c \u0441\u0446\u0435\u043d\u0430\u0440\u0438\u0438 \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u043b\u043e\u0441\u044c 1000 \u043e\u0434\u043d\u043e\u0442\u0438\u043f\u043d\u044b\u0445 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u043d\u0430\u0434\u043e \u0443\u043c\u043d\u043e\u0436\u0430\u0442\u044c \u043d\u0430 1000.  <\/p>\n<div class=\"spoiler\"><b class=\"spoiler_title\">\u041a\u043e\u0434 \u043f\u043e\u0434 \u0441\u043f\u043e\u0439\u043b\u0435\u0440\u043e\u043c<\/b><\/p>\n<div class=\"spoiler_text\">\n<pre><code class=\"java\">@Fork(1) @Warmup(iterations = 3) @Measurement(iterations = 5) public class PerformanceCompare {      public static final Map&lt;String, Class&gt; CLASSES = Stream.of(TreeList.class, IndexedTreeListSet.class, IndexedTreeList.class,             ArrayList.class)             .collect(Collectors.toMap(c -&gt; c.getSimpleName(), c -&gt; c));      public static final int ITERATIONS = 1000;      @State(Scope.Benchmark)     public static class Plan {          @Param({&quot;10&quot;, &quot;100&quot;, &quot;1000&quot;, &quot;10000&quot;, &quot;100000&quot;, &quot;1000000&quot;\/*, &quot;10000000&quot;*\/})         public int size;          @Param({&quot;ArrayList&quot;, &quot;TreeList&quot;, &quot;IndexedTreeList&quot;, &quot;IndexedTreeListSet&quot;})         public String className;          private Random random;         private List&lt;Integer&gt; list;          @Setup         public void init() throws IllegalAccessException, InstantiationException {             random = new Random();             list = (List&lt;Integer&gt;) CLASSES.get(className).newInstance();              for (int i = 0; i &lt; size; i++) {                 list.add(i);             }         }     }       @Benchmark     public void indexOfKnown(Plan plan, Blackhole blackhole) {         List&lt;Integer&gt; list = plan.list;         Random random = plan.random;         int value = 0;         for (int i = 0; i &lt; ITERATIONS; i++) {             value = list.indexOf(random.nextInt(plan.size));         }         blackhole.consume(value);     }      @Benchmark     public void indexOfUnknown(Plan plan, Blackhole blackhole) {         List&lt;Integer&gt; list = plan.list;         Random random = plan.random;         int value = 0;         for (int i = 0; i &lt; ITERATIONS; i++) {             value += list.indexOf(random.nextInt());         }         blackhole.consume(value);     }      @Benchmark     public void addRemoveRandom(Plan plan, Blackhole blackhole) {         List&lt;Integer&gt; list = plan.list;         Random random = plan.random;         int value = 0;         for (int i = 0; i &lt; ITERATIONS; i++) {             list.add(random.nextInt(list.size() + 1), random.nextInt());             value += list.remove(random.nextInt(list.size()));         }         blackhole.consume(value);     }      @Benchmark     public void get(Plan plan, Blackhole blackhole) {         List&lt;Integer&gt; list = plan.list;         Random random = plan.random;         int value = 0;         for (int i = 0; i &lt; ITERATIONS; i++) {             value += list.get(random.nextInt(list.size()));         }         blackhole.consume(value);     }      @Timeout(time = 1, timeUnit = TimeUnit.MILLISECONDS)     public static void main(String[] args) throws RunnerException {         Options opt = new OptionsBuilder()                 .include(PerformanceCompare.class.getSimpleName())                 .forks(1) \/\/                .jvmArgs(&quot;-Xms2048m&quot;, &quot;-Xmx2048m&quot;, &quot;-XX:MaxDirectMemorySize=512M&quot;)                 .build();          new Runner(opt).run();     } }<\/code><\/pre>\n<p>  <\/div>\n<\/div>\n<p>  \u0414\u043b\u044f \u043d\u0430\u0447\u0430\u043b\u0430 \u044f \u0441\u0440\u0430\u0432\u043d\u0438\u043b \u0441\u043a\u043e\u0440\u043e\u0441\u0442\u044c \u0434\u043e\u0441\u0442\u0430\u0432\u0430\u043d\u0438\u044f \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u043e\u0433\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u0438\u0437 \u0441\u043f\u0438\u0441\u043a\u0430. \u041f\u0440\u0435\u0434\u0443\u043f\u0440\u0435\u0436\u0443 \u0441\u0440\u0430\u0437\u0443, \u0447\u0442\u043e \u0432 \u0434\u0430\u043d\u043d\u043e\u043c \u0442\u0435\u0441\u0442\u0435 \u043d\u0430\u043a\u043b\u0430\u0434\u043d\u044b\u0435 \u0440\u0430\u0441\u0445\u043e\u0434\u044b \u043e\u0447\u0435\u043d\u044c \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u044b. \u0420\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u044b, \u043f\u0440\u0438\u0431\u043b\u0438\u0436\u0430\u044e\u0449\u0438\u0435\u0441\u044f \u043a 100000 * 1000 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u0432 \u0441\u0435\u043a\u0443\u043d\u0434\u0443 \u0441\u0438\u043b\u044c\u043d\u043e \u0438\u0441\u043a\u0430\u0436\u0435\u043d\u044b.  <\/p>\n<div class=\"spoiler\"><b class=\"spoiler_title\">\u0420\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u0442\u0435\u0441\u0442\u0430 get<\/b><\/p>\n<div class=\"spoiler_text\">\n<pre><code class=\"plaintext\">PerformanceCompare.get                       ArrayList       10  thrpt    5  79865.412 \u00b1 10145.202  ops\/s PerformanceCompare.get                       ArrayList      100  thrpt    5  81862.243 \u00b1   983.727  ops\/s PerformanceCompare.get                       ArrayList     1000  thrpt    5  81033.507 \u00b1  4540.206  ops\/s PerformanceCompare.get                       ArrayList    10000  thrpt    5  64096.123 \u00b1  1430.361  ops\/s PerformanceCompare.get                       ArrayList   100000  thrpt    5  41289.491 \u00b1 11286.114  ops\/s PerformanceCompare.get                       ArrayList  1000000  thrpt    5   8598.944 \u00b1  2048.461  ops\/s PerformanceCompare.get                        TreeList       10  thrpt    5  33912.275 \u00b1  3754.284  ops\/s PerformanceCompare.get                        TreeList      100  thrpt    5  21346.854 \u00b1   863.588  ops\/s PerformanceCompare.get                        TreeList     1000  thrpt    5  14808.414 \u00b1   508.098  ops\/s PerformanceCompare.get                        TreeList    10000  thrpt    5   8679.384 \u00b1   109.250  ops\/s PerformanceCompare.get                        TreeList   100000  thrpt    5   4605.998 \u00b1  1028.945  ops\/s PerformanceCompare.get                        TreeList  1000000  thrpt    5   2241.381 \u00b1   768.147  ops\/s PerformanceCompare.get                 IndexedTreeList       10  thrpt    5  34054.357 \u00b1  3682.829  ops\/s PerformanceCompare.get                 IndexedTreeList      100  thrpt    5  21934.002 \u00b1  2339.947  ops\/s PerformanceCompare.get                 IndexedTreeList     1000  thrpt    5  14626.691 \u00b1   369.893  ops\/s PerformanceCompare.get                 IndexedTreeList    10000  thrpt    5   7386.863 \u00b1   342.150  ops\/s PerformanceCompare.get                 IndexedTreeList   100000  thrpt    5   4562.126 \u00b1   352.772  ops\/s PerformanceCompare.get                 IndexedTreeList  1000000  thrpt    5   2105.718 \u00b1   702.064  ops\/s PerformanceCompare.get              IndexedTreeListSet       10  thrpt    5  33317.503 \u00b1  2307.829  ops\/s PerformanceCompare.get              IndexedTreeListSet      100  thrpt    5  21247.440 \u00b1  1253.386  ops\/s PerformanceCompare.get              IndexedTreeListSet     1000  thrpt    5  14665.557 \u00b1   487.833  ops\/s PerformanceCompare.get              IndexedTreeListSet    10000  thrpt    5   7667.214 \u00b1    80.093  ops\/s PerformanceCompare.get              IndexedTreeListSet   100000  thrpt    5   3454.023 \u00b1    82.994  ops\/s PerformanceCompare.get              IndexedTreeListSet  1000000  thrpt    5   1768.701 \u00b1    35.878  ops\/s <\/code><\/pre>\n<p>  <\/div>\n<\/div>\n<p>  \u0422\u0443\u0442, \u043a\u0430\u043a \u043d\u0438 \u0441\u0442\u0440\u0430\u043d\u043d\u043e, \u0441\u0430\u043c\u044b\u0439 \u0431\u043e\u043b\u044c\u0448\u043e\u0439 \u0438\u043d\u0442\u0435\u0440\u0435\u0441 \u0432\u044b\u0437\u044b\u0432\u0430\u0435\u0442 \u0441\u0442\u0430\u043d\u0434\u0430\u0440\u0442\u043d\u044b\u0439 ArrayList. \u0422\u0435\u043e\u0440\u0435\u0442\u0438\u0447\u0435\u0441\u043a\u0438 \u0441\u043a\u043e\u0440\u043e\u0441\u0442\u044c \u0434\u043e\u0441\u0442\u0430\u0432\u0430\u043d\u0438\u044f \u0438\u0437 \u043d\u0435\u0433\u043e \u0434\u043e\u043b\u0436\u043d\u0430 \u0431\u044b\u0442\u044c \u043a\u043e\u043d\u0441\u0442\u0430\u043d\u0442\u043e\u0439 \u0438 \u043d\u0435 \u0437\u0430\u0432\u0438\u0441\u0435\u0442\u044c \u043e\u0442 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432. \u041d\u0430 \u043f\u0440\u0430\u043a\u0442\u0438\u043a\u0435 \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u0441\u043d\u0430\u0447\u0430\u043b\u0430 \u0434\u0435\u0440\u0436\u0438\u0442\u0441\u044f \u043e\u043a\u043e\u043b\u043e 90000 * 1000 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u0432 \u0441\u0435\u043a\u0443\u043d\u0434\u0443 (\u043f\u043e\u043c\u043d\u0438\u043c \u043f\u0440\u043e \u043d\u0430\u043a\u043b\u0430\u0434\u043d\u044b\u0435 \u0440\u0430\u0441\u0445\u043e\u0434\u044b), \u043d\u043e \u043f\u0440\u0438 \u0434\u043b\u0438\u043d\u0435 \u0441\u043f\u0438\u0441\u043a\u0430 \u0432 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0442\u044b\u0441\u044f\u0447 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u043d\u0430\u0447\u0438\u043d\u0430\u0435\u0442 \u043f\u0440\u043e\u0441\u0435\u0434\u0430\u0442\u044c. \u0412\u0438\u043d\u043e\u0439 \u0442\u043e\u043c\u0443 \u0432\u0441\u0451 \u0431\u043e\u043b\u0435\u0435 \u0447\u0430\u0441\u0442\u044b\u0439 cache miss: \u0432 \u043a\u044d\u0448\u0435 \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u043e\u0440\u0430 \u043d\u0435 \u043e\u043a\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u043d\u0443\u0436\u043d\u044b\u0445 \u0434\u0430\u043d\u043d\u044b\u0445 \u0438 \u043d\u0443\u0436\u043d\u043e \u0432\u0441\u0451 \u0447\u0430\u0449\u0435 \u0445\u043e\u0434\u0438\u0442\u044c \u0437\u0430 \u0434\u0430\u043d\u043d\u044b\u043c\u0438 \u0432 \u043e\u043f\u0435\u0440\u0430\u0442\u0438\u0432\u043d\u0443\u044e \u043f\u0430\u043c\u044f\u0442\u044c. \u041f\u0440\u0438 \u043c\u0438\u043b\u043b\u0438\u043e\u043d\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0441\u043a\u043e\u0440\u043e\u0441\u0442\u044c \u043f\u0440\u043e\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u044f \u0442\u0435\u0441\u0442\u0430 \u043d\u0438\u0436\u0435 \u0432 10 \u0440\u0430\u0437, \u043d\u043e \u043d\u0430 \u043f\u0440\u0430\u043a\u0442\u0438\u043a\u0435 \u043f\u0440\u043e\u0441\u0435\u0434\u0430\u043d\u0438\u0435 \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u0435\u0449\u0435 \u0431\u043e\u043b\u044c\u0448\u0435.<\/p>\n<p>  TreeList, IndexedTreeList \u0438 IndexedTreeListSet \u043e\u0436\u0438\u0434\u0430\u0435\u043c\u043e \u043f\u043e\u043a\u0430\u0437\u044b\u0432\u0430\u044e\u0442 \u0441\u0445\u043e\u0436\u0438\u0439 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442. \u041e\u0436\u0438\u0434\u0430\u0435\u043c\u043e \u0441\u0438\u043b\u044c\u043d\u043e \u043c\u0435\u0434\u043b\u0435\u043d\u043d\u0435\u0435, \u0447\u0435\u043c ArrayList. \u0414\u0430\u0436\u0435 \u043f\u0440\u0438 \u043c\u0430\u043b\u0435\u043d\u044c\u043a\u043e\u043c \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 TreeList \u0432 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0440\u0430\u0437 \u043c\u0435\u0434\u043b\u0435\u043d\u043d\u0435\u0435, \u0447\u0435\u043c ArrayList, \u0445\u043e\u0442\u044f \u0442\u0435\u0441\u0442 \u043f\u043e\u043a\u0430\u0437\u044b\u0432\u0430\u0435\u0442 \u0440\u0430\u0437\u043d\u0438\u0446\u0443 \u0432\u0441\u0435\u0433\u043e \u0432 2 \u0440\u0430\u0437\u0430.<br \/>  \u0421\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0439 \u0442\u0435\u0441\u0442 addRemoveRandom. \u0417\u0434\u0435\u0441\u044c \u0432 \u043a\u0430\u0436\u0434\u043e\u043c \u0442\u0435\u0441\u0442\u0435 \u044f \u0432\u0441\u0442\u0430\u0432\u043b\u044f\u044e \u0432 \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u0443\u044e \u043f\u043e\u0437\u0438\u0446\u0438\u044e \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0438 \u0443\u0434\u0430\u043b\u044f\u044e \u0438\u0437 \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u043e\u0439 \u043f\u043e\u0437\u0438\u0446\u0438\u0438 \u044d\u043b\u0435\u043c\u0435\u043d\u0442.  <\/p>\n<div class=\"spoiler\"><b class=\"spoiler_title\">\u0420\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u0442\u0435\u0441\u0442\u0430 addRemoveRandom<\/b><\/p>\n<div class=\"spoiler_text\">\n<pre><code class=\"plaintext\">PerformanceCompare.addRemoveRandom           ArrayList       10  thrpt    5  12440.764 \u00b1   485.642  ops\/s PerformanceCompare.addRemoveRandom           ArrayList      100  thrpt    5   9880.123 \u00b1   464.014  ops\/s PerformanceCompare.addRemoveRandom           ArrayList     1000  thrpt    5   5288.905 \u00b1  1219.055  ops\/s PerformanceCompare.addRemoveRandom           ArrayList    10000  thrpt    5   1024.942 \u00b1   179.366  ops\/s PerformanceCompare.addRemoveRandom           ArrayList   100000  thrpt    5     91.219 \u00b1    25.380  ops\/s PerformanceCompare.addRemoveRandom           ArrayList  1000000  thrpt    5      5.499 \u00b1     0.400  ops\/s PerformanceCompare.addRemoveRandom            TreeList       10  thrpt    5   6242.607 \u00b1   350.290  ops\/s PerformanceCompare.addRemoveRandom            TreeList      100  thrpt    5   3117.945 \u00b1   116.066  ops\/s PerformanceCompare.addRemoveRandom            TreeList     1000  thrpt    5   1829.778 \u00b1    80.516  ops\/s PerformanceCompare.addRemoveRandom            TreeList    10000  thrpt    5   1230.077 \u00b1    53.381  ops\/s PerformanceCompare.addRemoveRandom            TreeList   100000  thrpt    5    443.571 \u00b1    69.207  ops\/s PerformanceCompare.addRemoveRandom            TreeList  1000000  thrpt    5    308.963 \u00b1    84.077  ops\/s PerformanceCompare.addRemoveRandom     IndexedTreeList       10  thrpt    5   3556.511 \u00b1   144.596  ops\/s PerformanceCompare.addRemoveRandom     IndexedTreeList      100  thrpt    5   2120.777 \u00b1    83.848  ops\/s PerformanceCompare.addRemoveRandom     IndexedTreeList     1000  thrpt    5   1211.112 \u00b1    92.288  ops\/s PerformanceCompare.addRemoveRandom     IndexedTreeList    10000  thrpt    5    789.458 \u00b1    19.450  ops\/s PerformanceCompare.addRemoveRandom     IndexedTreeList   100000  thrpt    5    302.989 \u00b1    40.030  ops\/s PerformanceCompare.addRemoveRandom     IndexedTreeList  1000000  thrpt    5    178.822 \u00b1    92.853  ops\/s PerformanceCompare.addRemoveRandom  IndexedTreeListSet       10  thrpt    5   4138.007 \u00b1   119.943  ops\/s PerformanceCompare.addRemoveRandom  IndexedTreeListSet      100  thrpt    5   2435.803 \u00b1    20.276  ops\/s PerformanceCompare.addRemoveRandom  IndexedTreeListSet     1000  thrpt    5   1445.054 \u00b1   276.909  ops\/s PerformanceCompare.addRemoveRandom  IndexedTreeListSet    10000  thrpt    5    972.256 \u00b1    19.987  ops\/s PerformanceCompare.addRemoveRandom  IndexedTreeListSet   100000  thrpt    5    366.608 \u00b1    94.487  ops\/s PerformanceCompare.addRemoveRandom  IndexedTreeListSet  1000000  thrpt    5    227.677 \u00b1    48.276  ops\/s <\/code><\/pre>\n<p>  <\/div>\n<\/div>\n<p>  \u041c\u043e\u0436\u043d\u043e \u0431\u044b\u043b\u043e \u043f\u0440\u0435\u0434\u043f\u043e\u043b\u043e\u0436\u0438\u0442\u044c, \u0447\u0442\u043e ArrayList \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u0431\u044b\u0441\u0442\u0440\u0435\u0435 \u043d\u0430 \u043c\u0430\u043b\u0435\u043d\u044c\u043a\u0438\u0445 \u0441\u043f\u0438\u0441\u043a\u0430\u0445. \u041e\u0434\u043d\u0430\u043a\u043e \u0442\u043e, \u0447\u0442\u043e \u043e\u043d \u0432\u044b\u0438\u0433\u0440\u044b\u0432\u0430\u0435\u0442 \u0432 \u044d\u0442\u043e\u043c \u0442\u0435\u0441\u0442\u0435 \u043d\u0430 \u0441\u043f\u0438\u0441\u043a\u0430\u0445 \u0432\u043f\u043b\u043e\u0442\u044c \u0434\u043e 10000 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0432\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u043e. \u0412\u0438\u0434\u0438\u043c\u043e, System.arrayCopy \u043e\u0447\u0435\u043d\u044c \u0445\u043e\u0440\u043e\u0448\u043e \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u043d \u0438 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442 \u0432\u0441\u0435 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e\u0441\u0442\u0438 \u0441\u043e\u0432\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445 \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u043e\u0440\u043e\u0432. \u041d\u0430\u0447\u0438\u043d\u0430\u044f \u0441 10000 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0441\u043f\u0435\u0446\u0438\u0430\u043b\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0435 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0434\u0430\u043d\u043d\u044b\u0445 \u043d\u0430\u0447\u0438\u043d\u0430\u044e\u0442 \u0432\u044b\u0438\u0433\u0440\u044b\u0432\u0430\u0442\u044c. \u041f\u0440\u0438 1000000 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0440\u0430\u0437\u043d\u0438\u0446\u0430 \u0441\u043a\u043e\u0440\u043e\u0441\u0442\u0438 \u0432 30-50 \u0440\u0430\u0437.<\/p>\n<p>  IndexedTreeList \u0438 IndexedTreeListSet \u043e\u0436\u0438\u0434\u0430\u0435\u043c\u043e \u043c\u0435\u0434\u043b\u0435\u043d\u043d\u0435\u0435, \u0447\u0435\u043c TreeList. \u041f\u0440\u0438\u043c\u0435\u0440\u043d\u043e \u0432 1.5 \u2014 2 \u0440\u0430\u0437\u0430.<\/p>\n<p>  \u041e\u0441\u0442\u0430\u0432\u0448\u0438\u0435\u0441\u044f 2 \u0442\u0435\u0441\u0442\u0430 indexOfKnown \u0438 indexOfUnknown \u043a\u0430\u043a \u0440\u0430\u0437 \u0434\u043e\u043b\u0436\u043d\u044b \u043f\u0440\u043e\u0434\u0435\u043c\u043e\u043d\u0441\u0442\u0440\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u043e\u0441\u043d\u043e\u0432\u043d\u0443\u044e \u043e\u0441\u043e\u0431\u0435\u043d\u043d\u043e\u0441\u0442\u044c \u0434\u0430\u043d\u043d\u043e\u0439 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b. \u0420\u0430\u0437\u043b\u0438\u0447\u0438\u0435 \u0442\u0435\u0441\u0442\u043e\u0432 \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e \u0432 \u043e\u0434\u043d\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u043c\u044b \u0438\u0449\u0435\u043c \u044d\u043b\u0435\u043c\u0435\u043d\u0442, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0435\u0441\u0442\u044c \u0432 \u0441\u043f\u0438\u0441\u043a\u0435, \u0430 \u0432 \u0434\u0440\u0443\u0433\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u0438\u0449\u0435\u043c \u044d\u043b\u0435\u043c\u0435\u043d\u0442, \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u0432 \u0441\u043f\u0438\u0441\u043a\u0435 \u043d\u0435\u0442.  <\/p>\n<div class=\"spoiler\"><b class=\"spoiler_title\">\u0420\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u0442\u0435\u0441\u0442\u043e\u0432 indexOfKnown \u0438 indexOfUnknown<\/b><\/p>\n<div class=\"spoiler_text\">\n<pre><code class=\"plaintext\">PerformanceCompare.indexOfKnown              ArrayList       10  thrpt    5  41424.356 \u00b1   549.047  ops\/s PerformanceCompare.indexOfKnown              ArrayList      100  thrpt    5  17216.477 \u00b1  1444.744  ops\/s PerformanceCompare.indexOfKnown              ArrayList     1000  thrpt    5   2296.306 \u00b1    76.372  ops\/s PerformanceCompare.indexOfKnown              ArrayList    10000  thrpt    5    233.863 \u00b1    26.926  ops\/s PerformanceCompare.indexOfKnown              ArrayList   100000  thrpt    5     23.208 \u00b1     2.776  ops\/s PerformanceCompare.indexOfKnown              ArrayList  1000000  thrpt    5      0.919 \u00b1     0.455  ops\/s PerformanceCompare.indexOfKnown               TreeList       10  thrpt    5  26740.708 \u00b1  1323.125  ops\/s PerformanceCompare.indexOfKnown               TreeList      100  thrpt    5   5670.923 \u00b1    99.638  ops\/s PerformanceCompare.indexOfKnown               TreeList     1000  thrpt    5    745.408 \u00b1    26.827  ops\/s PerformanceCompare.indexOfKnown               TreeList    10000  thrpt    5     52.288 \u00b1     1.362  ops\/s PerformanceCompare.indexOfKnown               TreeList   100000  thrpt    5      4.224 \u00b1     0.855  ops\/s PerformanceCompare.indexOfKnown               TreeList  1000000  thrpt    5      0.193 \u00b1     0.052  ops\/s PerformanceCompare.indexOfKnown        IndexedTreeList       10  thrpt    5  34485.128 \u00b1  1582.703  ops\/s PerformanceCompare.indexOfKnown        IndexedTreeList      100  thrpt    5  29209.412 \u00b1  1544.268  ops\/s PerformanceCompare.indexOfKnown        IndexedTreeList     1000  thrpt    5  21139.584 \u00b1  1442.867  ops\/s PerformanceCompare.indexOfKnown        IndexedTreeList    10000  thrpt    5  12544.306 \u00b1   312.097  ops\/s PerformanceCompare.indexOfKnown        IndexedTreeList   100000  thrpt    5   3538.201 \u00b1   272.537  ops\/s PerformanceCompare.indexOfKnown        IndexedTreeList  1000000  thrpt    5   1420.119 \u00b1   538.476  ops\/s PerformanceCompare.indexOfKnown     IndexedTreeListSet       10  thrpt    5  39201.995 \u00b1  1887.065  ops\/s PerformanceCompare.indexOfKnown     IndexedTreeListSet      100  thrpt    5  34204.112 \u00b1  1122.517  ops\/s PerformanceCompare.indexOfKnown     IndexedTreeListSet     1000  thrpt    5  25374.557 \u00b1  1596.746  ops\/s PerformanceCompare.indexOfKnown     IndexedTreeListSet    10000  thrpt    5  14291.317 \u00b1   391.180  ops\/s PerformanceCompare.indexOfKnown     IndexedTreeListSet   100000  thrpt    5   4215.898 \u00b1   283.680  ops\/s PerformanceCompare.indexOfKnown     IndexedTreeListSet  1000000  thrpt    5   1729.100 \u00b1  1260.815  ops\/s PerformanceCompare.indexOfUnknown            ArrayList       10  thrpt    5  59053.313 \u00b1  1845.665  ops\/s PerformanceCompare.indexOfUnknown            ArrayList      100  thrpt    5  10867.572 \u00b1   142.823  ops\/s PerformanceCompare.indexOfUnknown            ArrayList     1000  thrpt    5   1186.583 \u00b1    28.003  ops\/s PerformanceCompare.indexOfUnknown            ArrayList    10000  thrpt    5    120.953 \u00b1     4.146  ops\/s PerformanceCompare.indexOfUnknown            ArrayList   100000  thrpt    5     11.936 \u00b1     0.320  ops\/s PerformanceCompare.indexOfUnknown            ArrayList  1000000  thrpt    5      0.566 \u00b1     0.335  ops\/s PerformanceCompare.indexOfUnknown             TreeList       10  thrpt    5  28134.237 \u00b1  2291.670  ops\/s PerformanceCompare.indexOfUnknown             TreeList      100  thrpt    5   3153.930 \u00b1   158.734  ops\/s PerformanceCompare.indexOfUnknown             TreeList     1000  thrpt    5    322.383 \u00b1    44.245  ops\/s PerformanceCompare.indexOfUnknown             TreeList    10000  thrpt    5     25.674 \u00b1     1.787  ops\/s PerformanceCompare.indexOfUnknown             TreeList   100000  thrpt    5      1.867 \u00b1     0.291  ops\/s PerformanceCompare.indexOfUnknown             TreeList  1000000  thrpt    5      0.093 \u00b1     0.008  ops\/s PerformanceCompare.indexOfUnknown      IndexedTreeList       10  thrpt    5  66625.126 \u00b1  5232.668  ops\/s PerformanceCompare.indexOfUnknown      IndexedTreeList      100  thrpt    5  70038.055 \u00b1  5803.848  ops\/s PerformanceCompare.indexOfUnknown      IndexedTreeList     1000  thrpt    5  63240.467 \u00b1   885.956  ops\/s PerformanceCompare.indexOfUnknown      IndexedTreeList    10000  thrpt    5  54731.988 \u00b1  3950.150  ops\/s PerformanceCompare.indexOfUnknown      IndexedTreeList   100000  thrpt    5  22049.476 \u00b1   821.924  ops\/s PerformanceCompare.indexOfUnknown      IndexedTreeList  1000000  thrpt    5   9459.862 \u00b1   804.738  ops\/s PerformanceCompare.indexOfUnknown   IndexedTreeListSet       10  thrpt    5  70274.968 \u00b1 15830.355  ops\/s PerformanceCompare.indexOfUnknown   IndexedTreeListSet      100  thrpt    5  71017.685 \u00b1  6920.447  ops\/s PerformanceCompare.indexOfUnknown   IndexedTreeListSet     1000  thrpt    5  66405.960 \u00b1  1127.231  ops\/s PerformanceCompare.indexOfUnknown   IndexedTreeListSet    10000  thrpt    5  57983.963 \u00b1  3276.142  ops\/s PerformanceCompare.indexOfUnknown   IndexedTreeListSet   100000  thrpt    5  41277.110 \u00b1  9919.893  ops\/s PerformanceCompare.indexOfUnknown   IndexedTreeListSet  1000000  thrpt    5   9840.185 \u00b1  2159.352  ops\/s <\/code><\/pre>\n<p>  <\/div>\n<\/div>\n<p>  \u0417\u0434\u0435\u0441\u044c \u0443 ArrayList \u0438 TreeList \u043f\u043e\u0447\u0442\u0438 \u0431\u0435\u0437 \u0441\u044e\u0440\u043f\u0440\u0438\u0437\u043e\u0432. \u0421 \u0443\u0432\u0435\u043b\u0438\u0447\u0435\u043d\u0438\u0435\u043c \u0440\u0430\u0437\u043c\u0435\u0440\u0430 \u0441\u043a\u043e\u0440\u043e\u0441\u0442\u044c \u043f\u0430\u0434\u0430\u0435\u0442 \u043f\u0440\u0430\u043a\u0442\u0438\u0447\u0435\u0441\u043a\u0438 \u043b\u0438\u043d\u0435\u0439\u043d\u043e. \u041f\u043e\u0438\u0441\u043a \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u043d\u0435 \u0438\u0437 \u0441\u043f\u0438\u0441\u043a\u0430 \u043e\u0436\u0438\u0434\u0430\u0435\u043c\u043e \u0432 2 \u0440\u0430\u0437\u0430 \u043c\u0435\u0434\u043b\u0435\u043d\u043d\u0435\u0435, \u0447\u0435\u043c \u043f\u043e\u0438\u0441\u043a \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u0438\u0437 \u0441\u043f\u0438\u0441\u043a\u0430, \u0442.\u043a. \u043d\u0430\u0434\u043e \u043f\u0440\u043e\u0439\u0442\u0438 \u0432\u0435\u0441\u044c \u043c\u0430\u0441\u0441\u0438\u0432 \u0432\u043c\u0435\u0441\u0442\u043e \u043f\u043e\u043b\u043e\u0432\u0438\u043d\u044b \u0432 \u0441\u0440\u0435\u0434\u043d\u0435\u043c.<\/p>\n<p>  \u0410 \u0432\u043e\u0442 IndexedTreeList \u0438 IndexedTreeListSet \u0437\u0434\u0435\u0441\u044c \u043f\u043e\u043a\u0430\u0437\u044b\u0432\u0430\u044e\u0442 \u043e\u0436\u0438\u0434\u0430\u0435\u043c\u043e \u0445\u043e\u0440\u043e\u0448\u0438\u0439 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442. \u042d\u0442\u0438 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0434\u0430\u043d\u043d\u044b\u0445 \u043f\u043e\u043a\u0430\u0437\u044b\u0432\u0430\u044e\u0442 \u0441\u0440\u0430\u0432\u043d\u0438\u043c\u0443\u044e \u0441 ArrayList \u0441\u043a\u043e\u0440\u043e\u0441\u0442\u044c \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u044f indexOf \u0434\u0430\u0436\u0435 \u043f\u0440\u0438 10 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430\u0445. \u041f\u0440\u0438 1000 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430\u0445 \u044d\u0442\u0438 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0431\u044b\u0441\u0442\u0440\u0435\u0435 \u0432 10 \u0440\u0430\u0437, \u043f\u0440\u0438 1000000 \u0431\u044b\u0441\u0442\u0440\u0435\u0435 \u0432 1000 \u0440\u0430\u0437. \u041f\u0440\u0438 \u043f\u043e\u0438\u0441\u043a\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430, \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u043d\u0435\u0442 \u0432 \u0441\u043f\u0438\u0441\u043a\u0435 \u043e\u043d\u0438 \u043e\u0436\u0438\u0434\u0430\u0435\u043c\u043e \u0434\u0430\u044e\u0442 \u043b\u0443\u0447\u0448\u0443\u044e \u0441\u043a\u043e\u0440\u043e\u0441\u0442\u044c, \u0447\u0435\u043c \u043f\u0440\u0438 \u043f\u043e\u0438\u0441\u043a\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u0438\u0437 \u0441\u043f\u0438\u0441\u043a\u0430.<\/p>\n<p>  \u041d\u0430 \u0447\u0442\u043e \u0435\u0449\u0435 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u043e \u043e\u0431\u0440\u0430\u0442\u0438\u0442\u044c \u0432\u043d\u0438\u043c\u0430\u043d\u0438\u0435, \u0442\u0430\u043a \u044d\u0442\u043e \u043d\u0430 \u043f\u0440\u043e\u0441\u0435\u0434\u0430\u043d\u0438\u0435 \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u0443 IndexedTreeList \u0438 IndexedTreeListSet \u0432 \u0442\u0435\u0441\u0442\u0435 indexOfUnknown. \u0422\u0443\u0442 \u0441\u0438\u0442\u0443\u0430\u0446\u0438\u044f \u0430\u043d\u0430\u043b\u043e\u0433\u0438\u0447\u043d\u0430\u044f \u0442\u043e\u0439, \u0447\u0442\u043e \u0431\u044b\u043b\u0430 \u0432 \u0442\u0435\u0441\u0442\u0435 \u0441 ArrayList.get. \u0422\u0435\u043e\u0440\u0435\u0442\u0438\u0447\u0435\u0441\u043a\u0438 \u043c\u044b \u043d\u0435 \u0434\u043e\u043b\u0436\u043d\u044b \u0431\u044b\u043b\u0438 \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u043f\u0430\u0434\u0435\u043d\u0438\u0435 \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438, \u0430 \u043d\u0430 \u043f\u0440\u0430\u043a\u0442\u0438\u043a\u0435, \u0438\u0437-\u0437\u0430 cache miss \u043f\u043e\u043b\u0443\u0447\u0438\u043b\u0438, \u043f\u0440\u0438\u0447\u0451\u043c \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u043e.<\/p>\n<h2>\u0412\u043c\u0435\u0441\u0442\u043e \u0437\u0430\u043a\u043b\u044e\u0447\u0435\u043d\u0438\u044f<\/h2>\n<p>  \u042f \u0434\u043e \u0441\u0438\u0445 \u043f\u043e\u0440 \u043d\u0435 \u0437\u043d\u0430\u044e, \u0435\u0441\u0442\u044c \u043b\u0438 \u0432 \u043f\u0440\u0435\u0434\u043b\u043e\u0436\u0435\u043d\u043d\u043e\u0439 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0435 \u043d\u043e\u0432\u0438\u0437\u043d\u0430 \u0438\u043b\u0438 \u043d\u0435\u0442. \u0421 \u043e\u0434\u043d\u043e\u0439 \u0441\u0442\u043e\u0440\u043e\u043d\u044b, \u0438\u0434\u0435\u044f \u043d\u0435 \u0441\u043b\u043e\u0436\u043d\u0430\u044f, \u0435\u0441\u043b\u0438 \u0437\u043d\u0430\u0442\u044c \u043a\u0430\u043a \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u0434\u0435\u0440\u0435\u0432\u043e \u043f\u043e \u043d\u0435\u044f\u0432\u043d\u043e\u043c\u0443 \u043a\u043b\u044e\u0447\u0443. \u0421 \u0434\u0440\u0443\u0433\u043e\u0439 \u0441\u0442\u043e\u0440\u043e\u043d\u044b, \u043e\u043f\u0438\u0441\u0430\u043d\u0438\u044f \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0441\u043e \u0442\u0430\u043a\u0438\u043c\u0438 \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u0430\u043c\u0438 \u044f \u043d\u0435 \u0432\u0441\u0442\u0440\u0435\u0447\u0430\u043b. \u0410 \u0440\u0430\u0437 \u0442\u0430\u043a, \u0442\u043e \u0435\u0441\u0442\u044c \u0441\u043c\u044b\u0441\u043b \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0443 \u0431\u043e\u043b\u0435\u0435 \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u043e\u0439, \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e, \u043a\u043e\u043c\u0443-\u0442\u043e \u043f\u0440\u0438\u0433\u043e\u0434\u0438\u0442\u0441\u044f. <\/p>\n<p>  \u041d\u043e \u0434\u0430\u0436\u0435 \u0435\u0441\u043b\u0438 \u044d\u0442\u043e \u0435\u0449\u0451 \u043e\u0434\u0438\u043d \u0432\u0435\u043b\u043e\u0441\u0438\u043f\u0435\u0434, \u0442\u043e \u044f \u043f\u043e\u0441\u0442\u0430\u0440\u0430\u043b\u0441\u044f \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u0435\u0433\u043e \u043f\u043e\u043b\u0435\u0437\u043d\u044b\u043c. Pull request \u0432 common-collections \u0441\u043e\u0437\u0434\u0430\u043d, \u043d\u043e \u043d\u0430 \u043c\u043e\u043c\u0435\u043d\u0442 \u043d\u0430\u043f\u0438\u0441\u0430\u043d\u0438\u044f \u0441\u0442\u0430\u0442\u044c\u0438 \u0435\u0449\u0451 \u043d\u0435 \u0432\u043b\u0438\u0442. \u0417\u043d\u0430\u044f, \u043a\u0430\u043a \u043c\u0435\u0434\u043b\u0435\u043d\u043d\u043e \u0432\u0441\u0451 \u043c\u043e\u0436\u0435\u0442 \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u0442\u044c \u0432 open source, \u043d\u0435 \u0443\u0434\u0438\u0432\u043b\u044e\u0441\u044c, \u0435\u0441\u043b\u0438 \u043f\u0440\u043e\u0446\u0435\u0441\u0441 \u0437\u0430\u0442\u044f\u043d\u0435\u0442\u0441\u044f \u043d\u0430 \u043c\u0435\u0441\u044f\u0446\u044b.<\/p>\n<p>  \u041d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0443\u0434\u0438\u0432\u0438\u043b \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438 ArrayList \u0438 TreeList. \u0422\u0435\u0441\u0442\u044b \u043f\u043e\u043a\u0430\u0437\u0430\u043b\u0438, \u0447\u0442\u043e TreeList \u043d\u0435\u0442 \u0441\u043c\u044b\u0441\u043b\u0430 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u043d\u0430 \u0440\u0430\u0437\u043c\u0435\u0440\u0430\u0445 \u0441\u043f\u0438\u0441\u043a\u0430 \u0434\u043e 10000 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432. \u0411\u044b\u043b\u043e \u0431\u044b \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u043e \u043f\u043e\u043f\u0440\u043e\u0431\u043e\u0432\u0430\u0442\u044c b-tree \u0432\u043c\u0435\u0441\u0442\u043e \u0431\u0438\u043d\u0430\u0440\u043d\u043e\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430. \u042d\u0442\u0430 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u0434\u043e\u043b\u0436\u043d\u0430 \u0431\u043e\u043b\u0435\u0435 \u0431\u0435\u0440\u0435\u0436\u043d\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u043f\u0430\u043c\u044f\u0442\u044c \u0438, \u0441\u043a\u043e\u0440\u0435\u0435 \u0432\u0441\u0435\u0433\u043e, \u0431\u044b\u0441\u0442\u0440\u0435\u0435 \u0440\u0430\u0431\u043e\u0442\u0430\u0442\u044c. \u0418 \u043f\u043e\u0434 \u043d\u0435\u0451 \u043c\u043e\u0436\u043d\u043e \u0430\u0434\u0430\u043f\u0442\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0438\u0434\u0435\u044e \u0441 \u0438\u043d\u0434\u0435\u043a\u0441\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435\u043c.<\/p>\n<p>  \u0412 \u043b\u044e\u0431\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435, \u043f\u0440\u0438\u043a\u043e\u043b\u044c\u043d\u043e \u0438\u043c\u0435\u0442\u044c \u0432 \u0430\u0440\u0441\u0435\u043d\u0430\u043b\u0435 \u0438\u043d\u0441\u0442\u0440\u0443\u043c\u0435\u043d\u0442, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043c\u043e\u0436\u0435\u0442 (\u043f\u043e\u0447\u0442\u0438) \u0432\u0441\u0451 \u0441 \u043f\u0440\u0435\u0434\u0441\u043a\u0430\u0437\u0443\u0435\u043c\u043e\u0439 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c\u044e. <\/p>\n<h2>\u0421\u0441\u044b\u043b\u043a\u0438<\/h2>\n<p>  \u041e\u0440\u0438\u0433\u0438\u043d\u0430\u043b\u044c\u043d\u044b\u0439 \u043f\u0440\u043e\u0435\u043a\u0442: <a href=\"https:\/\/github.com\/masyamandev\/indexable-set\" rel=\"nofollow\">github.com\/masyamandev\/indexable-set<\/a><br \/>  Pull request \u0432 apache common-collections: <a href=\"https:\/\/github.com\/apache\/commons-collections\/pull\/129\" rel=\"nofollow\">github.com\/apache\/commons-collections\/pull\/129<\/a><br \/>  \u0422\u0438\u043a\u0435\u0442 \u0432 Jira: <a href=\"https:\/\/issues.apache.org\/jira\/browse\/COLLECTIONS-672\" rel=\"nofollow\">issues.apache.org\/jira\/browse\/COLLECTIONS-672<\/a><\/div>\n<p> \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0441\u0442\u0430\u0442\u044c\u0438 <a href=\"https:\/\/habr.com\/ru\/post\/488778\/\"> https:\/\/habr.com\/ru\/post\/488778\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"\n<div class=\"post__text post__text-html\" id=\"post-content-body\" data-io-article-url=\"https:\/\/habr.com\/ru\/post\/488778\/\"><i>* \u041f\u043e\u0434 \u0432\u0441\u0451 \u0438\u043c\u0435\u0435\u0442\u0441\u044f \u0432 \u0432\u0438\u0434\u0443 \u043e\u0442\u043d\u043e\u0441\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0431\u044b\u0441\u0442\u0440\u043e\u0435 \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u0435 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u043d\u0430\u0434 \u0435\u0434\u0438\u043d\u0438\u0447\u043d\u044b\u043c \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u043c \u043c\u0430\u0441\u0441\u0438\u0432\u0430.<\/i><\/p>\n<p>  \u0421\u0442\u0440\u0443\u043a\u0442\u0443\u0440 \u0434\u0430\u043d\u043d\u044b\u0445, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0440\u0435\u0430\u043b\u0438\u0437\u0443\u044e\u0442 \u0441\u043f\u0438\u0441\u043e\u043a \u043f\u043e\u043b\u043d\u043e. \u0423 \u0432\u0441\u0435\u0445 \u0435\u0441\u0442\u044c \u0441\u0432\u043e\u0438 \u0434\u043e\u0441\u0442\u043e\u0438\u043d\u0441\u0442\u0432\u0430 \u0438 \u043d\u0435\u0434\u043e\u0441\u0442\u0430\u0442\u043a\u0438. \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440 \u0432 \u043c\u0438\u0440\u0435 Java \u2014 \u0432 \u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u0438 \u043e\u0442 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u044b\u0445 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u2014 \u043c\u043e\u0436\u043d\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c:  <\/p>\n<ul>\n<li>add(obj), get(obj), set(index, obj): \u0431\u0430\u0437\u043e\u0432\u044b\u0439 \u043d\u0430\u0431\u043e\u0440 \u043f\u043e\u0447\u0442\u0438 \u0432\u0441\u0435\u0445 \u0441\u043f\u0438\u0441\u043a\u043e\u0432, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440 ArrayList. <\/li>\n<li>add(index, obj): \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0432 \u0432\u0438\u0434\u0435 \u0434\u0435\u0440\u0435\u0432\u0430, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440 TreeList \u0438\u0437 apache common-collections. <\/li>\n<li>remove(index): \u0442\u043e \u0436\u0435, \u0447\u0442\u043e \u0438 \u0432\u044b\u0448\u0435. <\/li>\n<li>contains(obj), indexOf(obj): \u043c\u043e\u0436\u043d\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0441\u0432\u044f\u0437\u043a\u0443 ArrayList \u0438 HashMap. <\/li>\n<li>remove(obj): \u2026 \u0437\u0430\u0442\u0440\u0443\u0434\u043d\u044f\u044e\u0441\u044c \u043e\u0442\u0432\u0435\u0442\u0438\u0442\u044c. \u0412 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0441\u043b\u0443\u0447\u0430\u044f\u0445 \u043c\u043e\u0436\u043d\u043e \u043e\u0431\u043e\u0439\u0442\u0438\u0441\u044c LinkedHashSet. \u0420\u0435\u0448\u0430\u0435\u0442\u0441\u044f \u0442\u0440\u0438\u0432\u0438\u0430\u043b\u044c\u043d\u043e \u043f\u0440\u0438 \u043d\u0430\u043b\u0438\u0447\u0438\u0438 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0438\u0445 \u0434\u0432\u0443\u0445 \u043f\u0443\u043d\u043a\u0442\u043e\u0432, \u043d\u043e \u043a\u0430\u043a\u0438\u0435 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u043c\u043e\u0433\u0443\u0442 \u0438 \u0442\u043e \u0438 \u0434\u0440\u0443\u0433\u043e\u0435 \u0431\u044b\u0441\u0442\u0440\u043e? <\/li>\n<\/ul>\n<p>  \u041a\u043e\u0433\u0434\u0430 \u043c\u043d\u0435 \u043f\u043e\u043d\u0430\u0434\u043e\u0431\u0438\u043b\u0430\u0441\u044c \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u0441 \u0431\u044b\u0441\u0442\u0440\u044b\u043c\u0438 add(obj), get(index), remove(index) \u0438 indexOf(obj), \u0442\u043e google \u043d\u0435 \u0434\u0430\u043b \u043e\u0442\u0432\u0435\u0442\u0430. \u041d\u0438 \u043f\u0440\u0438\u043c\u0435\u0440\u043e\u0432 \u043a\u043e\u0434\u0430, \u043d\u0438 \u043e\u043f\u0438\u0441\u0430\u043d\u0438\u044f \u043f\u043e\u0434\u043e\u0431\u043d\u044b\u0445 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440 \u044f \u043d\u0435 \u043d\u0430\u0448\u0435\u043b. \u0412\u043e\u0437\u043c\u043e\u0436\u043d\u043e \u043d\u0435 \u0442\u0430\u043c \u0438\u0441\u043a\u0430\u043b, \u043f\u0440\u0438\u0448\u043b\u043e\u0441\u044c \u0432\u044b\u0434\u0443\u043c\u044b\u0432\u0430\u0442\u044c \u0441\u0430\u043c\u043e\u043c\u0443. \u041d\u043e \u0435\u0441\u043b\u0438 \u043a\u0442\u043e-\u0442\u043e \u0441\u043a\u0438\u043d\u0435\u0442 \u0441\u0441\u044b\u043b\u043a\u0443 \u0432 \u043a\u043e\u043c\u043c\u0435\u043d\u0442\u0430\u0440\u0438\u044f\u0445, \u0442\u043e \u0431\u0443\u0434\u0443 \u0432\u0435\u0441\u044c\u043c\u0430 \u043f\u0440\u0438\u0437\u043d\u0430\u0442\u0435\u043b\u0435\u043d.<\/p>\n<p>  \u0412\u043e\u0437\u043c\u043e\u0436\u043d\u043e, \u043a\u0442\u043e-\u0442\u043e \u0434\u043e\u0433\u0430\u0434\u0430\u043b\u0441\u044f, \u0447\u0442\u043e \u043c\u043e\u0436\u043d\u043e \u0432\u0437\u044f\u0442\u044c TreeList, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0443\u043c\u0435\u0435\u0442 \u0431\u044b\u0441\u0442\u0440\u043e \u0432\u0441\u0442\u0430\u0432\u043b\u044f\u0442\u044c\/\u0443\u0434\u0430\u043b\u044f\u0442\u044c \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0432 \u0441\u0435\u0440\u0435\u0434\u0438\u043d\u0435 \u0441\u043f\u0438\u0441\u043a\u0430 \u0438 \u0434\u043e\u0431\u0430\u0432\u0438\u0442\u044c \u043a \u043d\u0435\u043c\u0443 HashMap \u0438\u0437 \u043e\u0431\u044a\u0435\u043a\u0442\u0430 \u0432 \u0438\u043d\u0434\u0435\u043a\u0441 \u0432 TreeList \u0434\u043b\u044f \u0431\u044b\u0441\u0442\u0440\u043e\u0433\u043e \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u044f indexOf(obj). \u0418 \u044d\u0442\u043e \u0431\u0443\u0434\u0435\u0442 \u043f\u0440\u043e\u0441\u0442\u043e\u0435, \u0438\u0437\u044f\u0449\u043d\u043e\u0435, \u043d\u043e \u043d\u0435\u0432\u0435\u0440\u043d\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435. \u0412\u0435\u0434\u044c \u043f\u0440\u0438 \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u0438 \u0432 \u0441\u0435\u0440\u0435\u0434\u0438\u043d\u0443 \u0438\u043b\u0438 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u0438 \u0438\u0437 \u0441\u0435\u0440\u0435\u0434\u0438\u043d\u044b \u043d\u0443\u0436\u043d\u043e \u0431\u0443\u0434\u0435\u0442 \u043f\u0435\u0440\u0435\u0441\u0447\u0438\u0442\u0430\u0442\u044c \u0438\u043d\u0434\u0435\u043a\u0441\u044b, \u0432 \u0441\u0440\u0435\u0434\u043d\u0435\u043c, \u0434\u043b\u044f \u043f\u043e\u043b\u043e\u0432\u0438\u043d\u044b \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432. \u042d\u0442\u043e \u0443\u0445\u0443\u0434\u0448\u0438\u0442 \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u0434\u043e O(n).<\/p>\n<p>  \u0414\u0430\u043b\u044c\u0448\u0435 \u044f \u0440\u0430\u0441\u0441\u043a\u0430\u0436\u0443 \u043e \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0435 \u0434\u0430\u043d\u043d\u044b\u0445, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043c\u043e\u0436\u0435\u0442 \u0432\u0441\u0451 \u0438\u0437 \u043f\u0435\u0440\u0435\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u043e\u0433\u043e \u0432\u044b\u0448\u0435. \u041a\u043e\u0442\u043e\u0440\u0430\u044f \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442 \u043b\u044e\u0431\u0443\u044e \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044e \u043d\u0430\u0434 \u043e\u0434\u043d\u0438\u043c \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u043c \u0437\u0430 O(log(n)) \u0432\u0440\u0435\u043c\u0435\u043d\u0438. \u041d\u0443 \u043f\u043e\u0447\u0442\u0438 \u2014 \u0437\u0430 \u043b\u043e\u0433\u0430\u0440\u0438\u0444\u043c \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442\u0441\u044f \u0432 \u0442\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435, \u043a\u043e\u0433\u0434\u0430 \u0432\u0441\u0435 \u043e\u0431\u044a\u0435\u043a\u0442\u044b \u0432 \u0441\u043f\u0438\u0441\u043a\u0435 \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b. \u0415\u0441\u043b\u0438 \u0432 \u0441\u043f\u0438\u0441\u043a\u0435 \u0435\u0441\u0442\u044c \u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u044b\u0435 \u043e\u0431\u044a\u0435\u043a\u0442\u044b, \u0442\u043e \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e \u043f\u0440\u043e\u0441\u0435\u0434\u0430\u043d\u0438\u0435 \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u0432\u043f\u043b\u043e\u0442\u044c \u0434\u043e O(log(n) ^ 2).  <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"class_list":["post-298823","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/298823","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=298823"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/298823\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=298823"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=298823"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=298823"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}