{"id":292887,"date":"2019-08-01T21:00:06","date_gmt":"2019-08-01T21:00:06","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=292887"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=292887","title":{"rendered":"\u0421\u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0435 \u0434\u0432\u043e\u0438\u0447\u043d\u044b\u0435 \u0434\u0435\u0440\u0435\u0432\u044c\u044f \u043f\u043e\u0438\u0441\u043a\u0430: \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u043d\u0430 Julia"},"content":{"rendered":"\n<div class=\"post__text post__text-html js-mediator-article\">\n<p><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/5q\/ek\/4n\/5qek4nssuu4dsjepoaa2g9tgmw0.png\"><br \/>  <em>\u0418\u043b\u043b\u044e\u0441\u0442\u0440\u0430\u0446\u0438\u044f \u0438\u0437 \u0440\u0430\u0431\u043e\u0442\u044b \u0413.\u041c. \u0410\u0434\u0435\u043b\u044c\u0441\u043e\u043d-\u0412\u0435\u043b\u044c\u0441\u043a\u043e\u0433\u043e \u0438 \u0415.\u041c. \u041b\u0430\u043d\u0434\u0438\u0441\u0430 1962 \u0433\u043e\u0434\u0430<\/em><\/p>\n<p>  <\/p>\n<p>\u0414\u0435\u0440\u0435\u0432\u044c\u044f \u043f\u043e\u0438\u0441\u043a\u0430 \u2014 \u044d\u0442\u043e \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0434\u0430\u043d\u043d\u044b\u0445 \u0434\u043b\u044f \u0443\u043f\u043e\u0440\u044f\u0434\u043e\u0447\u0435\u043d\u043d\u043e\u0433\u043e \u0445\u0440\u0430\u043d\u0435\u043d\u0438\u044f \u0438 \u043f\u0440\u043e\u0441\u0442\u043e\u0433\u043e \u043f\u043e\u0438\u0441\u043a\u0430 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432. \u0428\u0438\u0440\u043e\u043a\u043e \u043f\u0440\u0438\u043c\u0435\u043d\u044f\u044e\u0442\u0441\u044f <em>\u0434\u0432\u043e\u0438\u0447\u043d\u044b\u0435<\/em> \u0434\u0435\u0440\u0435\u0432\u044c\u044f \u043f\u043e\u0438\u0441\u043a\u0430, \u0432 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0443 \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0443\u0437\u043b\u0430 \u0435\u0441\u0442\u044c \u0442\u043e\u043b\u044c\u043a\u043e \u0434\u0432\u0430 \u043f\u043e\u0442\u043e\u043c\u043a\u0430. \u0412 \u044d\u0442\u043e\u0439 \u0441\u0442\u0430\u0442\u044c\u0435 \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u0434\u0432\u0430 \u043c\u0435\u0442\u043e\u0434\u0430 \u043e\u0440\u0433\u0430\u043d\u0438\u0437\u0430\u0446\u0438\u0438 \u0434\u0432\u043e\u0438\u0447\u043d\u044b\u0445 \u0434\u0435\u0440\u0435\u0432\u044c\u0435\u0432 \u043f\u043e\u0438\u0441\u043a\u0430: \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0410\u0434\u0435\u043b\u044c\u0441\u043e\u043d-\u0412\u0435\u043b\u044c\u0441\u043a\u043e\u0433\u043e \u0438 \u041b\u0430\u043d\u0434\u0438\u0441\u0430 (\u0410\u0412\u041b-\u0434\u0435\u0440\u0435\u0432\u044c\u044f) \u0438 \u043e\u0441\u043b\u0430\u0431\u043b\u0435\u043d\u043d\u044b\u0435 \u0410\u0412\u041b-\u0434\u0435\u0440\u0435\u0432\u044c\u044f (WAVL-\u0434\u0435\u0440\u0435\u0432\u044c\u044f).<\/p>\n<p><a name=\"habracut\"><\/a>  <\/p>\n<p>\u041d\u0430\u0447\u043d\u0451\u043c \u0441 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0439. <a href=\"https:\/\/habr.com\/ru\/post\/65617\/\">\u0414\u0432\u043e\u0438\u0447\u043d\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e<\/a> \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0438\u0437 <em>\u0443\u0437\u043b\u043e\u0432<\/em>, \u043a\u0430\u0436\u0434\u044b\u0439 \u0443\u0437\u0435\u043b \u0445\u0440\u0430\u043d\u0438\u0442 <em>\u0437\u0430\u043f\u0438\u0441\u044c<\/em> \u0432 \u0432\u0438\u0434\u0435 \u043f\u0430\u0440 <em>\u043a\u043b\u044e\u0447-\u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435<\/em> (\u043b\u0438\u0431\u043e, \u0432 \u043f\u0440\u043e\u0441\u0442\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435, \u0442\u043e\u043b\u044c\u043a\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439) \u0438 \u0438\u043c\u0435\u0435\u0442 \u043d\u0435 \u0431\u043e\u043b\u0435\u0435 \u0434\u0432\u0443\u0445 <em>\u043f\u043e\u0442\u043e\u043c\u043a\u043e\u0432<\/em>. \u0423\u0437\u043b\u044b-\u043f\u043e\u0442\u043e\u043c\u043a\u0438 \u0440\u0430\u0437\u043b\u0438\u0447\u0430\u044e\u0442\u0441\u044f \u043d\u0430 <em>\u043f\u0440\u0430\u0432\u044b\u0439<\/em> \u0438 <em>\u043b\u0435\u0432\u044b\u0439<\/em>, \u043f\u0440\u0438\u0447\u0451\u043c \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442\u0441\u044f \u0443\u0441\u043b\u043e\u0432\u0438\u0435 \u043d\u0430 \u0443\u043f\u043e\u0440\u044f\u0434\u043e\u0447\u0435\u043d\u043d\u043e\u0441\u0442\u044c \u043a\u043b\u044e\u0447\u0435\u0439: \u043a\u043b\u044e\u0447 \u043b\u0435\u0432\u043e\u0433\u043e \u043f\u043e\u0442\u043e\u043c\u043a\u0430 \u043d\u0435 \u0431\u043e\u043b\u044c\u0448\u0435, \u0430 \u043f\u0440\u0430\u0432\u043e\u0433\u043e \u2014 \u043d\u0435 \u043c\u0435\u043d\u044c\u0448\u0435, \u0447\u0435\u043c \u043a\u043b\u044e\u0447 \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u0441\u043a\u043e\u0433\u043e \u0443\u0437\u043b\u0430. \u0414\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0432 \u0443\u0437\u043b\u0430\u0445 \u043c\u043e\u0436\u0435\u0442 \u0445\u0440\u0430\u043d\u0438\u0442\u044c\u0441\u044f (\u0438 \u043e\u0431\u044b\u0447\u043d\u043e \u0445\u0440\u0430\u043d\u0438\u0442\u0441\u044f) \u0441\u043b\u0443\u0436\u0435\u0431\u043d\u0430\u044f \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u044f \u2014 \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u0441\u043a\u0438\u0439 \u0443\u0437\u0435\u043b \u0438\u043b\u0438 \u0434\u0440\u0443\u0433\u0438\u0435 \u0434\u0430\u043d\u043d\u044b\u0435. \u0421\u043f\u0435\u0446\u0438\u0430\u043b\u044c\u043d\u044b\u043c\u0438 \u0441\u043b\u0443\u0447\u0430\u044f\u043c\u0438 \u044f\u0432\u043b\u044f\u044e\u0442\u0441\u044f <em>\u043a\u043e\u0440\u043d\u0435\u0432\u043e\u0439 \u0443\u0437\u0435\u043b<\/em>, \u0441 \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u0442 \u0432\u0445\u043e\u0434 \u0432 \u0434\u0435\u0440\u0435\u0432\u043e, \u0438 <em>\u043f\u0443\u0441\u0442\u043e\u0439 \u0443\u0437\u0435\u043b<\/em>, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043d\u0435 \u0445\u0440\u0430\u043d\u0438\u0442 \u043d\u0438\u043a\u0430\u043a\u043e\u0439 \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u0438. \u0423\u0437\u043b\u044b, \u0443 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u043e\u0431\u0430 \u043f\u043e\u0442\u043e\u043c\u043a\u0430 \u043f\u0443\u0441\u0442\u044b\u0435, \u043d\u0430\u0437\u044b\u0432\u0430\u044e\u0442\u0441\u044f <em>\u043b\u0438\u0441\u0442\u044c\u044f\u043c\u0438<\/em> \u0434\u0435\u0440\u0435\u0432\u0430. \u0423\u0437\u0435\u043b \u0441\u043e \u0432\u0441\u0435\u043c\u0438 \u043f\u043e\u0442\u043e\u043c\u043a\u0430\u043c\u0438 \u043e\u0431\u0440\u0430\u0437\u0443\u0435\u0442 <em>\u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u043e<\/em>. \u0422\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, \u043a\u0430\u0436\u0434\u044b\u0439 \u0443\u0437\u0435\u043b \u043b\u0438\u0431\u043e \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043a\u043e\u0440\u043d\u0435\u043c \u043a\u0430\u043a\u043e\u0433\u043e-\u0442\u043e \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u0430, \u043b\u0438\u0431\u043e \u043b\u0438\u0441\u0442\u043e\u043c.<br \/>  \u042d\u0442\u043e \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0435 \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u043f\u043e\u0441\u0442\u0440\u043e\u0438\u0442\u044c \u043f\u0440\u043e\u0441\u0442\u0435\u0439\u0448\u0443\u044e \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0443 \u0434\u043b\u044f \u0445\u0440\u0430\u043d\u0435\u043d\u0438\u044f \u0443\u0437\u043b\u043e\u0432 \u0438 \u0441\u0430\u043c\u043e\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430. \u0411\u0443\u0434\u0435\u043c \u0441\u0447\u0438\u0442\u0430\u0442\u044c, \u0447\u0442\u043e \u043f\u0443\u0441\u0442\u043e\u0439 \u0443\u0437\u0435\u043b \u0438\u043c\u0435\u0435\u0442 \u0441\u043f\u0435\u0446\u0438\u0430\u043b\u044c\u043d\u043e\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 <code>nothing<\/code> \u0442\u0438\u043f\u0430 <code>Nothing<\/code>. \u0422\u043e\u0433\u0434\u0430 \u0432 \u0443\u0437\u043b\u0435 \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u0441\u0441\u044b\u043b\u043a\u0438 \u043d\u0430 \u043f\u0440\u0430\u0432\u043e\u0433\u043e \u0438 \u043b\u0435\u0432\u043e\u0433\u043e \u043f\u043e\u0442\u043e\u043c\u043a\u0430 \u0438 \u043d\u0430 \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044f. \u0421\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u0434\u043b\u044f \u0445\u0440\u0430\u043d\u0435\u043d\u0438\u044f \u0434\u0435\u0440\u0435\u0432\u0430 \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u0442\u043e\u043b\u044c\u043a\u043e \u0441\u0441\u044b\u043b\u043a\u0443 \u043d\u0430 \u043a\u043e\u0440\u043d\u0435\u0432\u043e\u0439 \u0443\u0437\u0435\u043b.<\/p>\n<p>  <\/p>\n<pre><code class=\"julia\"># K - \u0442\u0438\u043f \u043a\u043b\u044e\u0447\u0435\u0439 # V - \u0442\u0438\u043f \u0445\u0440\u0430\u043d\u0438\u043c\u044b\u0445 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439 mutable struct BSTNode{K, V}     key::K     value::V     left::Union{Nothing, BSTNode{K,V}}     right::Union{Nothing, BSTNode{K,V}}     parent::BSTNode{K,V} end  mutable struct BST{K, V}     root::BSTNode{K,V} end<\/code><\/pre>\n<p>  <\/p>\n<p>\u0412 \u044d\u0442\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u0432\u043e\u0437\u043d\u0438\u043a\u0430\u0435\u0442 \u0432\u043e\u043f\u0440\u043e\u0441, \u043a\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u043f\u0443\u0441\u0442\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e. \u0412\u043e\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c\u0441\u044f \u0434\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u043f\u043e\u0434\u0445\u043e\u0434\u043e\u043c \u0438\u0437 \u043a\u043d\u0438\u0433\u0438 &#171;\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b: \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u0435 \u0438 \u0430\u043d\u0430\u043b\u0438\u0437&#187; \u0438 \u0432\u0441\u0442\u0430\u0432\u0438\u043c \u0432 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u0442\u043e\u0447\u043a\u0438 \u0432\u0445\u043e\u0434\u0430 \u0432 \u0434\u0435\u0440\u0435\u0432\u043e \u043d\u0435 \u043a\u043e\u0440\u0435\u043d\u044c, \u0430 \u0444\u0438\u043a\u0442\u0438\u0432\u043d\u044b\u0439 \u0443\u0437\u0435\u043b, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0431\u0443\u0434\u0435\u0442 \u0441\u0432\u043e\u0438\u043c \u0441\u043e\u0431\u0441\u0442\u0432\u0435\u043d\u043d\u044b\u043c \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u0435\u043c. \u0414\u043b\u044f \u0441\u043e\u0437\u0434\u0430\u043d\u0438\u044f \u0442\u0430\u043a\u043e\u0433\u043e \u0443\u0437\u043b\u0430 \u043d\u0443\u0436\u043d\u043e \u0434\u043e\u0431\u0430\u0432\u0438\u0442\u044c \u0432 \u043e\u043f\u0438\u0441\u0430\u043d\u0438\u0435 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b BSTNode \u043a\u043e\u043d\u0441\u0442\u0440\u0443\u043a\u0442\u043e\u0440\u044b:<\/p>\n<p>  <\/p>\n<pre><code class=\"julia\">mutable struct BSTNode{K, V}     key::K     value::V     left::Union{Nothing, BSTNode{K,V}}     right::Union{Nothing, BSTNode{K,V}}     parent::BSTNode{K,V}     # \u043f\u0443\u0441\u0442\u043e\u0439 \u043a\u043e\u043d\u0441\u0442\u0440\u0443\u043a\u0442\u043e\u0440     function BSTNode{K,V}() where {K,V}         node = new{K,V}()         node.parent = node         node.left = node.right = nothing         return node     end     # \u043a\u043e\u043d\u0441\u0442\u0440\u0443\u043a\u0442\u043e\u0440 \u0441 \u043f\u0430\u0440\u043e\u0439 \u043a\u043b\u044e\u0447-\u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435     function BSTNode{K,V}(key, value) where {K, V}         node = new{K,V}()         node.parent = node         node.left = node.right = nothing         node.key, node.value = key, value         return node     end end  BSTNode() = BSTNode{Any, Any}()  # \u0422\u0435\u043f\u0435\u0440\u044c \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0443 \u043c\u043e\u0436\u043d\u043e \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u043d\u0435\u0438\u0437\u043c\u0435\u043d\u044f\u0435\u043c\u043e\u0439! struct BST{K, V}     entry::BSTNode{K,V}     BST{K,V}() where {K,V} = new{K,V}(BSTNode{K,V}()) end  BST() = BST{Any, Any}()  Base.isempty(bst::BST) = bst.entry.left == nothing<\/code><\/pre>\n<p>  <\/p>\n<p>\u0412 \u044d\u0442\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0443 <code>BST<\/code> \u043c\u043e\u0436\u043d\u043e \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u043d\u0435\u0438\u0437\u043c\u0435\u043d\u044f\u0435\u043c\u043e\u0439, \u0442.\u043a. \u0441\u0441\u044b\u043b\u043a\u0443 \u043d\u0430 \u0442\u043e\u0447\u043a\u0443 \u0432\u0445\u043e\u0434\u0430 \u043c\u0435\u043d\u044f\u0442\u044c \u0443\u0436\u0435 \u043d\u0435 \u043f\u043e\u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f. \u0414\u0430\u043b\u0435\u0435 \u0431\u0443\u0434\u0435\u043c \u0441\u0447\u0438\u0442\u0430\u0442\u044c, \u0447\u0442\u043e \u043a\u043e\u0440\u043d\u0435\u0432\u043e\u0439 \u0443\u0437\u0435\u043b \u0434\u0435\u0440\u0435\u0432\u0430 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0441\u0440\u0430\u0437\u0443 \u0438 \u043f\u0440\u0430\u0432\u044b\u043c, \u0438 \u043b\u0435\u0432\u044b\u043c \u043f\u043e\u0442\u043e\u043c\u043a\u043e\u043c \u0432\u0445\u043e\u0434\u043d\u043e\u0433\u043e \u0443\u0437\u043b\u0430.<br \/>  \u0413\u043b\u0430\u0432\u043d\u0430\u044f \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044f, \u0434\u043b\u044f \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u043d\u0443\u0436\u043d\u044b \u0434\u0435\u0440\u0435\u0432\u044c\u044f \u043f\u043e\u0438\u0441\u043a\u0430 \u2014 \u044d\u0442\u043e, \u0435\u0441\u0442\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u043e, \u043f\u043e\u0438\u0441\u043a \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432. \u041f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 \u043a\u043b\u044e\u0447 \u043b\u0435\u0432\u043e\u0433\u043e \u043f\u043e\u0442\u043e\u043c\u043a\u0430 \u043d\u0435 \u0431\u043e\u043b\u044c\u0448\u0435, \u0430 \u043f\u0440\u0430\u0432\u043e\u0433\u043e \u2014 \u043d\u0435 \u043c\u0435\u043d\u044c\u0448\u0435 \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u0441\u043a\u043e\u0433\u043e \u043a\u043b\u044e\u0447\u0430, \u043f\u0440\u043e\u0446\u0435\u0434\u0443\u0440\u0430 \u043f\u043e\u0438\u0441\u043a\u0430 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u043f\u0438\u0448\u0435\u0442\u0441\u044f \u043e\u0447\u0435\u043d\u044c \u043f\u0440\u043e\u0441\u0442\u043e: \u043d\u0430\u0447\u0438\u043d\u0430\u044f \u0441 \u043a\u043e\u0440\u043d\u044f \u0434\u0435\u0440\u0435\u0432\u0430, \u0441\u0440\u0430\u0432\u043d\u0438\u0432\u0430\u0435\u043c \u0432\u0445\u043e\u0434\u043d\u043e\u0439 \u043a\u043b\u044e\u0447 \u0441 \u043a\u043b\u044e\u0447\u043e\u043c \u0442\u0435\u043a\u0443\u0449\u0435\u0433\u043e \u0443\u0437\u043b\u0430; \u0435\u0441\u043b\u0438 \u043a\u043b\u044e\u0447\u0438 \u0441\u043e\u0432\u043f\u0430\u043b\u0438 \u2014 \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u043c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435, \u0432 \u043f\u0440\u043e\u0442\u0438\u0432\u043d\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u0438\u043c \u043a \u043b\u0435\u0432\u043e\u043c\u0443 \u0438\u043b\u0438 \u043f\u0440\u0430\u0432\u043e\u043c\u0443 \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u0443, \u0432 \u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u0438 \u043e\u0442 \u043f\u043e\u0440\u044f\u0434\u043a\u0430 \u043a\u043b\u044e\u0447\u0435\u0439. \u0415\u0441\u043b\u0438 \u043f\u0440\u0438 \u044d\u0442\u043e\u043c \u0434\u043e\u0448\u043b\u0438 \u0434\u043e \u043f\u0443\u0441\u0442\u043e\u0433\u043e \u0443\u0437\u043b\u0430 \u2014 \u043a\u043b\u044e\u0447\u0430 \u0432 \u0434\u0435\u0440\u0435\u0432\u0435 \u043d\u0435\u0442, \u0431\u0440\u043e\u0441\u0430\u0435\u043c \u0438\u0441\u043a\u043b\u044e\u0447\u0435\u043d\u0438\u0435.<\/p>\n<p>  <\/p>\n<pre><code class=\"julia\"># \u041f\u0435\u0440\u0435\u0433\u0440\u0443\u0437\u043a\u0430 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 Base.getindex() \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u0432 \u0434\u0430\u043b\u044c\u043d\u0435\u0439\u0448\u0435\u043c  # \u043e\u0431\u0440\u0430\u0449\u0430\u0442\u044c\u0441\u044f \u043a \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0443 \u0447\u0435\u0440\u0435\u0437 \u0441\u0438\u043d\u0442\u0430\u043a\u0441\u0438\u0441 tree[key] function Base.getindex(bst::BST{K,V}, key) where {K,V}     key = convert(K, key)     node = bst.entry.left     while node != nothing         key == node.key &amp;&amp; return node.value         node = (key &lt; node.key ? node.left : node.right)     end     throw(KeyError(key)) end<\/code><\/pre>\n<p>  <\/p>\n<p>\u041f\u043e\u0438\u0441\u043a \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u043f\u043e \u043a\u043b\u044e\u0447\u0443, \u043e\u0447\u0435\u0432\u0438\u0434\u043d\u043e, \u0437\u0430\u043d\u0438\u043c\u0430\u0435\u0442 \u0432\u0440\u0435\u043c\u044f <em>O<\/em>(<em>h<\/em>), \u0433\u0434\u0435 <em>h<\/em> \u2014 \u0432\u044b\u0441\u043e\u0442\u0430 \u0434\u0435\u0440\u0435\u0432\u0430, \u0442.\u0435. \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u043e\u0442 \u043a\u043e\u0440\u043d\u044f \u0434\u043e \u043b\u0438\u0441\u0442\u0430. \u041a\u0430\u043a \u043b\u0435\u0433\u043a\u043e \u043f\u043e\u0441\u0447\u0438\u0442\u0430\u0442\u044c, \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e \u0432\u044b\u0441\u043e\u0442\u044b <em>h<\/em> \u043c\u043e\u0436\u0435\u0442 \u043a\u0430\u043a \u043c\u0430\u043a\u0441\u0438\u043c\u0443\u043c \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0442\u044c 2<sup>h+1<\/sup>-1 \u0443\u0437\u043b\u043e\u0432, \u0435\u0441\u043b\u0438 \u043e\u043d\u043e <em>\u043f\u043b\u043e\u0442\u043d\u043e \u0437\u0430\u043f\u043e\u043b\u043d\u0435\u043d\u043e<\/em>, \u0442.\u0435. \u0432\u0441\u0435 \u0443\u0437\u043b\u044b, \u043a\u0440\u043e\u043c\u0435, \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c, \u0441\u0430\u043c\u043e\u0433\u043e \u043a\u0440\u0430\u0439\u043d\u0435\u0433\u043e \u0441\u043b\u043e\u044f, \u0438\u043c\u0435\u044e\u0442 \u043e\u0431\u043e\u0438\u0445 \u043f\u043e\u0442\u043e\u043c\u043a\u043e\u0432. \u041a \u0442\u043e\u043c\u0443 \u0436\u0435 \u043f\u043e\u043d\u044f\u0442\u043d\u043e, \u0447\u0442\u043e \u043b\u044e\u0431\u0443\u044e \u043d\u0430\u043f\u0435\u0440\u0451\u0434 \u0437\u0430\u0434\u0430\u043d\u043d\u0443\u044e \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u043a\u043b\u044e\u0447\u0435\u0439 \u043c\u043e\u0436\u043d\u043e \u043f\u0440\u0438\u0432\u0435\u0441\u0442\u0438 \u043a \u0442\u0430\u043a\u043e\u043c\u0443 \u043f\u043b\u043e\u0442\u043d\u043e\u043c\u0443 \u0434\u0435\u0440\u0435\u0432\u0443. \u042d\u0442\u043e \u0434\u0430\u0451\u0442 \u0432\u0435\u0441\u044c\u043c\u0430 \u043e\u043f\u0442\u0438\u043c\u0438\u0441\u0442\u0438\u0447\u043d\u0443\u044e \u0430\u0441\u0438\u043c\u043f\u0442\u043e\u0442\u0438\u043a\u0443 \u043f\u043e\u0438\u0441\u043a\u0430 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u0432 \u0434\u0435\u0440\u0435\u0432\u0435 \u043f\u0440\u0438 \u0435\u0433\u043e \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u043c \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u0438 \u0437\u0430 \u0432\u0440\u0435\u043c\u044f <em>O<\/em>(log<sub>2<\/sub><em>N<\/em>), \u0433\u0434\u0435 <em>N<\/em> \u2014 \u0447\u0438\u0441\u043b\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432.<br \/>  \u0415\u0441\u0442\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u043e, \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u0432 \u0434\u0435\u0440\u0435\u0432\u043e \u043f\u043e\u0438\u0441\u043a\u0430 \u043d\u0443\u0436\u043d\u043e \u0441\u0442\u0440\u043e\u0438\u0442\u044c \u0442\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, \u0447\u0442\u043e\u0431\u044b \u0443\u0441\u043b\u043e\u0432\u0438\u0435 \u043d\u0430 \u043f\u043e\u0440\u044f\u0434\u043e\u043a \u043a\u043b\u044e\u0447\u0435\u0439 \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u043b\u0441\u044f. \u041d\u0430\u043f\u0438\u0448\u0435\u043c \u043d\u0430\u0438\u0432\u043d\u0443\u044e \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044e \u0432\u0441\u0442\u0430\u0432\u043a\u0438 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u043f\u043e \u043a\u043b\u044e\u0447\u0443:<\/p>\n<p>  <\/p>\n<pre><code class=\"julia\"># \u041f\u0435\u0440\u0435\u0433\u0440\u0443\u0437\u043a\u0430 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 Base.setindex!() \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u0432 \u0434\u0430\u043b\u044c\u043d\u0435\u0439\u0448\u0435\u043c  # \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0442\u044c \u0438\u043b\u0438 \u043c\u0435\u043d\u044f\u0442\u044c \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0447\u0435\u0440\u0435\u0437 \u0441\u0438\u043d\u0442\u0430\u043a\u0441\u0438\u0441 tree[key] = value function Base.setindex!(bst::BST{K,V}, val::SV, key::SK) where {K, V}     key, value = convert(K, key), convert(V, val)     parent = bst.entry.left     # \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u044b\u0439 \u0441\u043b\u0443\u0447\u0430\u0439 - \u0432\u0441\u0442\u0430\u0432\u043a\u0430 \u0432 \u043f\u0443\u0441\u0442\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e     if parent == nothing         newnode.parent = bst.entry         bst.entry.left = bst.entry.right = newnode         return val     end      key_found = false     while !key_found         if key &lt; parent.key             if parent.left == nothing                 parent.left = BSTNode{K,V}(key, value)                 parent.left.parent = parent                 key_found = true             else                 parent = parent.left             end         elseif key &gt; parent.key             if parent.right == nothing                 parent.right = BSTNode{K,V}(key, value)                 newnode.parent = parent                 key_found = true             else                 parent = parent.right             end         else             key_found = true             parent.value = value         end     end     return val end<\/code><\/pre>\n<p>  <\/p>\n<p>\u041a \u0441\u043e\u0436\u0430\u043b\u0435\u043d\u0438\u044e, \u043d\u0430\u0438\u0432\u043d\u043e\u0435 \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u0435 \u0434\u0435\u0440\u0435\u0432\u0430 \u0434\u0430\u0441\u0442 \u043d\u0443\u0436\u043d\u0443\u044e \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0443 \u0442\u043e\u043b\u044c\u043a\u043e \u043d\u0430 \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u044b\u0445 \u0432\u0445\u043e\u0434\u043d\u044b\u0445 \u0434\u0430\u043d\u043d\u044b\u0445, \u0430 \u0432 \u0440\u0435\u0430\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u043e\u043d\u0438 \u0447\u0430\u0441\u0442\u043e \u0434\u043e\u0432\u043e\u043b\u044c\u043d\u043e \u0441\u0438\u043b\u044c\u043d\u043e \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0438\u0440\u043e\u0432\u0430\u043d\u044b. \u0412 \u043d\u0430\u0438\u0445\u0443\u0434\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435, \u0435\u0441\u043b\u0438 \u043f\u043e\u0441\u0442\u0443\u043f\u0430\u044e\u0449\u0438\u0435 \u043a\u043b\u044e\u0447\u0438 \u0441\u0442\u0440\u043e\u0433\u043e \u0443\u043f\u043e\u0440\u044f\u0434\u043e\u0447\u0435\u043d\u044b (\u0445\u043e\u0442\u044c \u043f\u043e \u0432\u043e\u0437\u0440\u0430\u0441\u0442\u0430\u043d\u0438\u044e, \u0445\u043e\u0442\u044c \u043f\u043e \u0443\u0431\u044b\u0432\u0430\u043d\u0438\u044e), \u043d\u0430\u0438\u0432\u043d\u043e\u0435 \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u0435 \u0434\u0435\u0440\u0435\u0432\u0430 \u0431\u0443\u0434\u0435\u0442 \u043e\u0442\u043f\u0440\u0430\u0432\u043b\u044f\u0442\u044c \u043d\u043e\u0432\u044b\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0432\u0441\u0451 \u0432\u0440\u0435\u043c\u044f \u0432 \u043e\u0434\u043d\u0443 \u0441\u0442\u043e\u0440\u043e\u043d\u0443, \u0441\u043e\u0431\u0438\u0440\u0430\u044f, \u043f\u043e \u0441\u0443\u0442\u0438, \u043b\u0438\u043d\u0435\u0439\u043d\u044b\u0439 \u0441\u043f\u0438\u0441\u043e\u043a. \u041a\u0430\u043a \u043d\u0435\u0442\u0440\u0443\u0434\u043d\u043e \u0434\u043e\u0433\u0430\u0434\u0430\u0442\u044c\u0441\u044f, \u0447\u0442\u043e \u0432\u0441\u0442\u0430\u0432\u043a\u0430 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432, \u0447\u0442\u043e \u043f\u043e\u0438\u0441\u043a \u0431\u0443\u0434\u0443\u0442 \u043f\u0440\u0438 \u0442\u0430\u043a\u043e\u0439 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0435 \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u0442\u044c \u0437\u0430 \u0432\u0440\u0435\u043c\u044f <em>O<\/em>(<em>N<\/em>), \u0447\u0442\u043e \u0441\u0432\u043e\u0434\u0438\u0442 \u043d\u0430 \u043d\u0435\u0442 \u0432\u0441\u0435 \u0443\u0441\u0438\u043b\u0438\u044f \u043f\u043e \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u044e \u0441\u043b\u043e\u0436\u043d\u043e\u0439 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0434\u0430\u043d\u043d\u044b\u0445.<br \/>  \u0412\u044b\u0432\u043e\u0434: \u0434\u0435\u0440\u0435\u0432\u043e \u043f\u043e\u0438\u0441\u043a\u0430 \u043f\u0440\u0438 \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u0438 \u043d\u0443\u0436\u043d\u043e <em>\u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u043e\u0432\u0430\u0442\u044c<\/em>, \u0442.\u0435. \u0432\u044b\u0440\u0430\u0432\u043d\u0438\u0432\u0430\u0442\u044c \u0432\u044b\u0441\u043e\u0442\u0443 \u043f\u0440\u0430\u0432\u043e\u0433\u043e \u0438 \u043b\u0435\u0432\u043e\u0433\u043e \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u0430 \u0443 \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0443\u0437\u043b\u0430. \u041a \u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u043e\u0432\u043a\u0435 \u0435\u0441\u0442\u044c \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u043f\u043e\u0434\u0445\u043e\u0434\u043e\u0432. \u041f\u0440\u043e\u0441\u0442\u0435\u0439\u0448\u0438\u0439 \u2014 \u0437\u0430\u0434\u0430\u0442\u044c \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u0447\u0438\u0441\u043b\u043e \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u0432\u0441\u0442\u0430\u0432\u043a\u0438 \u0438\u043b\u0438 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044f, \u043f\u043e\u0441\u043b\u0435 \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u0431\u0443\u0434\u0435\u0442 \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u044c\u0441\u044f \u043f\u0435\u0440\u0435\u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u043e\u0432\u043a\u0430 \u0434\u0435\u0440\u0435\u0432\u0430. \u0412 \u0442\u0430\u043a\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u0434\u0435\u0440\u0435\u0432\u043e \u0431\u0443\u0434\u0435\u0442 \u043f\u0435\u0440\u0435\u0434 \u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u043e\u0432\u043a\u043e\u0439 \u0431\u0443\u0434\u0435\u0442 \u0432 \u0434\u043e\u0432\u043e\u043b\u044c\u043d\u043e &#171;\u0437\u0430\u043f\u0443\u0449\u0435\u043d\u043d\u043e\u043c&#187; \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0438, \u0438\u0437-\u0437\u0430 \u0447\u0435\u0433\u043e \u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u043e\u0432\u043a\u0430 \u0431\u0443\u0434\u0435\u0442 \u0437\u0430\u043d\u0438\u043c\u0430\u0442\u044c \u0432\u0440\u0435\u043c\u044f \u043f\u043e\u0440\u044f\u0434\u043a\u0430 <em>O<\/em>(<em>N<\/em>) \u0432 \u0445\u0443\u0434\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435, \u0437\u0430\u0442\u043e \u043f\u043e\u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0435 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u0434\u043e \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u043f\u043e\u0440\u043e\u0433\u0430 \u0432\u0441\u0442\u0430\u0432\u043e\u043a\/\u0443\u0434\u0430\u043b\u0435\u043d\u0438\u0439 \u0431\u0443\u0434\u0443\u0442 \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0442\u044c\u0441\u044f \u0437\u0430 \u043b\u043e\u0433\u0430\u0440\u0438\u0444\u043c\u0438\u0447\u0435\u0441\u043a\u043e\u0435 \u0432\u0440\u0435\u043c\u044f. \u0414\u0440\u0443\u0433\u043e\u0439 \u0436\u0435 \u0432\u0430\u0440\u0438\u0430\u043d\u0442 \u2014 \u0441\u0442\u0440\u043e\u0438\u0442\u044c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u0432\u0441\u0442\u0430\u0432\u043a\u0438 \u0438 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044f \u0441\u0440\u0430\u0437\u0443 \u0442\u0430\u043a, \u0447\u0442\u043e\u0431\u044b \u0434\u0435\u0440\u0435\u0432\u043e \u043f\u043e\u0441\u0442\u043e\u044f\u043d\u043d\u043e \u043e\u0441\u0442\u0430\u0432\u0430\u043b\u043e\u0441\u044c \u0441\u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u043c, \u0447\u0442\u043e \u0434\u0430\u0451\u0442 \u0434\u043b\u044f \u043b\u044e\u0431\u043e\u0439 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 <em>\u0433\u0430\u0440\u0430\u043d\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u0443\u044e<\/em> \u0432\u0440\u0435\u043c\u0435\u043d\u043d\u0443\u044e \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c <em>O<\/em>(log<sub>2<\/sub><em>N<\/em>).<br \/>  \u0412 \u0441\u0432\u044f\u0437\u0438 \u0441 \u0442\u0435\u043c, \u0447\u0442\u043e \u0435\u0441\u0442\u044c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b, \u0432 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0434\u0435\u0440\u0435\u0432\u0443 \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u044e\u0442 &#171;\u0440\u0430\u0437\u0431\u0430\u043b\u0442\u044b\u0432\u0430\u0442\u044c\u0441\u044f&#187;, \u043d\u043e \u043f\u043e\u0441\u043b\u0435 \u044d\u0442\u043e\u0433\u043e \u0434\u043e\u0432\u043e\u043b\u044c\u043d\u043e \u0434\u043e\u043b\u0433\u043e \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u043c\u043e\u0436\u043d\u043e \u043f\u0440\u043e\u0432\u043e\u0434\u0438\u0442\u044c \u0437\u0430 \u043b\u043e\u0433\u0430\u0440\u0438\u0444\u043c\u0438\u0447\u0435\u0441\u043a\u043e\u0435 \u0432\u0440\u0435\u043c\u044f, \u043f\u0440\u0435\u0436\u0434\u0435 \u0447\u0435\u043c \u043f\u0440\u0438\u0434\u0451\u0442\u0441\u044f \u0434\u043e\u043b\u0433\u043e \u043f\u0440\u0438\u0432\u043e\u0434\u0438\u0442\u044c \u0434\u0435\u0440\u0435\u0432\u043e \u043e\u0431\u0440\u0430\u0442\u043d\u043e \u0432 \u0441\u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0435 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435, \u0440\u0430\u0437\u043b\u0438\u0447\u0430\u044e\u0442 <em>\u0433\u0430\u0440\u0430\u043d\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0435<\/em> \u0438 <em>\u0430\u043c\u043e\u0440\u0442\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0435<\/em> \u0432\u0440\u0435\u043c\u044f \u0432\u0441\u0442\u0430\u0432\u043a\u0438\/\u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044f \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430. \u0414\u043b\u044f \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0439 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u0441 \u0434\u0432\u043e\u0438\u0447\u043d\u044b\u043c\u0438 \u0434\u0435\u0440\u0435\u0432\u044c\u044f\u043c\u0438 \u043f\u043e\u0438\u0441\u043a\u0430 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0432\u0441\u0442\u0430\u0432\u043a\u0438 \u0438 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044f <em>O<\/em>(log<sub>2<\/sub><em>N<\/em>) \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0433\u0430\u0440\u0430\u043d\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0439, \u0434\u043b\u044f \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u2014 \u0430\u043c\u043e\u0440\u0442\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0439, \u0441 \u0443\u0445\u0443\u0434\u0448\u0435\u043d\u0438\u0435\u043c \u0434\u043e <em>O<\/em>(<em>N<\/em>).<\/p>\n<p>  <\/p>\n<h3 id=\"algoritm-adelson-velskogo-i-landisa-avl\">\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0410\u0434\u0435\u043b\u044c\u0441\u043e\u043d-\u0412\u0435\u043b\u044c\u0441\u043a\u043e\u0433\u043e \u0438 \u041b\u0430\u043d\u0434\u0438\u0441\u0430 (\u0410\u0412\u041b)<\/h3>\n<p>  <\/p>\n<p>\u041f\u0435\u0440\u0432\u0430\u044f \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u0441\u0430\u043c\u043e\u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u0443\u044e\u0449\u0435\u0433\u043e\u0441\u044f \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430 \u043f\u043e\u0438\u0441\u043a\u0430 \u0431\u044b\u043b\u0430 \u043f\u0440\u0435\u0434\u043b\u043e\u0436\u0435\u043d\u0430 \u0432 1962 \u0433\u043e\u0434\u0443 \u0410\u0434\u0435\u043b\u044c\u0441\u043e\u043d\u043e\u043c-\u0412\u0435\u043b\u044c\u0441\u043a\u0438\u043c \u0438 \u041b\u0430\u043d\u0434\u0438\u0441\u043e\u043c. \u0412 \u0441\u043e\u0432\u0440\u0435\u043c\u0435\u043d\u043d\u043e\u0439 \u043b\u0438\u0442\u0435\u0440\u0430\u0442\u0443\u0440\u0435 \u043f\u043e \u043d\u0430\u0447\u0430\u043b\u044c\u043d\u044b\u043c \u0431\u0443\u043a\u0432\u0430\u043c \u0444\u0430\u043c\u0438\u043b\u0438\u0439 \u044d\u0442\u0430 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f <a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%90%D0%92%D0%9B-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE\">\u0410\u0412\u041b-\u0434\u0435\u0440\u0435\u0432\u044c\u044f<\/a>. \u0421\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u043e\u043f\u0438\u0441\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u043c\u0438 \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u0430\u043c\u0438:<\/p>\n<p>  <\/p>\n<ol>\n<li>\u0423\u043f\u043e\u0440\u044f\u0434\u043e\u0447\u0435\u043d\u043d\u043e\u0441\u0442\u044c: \u0434\u043b\u044f \u043b\u044e\u0431\u043e\u0433\u043e \u0443\u0437\u043b\u0430 \u043a\u043b\u044e\u0447 \u0432 \u0432\u0435\u0440\u0448\u0438\u043d\u0435 \u043b\u0435\u0432\u043e\u0433\u043e \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u0430 \u043c\u0435\u043d\u044c\u0448\u0435, \u0430 \u0432 \u0432\u0435\u0440\u0448\u0438\u043d\u0435 \u043f\u0440\u0430\u0432\u043e\u0433\u043e \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u0430 \u2014 \u0431\u043e\u043b\u044c\u0448\u0435, \u0447\u0435\u043c \u043a\u043b\u044e\u0447 \u0441\u0430\u043c\u043e\u0433\u043e \u0443\u0437\u043b\u0430 (\u0435\u0441\u043b\u0438 \u043f\u043e\u0442\u043e\u043c\u043a\u0438 \u043d\u0435 \u044f\u0432\u043b\u044f\u044e\u0442\u0441\u044f \u043f\u0443\u0441\u0442\u044b\u043c\u0438 \u0443\u0437\u043b\u0430\u043c\u0438).<\/li>\n<li>\u0412\u043e\u0437\u0440\u0430\u0441\u0442\u0430\u043d\u0438\u0435 \u0432\u044b\u0441\u043e\u0442\u044b: \u0432\u044b\u0441\u043e\u0442\u0430 \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u0441\u043a\u043e\u0433\u043e \u0443\u0437\u043b\u0430 \u043d\u0430 \u0435\u0434\u0438\u043d\u0438\u0446\u0443 \u0431\u043e\u043b\u044c\u0448\u0435 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0439 \u0432\u044b\u0441\u043e\u0442\u044b \u0435\u0433\u043e \u043f\u043e\u0442\u043e\u043c\u043a\u043e\u0432. \u0412\u044b\u0441\u043e\u0442\u0430 \u043f\u0443\u0441\u0442\u044b\u0445 \u0443\u0437\u043b\u043e\u0432 \u043c\u043e\u0436\u0435\u0442 \u0441\u0447\u0438\u0442\u0430\u0442\u044c\u0441\u044f \u0440\u0430\u0432\u043d\u043e\u0439 \u043d\u0443\u043b\u044e.<\/li>\n<li>\u0410\u0412\u041b-\u0441\u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0441\u0442\u044c: \u0434\u043b\u044f \u043b\u044e\u0431\u043e\u0433\u043e \u0443\u0437\u043b\u0430 \u0432\u044b\u0441\u043e\u0442\u044b \u043f\u0440\u0430\u0432\u043e\u0433\u043e \u0438 \u043b\u0435\u0432\u043e\u0433\u043e \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u0430 \u043e\u0442\u043b\u0438\u0447\u0430\u044e\u0442\u0441\u044f \u043d\u0435 \u0431\u043e\u043b\u044c\u0448\u0435 \u0447\u0435\u043c \u043d\u0430 1.<\/li>\n<\/ol>\n<p>  <\/p>\n<p>\u0418\u0437 \u044d\u0442\u0438\u0445 \u0441\u0432\u043e\u0439\u0441\u0442\u0432 \u0441\u043b\u0435\u0434\u0443\u0435\u0442, \u0447\u0442\u043e \u0432\u044b\u0441\u043e\u0442\u0430 \u0432\u0441\u0435\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430 \u0441\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442 <em>O<\/em>(log<sub>2<\/sub><em>N<\/em>), \u0433\u0434\u0435 <em>N<\/em> \u2014 \u0447\u0438\u0441\u043b\u043e \u0445\u0440\u0430\u043d\u0438\u043c\u044b\u0445 \u0432 \u0434\u0435\u0440\u0435\u0432\u0435 \u0437\u0430\u043f\u0438\u0441\u0435\u0439, \u0430 \u0437\u043d\u0430\u0447\u0438\u0442, \u043f\u043e\u0438\u0441\u043a \u0437\u0430\u043f\u0438\u0441\u0438 \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u0442 \u0437\u0430 \u043b\u043e\u0433\u0430\u0440\u0438\u0444\u043c\u0438\u0447\u0435\u0441\u043a\u043e\u0435 \u0432\u0440\u0435\u043c\u044f. \u0427\u0442\u043e\u0431\u044b \u0443\u0441\u043b\u043e\u0432\u0438\u0435 \u0410\u0412\u041b-\u0441\u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0441\u0442\u0438 \u0441\u043e\u0445\u0440\u0430\u043d\u044f\u043b\u043e\u0441\u044c \u043f\u043e\u0441\u043b\u0435 \u043a\u0430\u0436\u0434\u043e\u0439 \u0432\u0441\u0442\u0430\u0432\u043a\u0438, \u043a\u0430\u0436\u0434\u0430\u044f \u0432\u0441\u0442\u0430\u0432\u043a\u0430 \u0441\u043e\u043f\u0440\u043e\u0432\u043e\u0436\u0434\u0430\u0435\u0442\u0441\u044f \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0435\u0439 <em>\u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u043e\u0432\u043a\u0438<\/em>. \u0414\u043b\u044f \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u043e\u0433\u043e \u043e\u0441\u0443\u0449\u0435\u0441\u0442\u0432\u043b\u0435\u043d\u0438\u044f \u044d\u0442\u043e\u0439 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u0432 \u043a\u0430\u0436\u0434\u043e\u043c \u0443\u0437\u043b\u0435 \u043d\u0443\u0436\u043d\u043e \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u0441\u043b\u0443\u0436\u0435\u0431\u043d\u0443\u044e \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u044e. \u0414\u043b\u044f \u043f\u0440\u043e\u0441\u0442\u043e\u0442\u044b, \u043f\u0443\u0441\u0442\u044c \u0442\u0430\u043c \u043f\u0440\u043e\u0441\u0442\u043e \u0445\u0440\u0430\u043d\u0438\u0442\u0441\u044f \u0432\u044b\u0441\u043e\u0442\u0430 \u0443\u0437\u043b\u0430.<\/p>\n<p>  <\/p>\n<pre><code class=\"julia\">mutable struct AVLNode{K,V}     # \u043d\u0430\u0434\u0435\u0435\u043c\u0441\u044f, \u0447\u0442\u043e \u0432\u044b\u0441\u043e\u0442\u0430 \u0434\u0435\u0440\u0435\u0432\u0430 \u043d\u0435 \u0431\u0443\u0434\u0435\u0442 \u0431\u043e\u043b\u044c\u0448\u0435 255     # (\u043d\u0435 \u0431\u043e\u043b\u044c\u0448\u0435 10^38 \u0437\u0430\u043f\u0438\u0441\u0435\u0439)     height::UInt8      key::K     value::V     left::Union{Nothing, AVLNode{K,V}}     right::Union{Nothing, AVLNode{K,V}}     parent::AVLNode{K,V}     # \u043f\u0443\u0441\u0442\u043e\u0439 \u043a\u043e\u043d\u0441\u0442\u0440\u0443\u043a\u0442\u043e\u0440     function AVLNode{K,V}() where {K,V}         node = new{K,V}()         node.height = 1         node.parent = node         node.left = node.right = nothing         return node     end     # \u043a\u043e\u043d\u0441\u0442\u0440\u0443\u043a\u0442\u043e\u0440 \u0441 \u043f\u0430\u0440\u043e\u0439 \u043a\u043b\u044e\u0447-\u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435     function AVLNode{K,V}(key::SK, value::SV) where {K, V, SK&lt;:K, SV&lt;:V}         node = new{K,V}()         node.height = 1         node.parent = node         node.left = node.right = nothing         node.key, node.value = key, value         return node     end end  avlheight(node::Union{Nothing,AVLNode}) = node == nothing ? 0 : Int(node.height)<\/code><\/pre>\n<p>  <\/p>\n<h4 id=\"vstavka-zapisi\">\u0412\u0441\u0442\u0430\u0432\u043a\u0430 \u0437\u0430\u043f\u0438\u0441\u0438<\/h4>\n<p>  <\/p>\n<p>\u0411\u0430\u0437\u043e\u0432\u0430\u044f \u0432\u0441\u0442\u0430\u0432\u043a\u0430 \u0434\u0435\u043b\u0430\u0435\u0442\u0441\u044f \u043f\u043e \u0441\u0442\u0430\u043d\u0434\u0430\u0440\u0442\u043d\u043e\u043c\u0443 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0443 \u2014 \u0441\u043f\u0443\u0441\u043a\u0430\u0435\u043c\u0441\u044f \u043f\u043e \u0434\u0435\u0440\u0435\u0432\u0443 \u0432\u043d\u0438\u0437, \u0438\u0449\u0435\u043c, \u043a\u0443\u0434\u0430 \u043c\u043e\u0436\u043d\u043e \u0432\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u043d\u043e\u0432\u044b\u0439 \u0443\u0437\u0435\u043b \u0438 \u0432\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u043c. \u041d\u0430\u043f\u0438\u0448\u0435\u043c \u043e\u0431\u0451\u0440\u0442\u043a\u0438 \u0434\u043b\u044f \u043f\u043e\u043b\u0443\u0447\u0435\u043d\u0438\u044f \u0438 \u0437\u0430\u043c\u0435\u043d\u044b \u0434\u043e\u0447\u0435\u0440\u043d\u0438\u0445 \u0443\u0437\u043b\u043e\u0432 \u0441 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0435\u043c \u0438\u043d\u0434\u0435\u043a\u0441\u043e\u0432 -1 \u0438 1 \u0432\u043c\u0435\u0441\u0442\u043e \u043b\u0435\u0432\u043e\u0433\u043e \u0438 \u043f\u0440\u0430\u0432\u043e\u0433\u043e:<\/p>\n<p>  <\/p>\n<pre><code class=\"julia\">function child(root::AVLNode, side::Signed)     if side == -1         root.left     elseif side == 1         root.right     else         throw(ArgumentError(\"Expecting side=-1 to get the left child or side=1 to get the right child\"))     end end  function insert_child!(root::AVLNode{K,V},                        newnode::Union{Nothing,AVLNode{K,V}},                        side::Signed) where {K,V}     newnode == nothing || (newnode.parent = root)     if side == -1         root.left = newnode     elseif side == 1         root.right = newnode     else         throw(ArgumentError(\"Expecting side=-1 for inserting node to the left or side=1 for inserting to the right\"))     end end<\/code><\/pre>\n<p>  <\/p>\n<p>\u0414\u0430\u043b\u0435\u0435, \u0438\u0434\u0451\u043c \u0432\u0432\u0435\u0440\u0445 \u043f\u043e \u0434\u0435\u0440\u0435\u0432\u0443 \u0438 \u0438\u0449\u0435\u043c \u043d\u0430\u0440\u0443\u0448\u0435\u043d\u0438\u044f \u0443\u0441\u043b\u043e\u0432\u0438\u0439 2 \u0438 3. \u0414\u0430\u043b\u0435\u0435 \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u044b, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043c\u043e\u0433\u0443\u0442 \u043f\u043e\u044f\u0432\u0438\u0442\u044c\u0441\u044f (\u043d\u0430 \u0440\u0438\u0441\u0443\u043d\u043a\u0430\u0445 \u0437\u0435\u043b\u0451\u043d\u044b\u043c \u043e\u0431\u043e\u0437\u043d\u0430\u0447\u0435\u043d \u0443\u0437\u0435\u043b, \u043f\u043e\u043c\u0435\u043d\u044f\u0432\u0448\u0438\u0439 \u0432\u044b\u0441\u043e\u0442\u0443, \u043e\u0431\u0440\u0430\u0431\u0430\u0442\u044b\u0432\u0430\u0435\u043c\u044b\u0439 \u0443\u0437\u0435\u043b \u2014 \u0435\u0433\u043e \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044c).<\/p>\n<p>  <\/p>\n<p><strong>\u0421\u043b\u0443\u0447\u0430\u0439 0<\/strong><br \/>  \u041f\u043e\u0441\u043b\u0435 \u0432\u0441\u0442\u0430\u0432\u043a\u0438 \u0432\u044b\u0441\u043e\u0442\u0430 \u0443\u0437\u043b\u0430 \u0441\u0442\u0430\u043b\u0430 \u0442\u0430\u043a\u043e\u0439 \u0436\u0435, \u043a\u0430\u043a \u0443 \u0441\u0435\u0441\u0442\u0440\u0438\u043d\u0441\u043a\u043e\u0433\u043e, \u0438 \u043d\u0430 1 \u043c\u0435\u043d\u044c\u0448\u0435 (\u0441\u0442\u0430\u0440\u043e\u0439) \u0432\u044b\u0441\u043e\u0442\u044b \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u0441\u043a\u043e\u0433\u043e \u0443\u0437\u043b\u0430.<br \/>  <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/uf\/9_\/iq\/uf9_iqcs1ydiwszzfl8ub8dbxj8.png\"><br \/>  \u0421\u0430\u043c\u044b\u0439 \u043b\u0443\u0447\u0448\u0438\u0439 \u0441\u043b\u0443\u0447\u0430\u0439, \u043d\u0438\u0447\u0435\u0433\u043e \u0434\u0430\u043b\u044c\u0448\u0435 \u0442\u0440\u043e\u0433\u0430\u0442\u044c \u043d\u0435 \u043d\u0430\u0434\u043e. \u0412\u044b\u0448\u0435 \u0442\u043e\u0436\u0435 \u0443\u0436\u0435 \u043c\u043e\u0436\u043d\u043e \u043d\u0435 \u0441\u043c\u043e\u0442\u0440\u0435\u0442\u044c, \u0442.\u043a. \u0442\u0430\u043c \u043d\u0438\u0447\u0435\u0433\u043e \u043d\u0435 \u043f\u043e\u043c\u0435\u043d\u044f\u0435\u0442\u0441\u044f.<\/p>\n<p>  <\/p>\n<p><strong>\u0421\u043b\u0443\u0447\u0430\u0439 1<\/strong><br \/>  \u0414\u043e \u0432\u0441\u0442\u0430\u0432\u043a\u0438 \u0432\u044b\u0441\u043e\u0442\u0430 \u0443\u0437\u043b\u0430 \u0431\u044b\u043b\u0430 \u0440\u0430\u0432\u043d\u0430 \u0432\u044b\u0441\u043e\u0442\u0435 \u0441\u0435\u0441\u0442\u0440\u0438\u043d\u0441\u043a\u043e\u0433\u043e \u0443\u0437\u043b\u0430. \u0412\u0441\u0442\u0430\u0432\u043a\u0430 \u043f\u043e\u0434\u043d\u0438\u043c\u0430\u0435\u0442 \u043a\u043e\u0440\u0435\u043d\u044c \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u0430, \u0438 \u0432\u044b\u0441\u043e\u0442\u0430 \u0443\u0437\u043b\u0430 \u0441\u0440\u0430\u0432\u043d\u0438\u0432\u0430\u0435\u0442\u0441\u044f \u0441 \u0432\u044b\u0441\u043e\u0442\u043e\u0439 \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044f.<br \/>  <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/s4\/nv\/t4\/s4nvt4y-m1znfln4g4ajf2346d0.png\"><\/p>\n<p>  <\/p>\n<p>\u0412 \u044d\u0442\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e &#171;\u043f\u043e\u0434\u043d\u044f\u0442\u044c&#187; \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u0441\u043a\u0438\u0439 \u0443\u0437\u0435\u043b, \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0432 \u0435\u0433\u043e \u0432\u044b\u0441\u043e\u0442\u0443 \u043d\u0430 1. \u041f\u0440\u0438 \u044d\u0442\u043e\u043c \u043d\u0443\u0436\u043d\u043e \u043f\u0440\u043e\u0434\u043e\u043b\u0436\u0438\u0442\u044c \u0434\u0432\u0438\u0433\u0430\u0442\u044c\u0441\u044f \u043a \u043a\u043e\u0440\u043d\u044e \u0434\u0435\u0440\u0435\u0432\u0430, \u043f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 \u0438\u0437\u043c\u0435\u043d\u0435\u043d\u0438\u0435 \u0432\u044b\u0441\u043e\u0442\u044b \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u0441\u043a\u043e\u0433\u043e \u0443\u0437\u043b\u0430 \u043c\u043e\u0433\u043b\u043e \u043f\u0440\u0438\u0432\u0435\u0441\u0442\u0438 \u043a \u043d\u0430\u0440\u0443\u0448\u0435\u043d\u0438\u044e \u0443\u0441\u043b\u043e\u0432\u0438\u044f 2 \u043d\u0430 \u0443\u0440\u043e\u0432\u0435\u043d\u044c \u0432\u044b\u0448\u0435.<br \/>  <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/v-\/j9\/0s\/v-j90s0nar7w4mgas4oujggl3h8.png\"><\/p>\n<p>  <\/p>\n<div class=\"spoiler\"><b class=\"spoiler_title\">\u041a\u043e\u0434<\/b><\/p>\n<div class=\"spoiler_text\">\n<pre><code class=\"julia\">fucntion promote!(nd::AVLNode, by::Integer=1)     nd.height += by end  fucntion demote!(nd::AVLNode, by::Integer=1)     nd.height -= by end<\/code><\/pre>\n<\/div>\n<\/div>\n<p>  <\/p>\n<p><strong>\u0421\u043b\u0443\u0447\u0430\u0439 2<\/strong><\/p>\n<p>  <\/p>\n<p>\u041f\u043e\u0441\u043b\u0435 \u0432\u0441\u0442\u0430\u0432\u043a\u0438 \u0440\u0430\u0437\u043d\u0438\u0446\u0430 \u0432\u044b\u0441\u043e\u0442 \u0441 \u0441\u0435\u0441\u0442\u0440\u0438\u043d\u0441\u043a\u0438\u043c \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u043e\u043c \u0441\u0442\u0430\u043b\u0430 2, \u043f\u0440\u0438\u0447\u0451\u043c &#171;\u0432\u044b\u0442\u043e\u043b\u043a\u043d\u0443\u043b\u043e&#187; \u0432\u0432\u0435\u0440\u0445 \u043b\u0435\u0432\u043e\u0435 \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u043e:<br \/>  <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/la\/bl\/aj\/lablajxlzp2lgvbhm4nlh5j-3ks.png\"><\/p>\n<p>  <\/p>\n<p>\u041f\u0440\u043e\u0431\u043b\u0435\u043c\u0430 \u043b\u0435\u0447\u0438\u0442\u0441\u044f \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0435\u0439, \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u043c\u043e\u0439 &#171;\u043f\u0440\u043e\u0441\u0442\u043e\u0439 \u043f\u043e\u0432\u043e\u0440\u043e\u0442&#187;, \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u0443\u044e\u0449\u0435\u0439 \u0434\u0435\u0440\u0435\u0432\u043e \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c:<\/p>\n<p>  <\/p>\n<p><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/8j\/zc\/yt\/8jzcytyqgke3xpcikei8zrbvbrq.png\"><br \/>  \u041d\u0430 \u043f\u0440\u043e\u0441\u0442\u043e\u0439 \u043f\u043e\u0432\u043e\u0440\u043e\u0442 \u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f 6 \u0438\u0437\u043c\u0435\u043d\u0435\u043d\u0438\u0439 \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u0435\u0439.<br \/>  \u041e\u0431\u0440\u0430\u0442\u0438\u0442\u0435 \u0432\u043d\u0438\u043c\u0430\u043d\u0438\u0435, \u0447\u0442\u043e \u0432 \u043f\u0440\u043e\u0435\u043a\u0446\u0438\u0438 \u043d\u0430 \u0433\u043e\u0440\u0438\u0437\u043e\u043d\u0442\u0430\u043b\u044c\u043d\u0443\u044e \u043e\u0441\u044c \u043f\u043e\u0440\u044f\u0434\u043e\u043a \u0432\u0435\u0440\u0448\u0438\u043d <em>n<\/em>, <em>p<\/em> \u0438 \u0434\u0435\u0440\u0435\u0432\u044c\u0435\u0432 <em>T<\/em><sub>1<\/sub> \u2014 <em>T<\/em><sub>3<\/sub> \u0434\u043e \u0438 \u043f\u043e\u0441\u043b\u0435 \u043f\u043e\u0432\u043e\u0440\u043e\u0442\u0430 \u043e\u0441\u0442\u0430\u0451\u0442\u0441\u044f \u043e\u0434\u043d\u0438\u043c \u0438 \u0442\u0435\u043c \u0436\u0435. \u042d\u0442\u043e \u2014 \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u0435 \u0443\u0441\u043b\u043e\u0432\u0438\u044f \u0443\u043f\u043e\u0440\u044f\u0434\u043e\u0447\u0435\u043d\u043d\u043e\u0441\u0442\u0438. \u041a\u0430\u043a \u0432\u0438\u0434\u043d\u043e, \u043f\u043e\u0441\u043b\u0435 \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u044f \u043f\u043e\u0432\u043e\u0440\u043e\u0442\u0430 \u0432\u044b\u0448\u0435 \u043f\u043e \u0434\u0435\u0440\u0435\u0432\u0443 \u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u043e\u0432\u043a\u0430 \u0443\u0436\u0435 \u043d\u0435 \u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f.<\/p>\n<p>  <\/p>\n<div class=\"spoiler\"><b class=\"spoiler_title\">\u041a\u043e\u0434<\/b><\/p>\n<div class=\"spoiler_text\">\n<pre><code class=\"julia\"># pivot \u043e\u043a\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u0432 \u043a\u043e\u043d\u0446\u0435 \u043d\u0430 \u0441\u0430\u043c\u043e\u043c \u0432\u0435\u0440\u0445\u0443 function rotate!(pivot::AVLNode, dir::Signed)     dir in (-1, 1) || throw(ArgumentError(\"Unknown rotation direction\"))     p = pivot.parent     g = p.parent     p.height = avlheight(child(pivot, dir)) + 1     pivot.height = p.height + 1     # \"\u043f\u0435\u0440\u0435\u0446\u0435\u043f\u043b\u044f\u0435\u043c\" pivot \u043a g     pivot.parent = g     g.left === p &amp;&amp; (g.left = pivot)     g.right === p &amp;&amp; (g.right = pivot)     c = child(pivot, dir)     # \u043f\u0435\u0440\u0435\u0446\u0435\u043f\u043b\u044f\u0435\u043c c \u043a p     insert_child!(p, c, -dir)     # \u043f\u0435\u0440\u0435\u0446\u0435\u043f\u043b\u044f\u0435\u043c p \u043a pivot     insert_child!(pivot, p, dir)     pivot end<\/code><\/pre>\n<\/div>\n<\/div>\n<p>  <\/p>\n<p><strong>\u0421\u043b\u0443\u0447\u0430\u0439 3<\/strong><br \/>  \u041f\u043e\u0441\u043b\u0435 \u0432\u0441\u0442\u0430\u0432\u043a\u0438 \u0440\u0430\u0437\u043d\u0438\u0446\u0430 \u0432\u044b\u0441\u043e\u0442 \u0441 \u0441\u0435\u0441\u0442\u0440\u0438\u043d\u0441\u043a\u0438\u043c \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u043e\u043c \u0441\u0442\u0430\u043b\u0430 2, \u043f\u0440\u0438\u0447\u0451\u043c &#171;\u0432\u044b\u0442\u043e\u043b\u043a\u043d\u0443\u043b\u043e&#187; \u0432\u0432\u0435\u0440\u0445 \u043f\u0440\u0430\u0432\u043e\u0435 \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u043e:<\/p>\n<p>  <\/p>\n<p><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/cs\/el\/1u\/csel1u39enlepfhdrc4bdw_legq.png\"><br \/>  \u0412 \u044d\u0442\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u043e\u0434\u0438\u043d\u043e\u0447\u043d\u044b\u0439 \u043f\u0440\u043e\u0441\u0442\u043e\u0439 \u043f\u043e\u0432\u043e\u0440\u043e\u0442 \u0443\u0436\u0435 \u043d\u0435 \u043f\u043e\u043c\u043e\u0436\u0435\u0442, \u043d\u043e \u043c\u043e\u0436\u043d\u043e \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u043f\u0440\u043e\u0441\u0442\u043e\u0439 \u043f\u043e\u0432\u043e\u0440\u043e\u0442 \u0432\u043b\u0435\u0432\u043e \u0432\u043e\u043a\u0440\u0443\u0433 \u043f\u0440\u0430\u0432\u043e\u0433\u043e \u043f\u043e\u0442\u043e\u043c\u043a\u0430, \u0447\u0442\u043e \u043f\u0440\u0438\u0432\u0435\u0434\u0451\u0442 \u0441\u0438\u0442\u0443\u0430\u0446\u0438\u044e \u043a \u0441\u043b\u0443\u0447\u0430\u044e 2, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0443\u0436\u0435 \u043b\u0435\u0447\u0438\u0442\u0441\u044f \u043f\u0440\u043e\u0441\u0442\u044b\u043c \u043f\u043e\u0432\u043e\u0440\u043e\u0442\u043e\u043c \u0432\u043f\u0440\u0430\u0432\u043e.<br \/>  \u0414\u043b\u044f \u0443\u043c\u0435\u043d\u044c\u0448\u0435\u043d\u0438\u044f \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0430 &#171;\u043f\u0435\u0440\u0435\u0432\u0435\u0448\u0438\u0432\u0430\u043d\u0438\u0439&#187; \u0443\u0437\u043b\u043e\u0432 \u043c\u043e\u0436\u043d\u043e \u0434\u0432\u0430 \u043f\u043e\u0432\u043e\u0440\u043e\u0442\u0430 \u0441\u043a\u043e\u043c\u043f\u043e\u043d\u043e\u0432\u0430\u0442\u044c \u0432 \u043e\u0434\u043d\u0443 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044e, \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u043c\u0443\u044e \u0431\u043e\u043b\u044c\u0448\u0438\u043c, \u0438\u043b\u0438 \u0434\u0432\u043e\u0439\u043d\u044b\u043c \u043f\u043e\u0432\u043e\u0440\u043e\u0442\u043e\u043c. \u0422\u043e\u0433\u0434\u0430 \u0432\u043c\u0435\u0441\u0442\u043e 12 \u0438\u0437\u043c\u0435\u043d\u0435\u043d\u0438\u0439 \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u0435\u0439 \u043d\u0443\u0436\u043d\u043e \u0431\u0443\u0434\u0435\u0442 \u0442\u043e\u043b\u044c\u043a\u043e 10. \u0412 \u0438\u0442\u043e\u0433\u0435 \u0434\u0432\u043e\u0439\u043d\u043e\u0433\u043e \u043f\u043e\u0432\u043e\u0440\u043e\u0442\u0430 \u0434\u0435\u0440\u0435\u0432\u043e \u043f\u0440\u0438\u043e\u0431\u0440\u0435\u0442\u0430\u0435\u0442 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0439 \u0432\u0438\u0434:<br \/>  <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/ub\/ds\/7i\/ubds7iawqzg9uqgned3mxiqs_8m.png\"><br \/>  \u041a\u0430\u043a \u0432\u0438\u0434\u043d\u043e, \u043f\u043e\u0441\u043b\u0435 \u0434\u0432\u043e\u0439\u043d\u043e\u0433\u043e \u043f\u043e\u0432\u043e\u0440\u043e\u0442\u0430 \u0434\u0430\u043b\u044c\u043d\u0435\u0439\u0448\u0435\u0439 \u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u043e\u0432\u043a\u0438 \u0432\u044b\u0448\u0435 \u043f\u043e \u0434\u0435\u0440\u0435\u0432\u0443 \u0442\u0430\u043a\u0436\u0435 \u043d\u0435 \u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f.<\/p>\n<p>  <\/p>\n<div class=\"spoiler\"><b class=\"spoiler_title\">\u041a\u043e\u0434<\/b><\/p>\n<div class=\"spoiler_text\">\n<pre><code class=\"julia\"># pivot \u043e\u043a\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u0432 \u043a\u043e\u043d\u0446\u0435 \u043d\u0430 \u0441\u0430\u043c\u043e\u043c \u0432\u0435\u0440\u0445\u0443 fun\u0441tion double_rotate!(pivot::AVLNode, dir::Signed)     dir in (-1, 1) || throw(ArgumentError(\"Unknown rotation direction\"))     n = pivot.parent     p = n.parent     g = p.parent     pivot.height = n.height     n.height = p.height = pivot.height - 1     # \"\u043f\u0435\u0440\u0435\u0446\u0435\u043f\u043b\u044f\u0435\u043c\" pivot \u043a g     pivot.parent = g     g.left === p &amp;&amp; (g.left = pivot)     g.right === p &amp;&amp; (g.right = pivot)     t2, t3 = child(pivot, -dir), child(pivot, dir)     # \u043f\u0435\u0440\u0435\u0446\u0435\u043f\u043b\u044f\u0435\u043c n \u043a pivot \u0438 t2 \u043a n     insert_child!(n, t2, dir)     insert_child!(pivot, n, -dir)     # \u043f\u0435\u0440\u0435\u0446\u0435\u043f\u043b\u044f\u0435\u043c p \u043a pivot \u0438 t3 \u043a p     insert_child!(p, t3, -dir)     insert_child!(pivot, p, dir)     pivot end<\/code><\/pre>\n<\/div>\n<\/div>\n<p>  <\/p>\n<p>\u0418\u0442\u0430\u043a, \u043f\u0440\u0438 \u0432\u0441\u0442\u0430\u0432\u043a\u0435 \u0437\u0430\u043f\u0438\u0441\u0438 \u0432 \u0410\u0412\u041b-\u0434\u0435\u0440\u0435\u0432\u043e \u043d\u0443\u0436\u043d\u043e <em>O<\/em>(log<sub>2<\/sub><em>N<\/em>) \u0438\u0437\u043c\u0435\u043d\u0435\u043d\u0438\u0439 \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u0438 \u043e \u0432\u044b\u0441\u043e\u0442\u0435 \u0443\u0437\u043b\u043e\u0432 \u0438 \u043d\u0435 \u0431\u043e\u043b\u0435\u0435 \u0434\u0432\u0443\u0445 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u043f\u043e\u0432\u043e\u0440\u043e\u0442\u0430. \u041e\u0431\u044a\u0435\u0434\u0438\u043d\u0438\u043c \u0432\u0441\u0451 \u0432 \u043e\u0434\u043d\u0443 \u0444\u0443\u043d\u043a\u0446\u0438\u044e \u0432\u0441\u0442\u0430\u0432\u043a\u0438. \u041e\u0442 \u0431\u0430\u0437\u043e\u0432\u043e\u0439 \u0432\u0441\u0442\u0430\u0432\u043a\u0438 \u043e\u043d\u0430 \u0431\u0443\u0434\u0435\u0442 \u043e\u0442\u043b\u0438\u0447\u0430\u0442\u044c\u0441\u044f \u0442\u043e\u043b\u044c\u043a\u043e \u0442\u0435\u043c, \u0447\u0442\u043e \u043f\u043e\u0441\u043b\u0435 \u0432\u0441\u0442\u0430\u0432\u043a\u0438 \u043d\u043e\u0432\u043e\u0433\u043e \u0443\u0437\u043b\u0430 \u0432\u044b\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u044f <code>fix_insertion!()<\/code>, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043f\u0440\u043e\u0445\u043e\u0434\u0438\u0442 \u043e\u0442 \u0442\u043e\u043b\u044c\u043a\u043e \u0447\u0442\u043e \u0432\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u043d\u043e\u0433\u043e \u0443\u0437\u043b\u0430 \u043a \u043a\u043e\u0440\u043d\u044e, \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u0442 \u0438 \u043f\u0440\u0438 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e\u0441\u0442\u0438 \u0438\u0441\u043f\u0440\u0430\u0432\u043b\u044f\u0435\u0442 \u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u043e\u0432\u043a\u0443.<\/p>\n<p>  <\/p>\n<pre><code class=\"julia\">function Base.setindex!(avlt::AVLTree{K,V}, val, key) where {K,V}     key, value = convert(K, key), convert(V, val)     parent = avlt.entry.left     # \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u044b\u0439 \u0441\u043b\u0443\u0447\u0430\u0439 - \u0432\u0441\u0442\u0430\u0432\u043a\u0430 \u0432 \u043f\u0443\u0441\u0442\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e     if parent == nothing         newnode = AVLNode{K,V}(key, value)         newnode.parent = avlt.entry         avlt.entry.left = avlt.entry.right = newnode         return val     end      key_found = false     while !key_found         key_found = key == parent.key         if key_found             parent.value = value         else             side = (key &gt; parent.key) * 2 - 1 # true == 1, false == 0             next = child(parent, side)             if next == nothing                 newnode = AVLNode{K,V}(key, value)                 insert_child!(parent, newnode, side)                 fix_insertion!(newnode)                 key_found = true             else                 parent = next             end         end     end     return val end<\/code><\/pre>\n<p>  <\/p>\n<p>\u0424\u0443\u043d\u043a\u0446\u0438\u044f <code>fix_insertion!()<\/code> \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u0442 \u0440\u0430\u0437\u043d\u0438\u0446\u0443 \u0432\u044b\u0441\u043e\u0442 \u0434\u0432\u0443\u0445 \u0434\u043e\u0447\u0435\u0440\u043d\u0438\u0445 \u0443\u0437\u043b\u043e\u0432, \u043d\u0430\u0447\u0438\u043d\u0430\u044f \u0441 \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u0441\u043a\u043e\u0433\u043e \u0443\u0437\u043b\u0430 \u043e\u0442 \u0432\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u043d\u043e\u0433\u043e. \u0415\u0441\u043b\u0438 \u043e\u043d\u0430 \u0440\u0430\u0432\u043d\u0430 1 \u2014 \u043c\u044b \u043d\u0430\u0445\u043e\u0434\u0438\u043c\u0441\u044f \u0432 \u0441\u043b\u0443\u0447\u0430\u0435 1, \u043d\u0443\u0436\u043d\u043e \u043f\u043e\u0434\u043d\u044f\u0442\u044c \u0432\u044b\u0441\u043e\u0442\u0443 \u0443\u0437\u043b\u0430 \u0438 \u043f\u0440\u043e\u0439\u0442\u0438 \u0432\u044b\u0448\u0435. \u0415\u0441\u043b\u0438 \u043e\u043d\u0430 \u043d\u043e\u043b\u044c \u2014 \u0434\u0435\u0440\u0435\u0432\u043e \u0441\u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u043e\u0432\u0430\u043d\u043e. \u0415\u0441\u043b\u0438 \u043e\u043d\u0430 \u0440\u0430\u0432\u043d\u0430 2 \u2014 \u044d\u0442\u043e \u0441\u043b\u0443\u0447\u0430\u0439 2 \u0438\u043b\u0438 3, \u043d\u0443\u0436\u043d\u043e \u043f\u0440\u0438\u043c\u0435\u043d\u0438\u0442\u044c \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u0439 \u043f\u043e\u0432\u043e\u0440\u043e\u0442, \u0438 \u0434\u0435\u0440\u0435\u0432\u043e \u043f\u0440\u0438\u0445\u043e\u0434\u0438\u0442 \u043a \u0441\u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u043c\u0443 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u044e. <\/p>\n<p>  <\/p>\n<pre><code class=\"julia\"># \u0435\u0441\u043b\u0438 \u043f\u0440\u0430\u0432\u043e\u0435 \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u043e \u0432\u044b\u0448\u0435 - \u0434\u0438\u0441\u0431\u0430\u043b\u0430\u043d\u0441 \u043f\u043e\u043b\u043e\u0436\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u0439, # \u0435\u0441\u043b\u0438 \u043b\u0435\u0432\u043e\u0435 - \u043e\u0442\u0440\u0438\u0446\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0439 imbalance(node::AVLNode) = avlheight(node.right) - avlheight(node.left)  function fix_insertion!(start::AVLNode)     node = start.parent     skew = imbalance(node)    # \u0443 \u0444\u0438\u043a\u0442\u0438\u0432\u043d\u043e\u0433\u043e \u0432\u0445\u043e\u0434\u043d\u043e\u0433\u043e \u0443\u0437\u043b\u0430 \u0434\u0438\u0441\u0431\u0430\u043b\u0430\u043d\u0441 0 - \u0442.\u0435. \u043f\u043e\u043f\u0430\u0434\u0430\u043d\u0438\u0435 \u0432 \u043d\u0435\u0433\u043e \u043c\u043e\u0436\u043d\u043e \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u043e \u043d\u0435 \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0442\u044c     while abs(skew) == 1         node.height += 1         node = node.parent         skew = imbalance(node)     end     @assert abs(skew) == 2 || skew == 0     if skew != 0         # \u043f\u043e\u0432\u0435\u0440\u043d\u0443\u0442\u044c \u043d\u0430\u0434\u043e \u0432 \u0441\u0442\u043e\u0440\u043e\u043d\u0443 \u0431\u043e\u043b\u0435\u0435 \u043d\u0438\u0437\u043a\u043e\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430,         # \u0442.\u0435. \u043f\u0440\u043e\u0442\u0438\u0432\u043e\u043f\u043e\u043b\u043e\u0436\u043d\u043e \u0434\u0438\u0441\u0431\u0430\u043b\u0430\u043d\u0441\u0443         dir = -skew \u00f7 2         n = child(node, -dir)         prev_skew = imbalance(n)         @assert abs(prev_skew) == 1         if prev_skew == dir             double_rotate!(child(n, dir), dir)         else             rotate!(n, dir)         end     end end<\/code><\/pre>\n<p>  <\/p>\n<h4 id=\"udalenie-zapisi\">\u0423\u0434\u0430\u043b\u0435\u043d\u0438\u0435 \u0437\u0430\u043f\u0438\u0441\u0438<\/h4>\n<p>  <\/p>\n<p>\u0423\u0434\u0430\u043b\u0435\u043d\u0438\u0435 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0441\u043b\u043e\u0436\u043d\u0435\u0435 \u0432\u0441\u0442\u0430\u0432\u043a\u0438.<br \/>  \u0414\u043b\u044f \u043d\u0430\u0447\u0430\u043b\u0430 \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u043e\u0431\u044b\u0447\u043d\u043e\u0435 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u0435 \u0437\u0430\u043f\u0438\u0441\u0438 \u0438\u0437 \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430 \u043f\u043e\u0438\u0441\u043a\u0430. <\/p>\n<p>  <\/p>\n<ol>\n<li>\u0415\u0441\u043b\u0438 \u0443\u0434\u0430\u043b\u044f\u0435\u043c\u0430\u044f \u0437\u0430\u043f\u0438\u0441\u044c \u0432 \u043b\u0438\u0441\u0442\u0435 \u2014 \u0442\u043e \u0437\u0430\u043f\u0438\u0441\u044c \u043f\u0440\u043e\u0441\u0442\u043e \u0443\u0434\u0430\u043b\u044f\u0435\u0442\u0441\u044f, \u0442\u0443\u0442 \u0432\u0441\u0451 \u043f\u0440\u043e\u0441\u0442\u043e.<\/li>\n<li>\u0415\u0441\u043b\u0438 \u0443\u0434\u0430\u043b\u044f\u0435\u043c\u0430\u044f \u0437\u0430\u043f\u0438\u0441\u044c \u0432 \u0443\u0437\u043b\u0435, \u0443 \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u0442\u043e\u043b\u044c\u043a\u043e \u043e\u0434\u0438\u043d \u043f\u043e\u0442\u043e\u043c\u043e\u043a \u2014 \u0442\u043e \u044d\u0442\u043e\u0442 \u043f\u043e\u0442\u043e\u043c\u043e\u043a \u0432\u043c\u0435\u0441\u0442\u0435 \u0441\u043e \u0432\u0441\u0435\u043c \u0441\u0432\u043e\u0438\u043c \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u043e\u043c \u0441\u0442\u0430\u0432\u0438\u0442\u0441\u044f \u043d\u0430 \u043c\u0435\u0441\u0442\u043e \u0443\u0434\u0430\u043b\u0451\u043d\u043d\u043e\u0433\u043e \u0443\u0437\u043b\u0430.<\/li>\n<li>\u0415\u0441\u043b\u0438 \u043f\u043e\u0442\u043e\u043c\u043a\u043e\u0432 \u0434\u0432\u0430 \u2014 \u0442\u043e \u043b\u0438\u0431\u043e \u0432 \u043b\u0435\u0432\u043e\u043c \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u0435 \u0438\u0449\u0435\u0442\u0441\u044f \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442, \u043b\u0438\u0431\u043e \u0432 \u043f\u0440\u0430\u0432\u043e\u043c \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439, \u0438\u0437\u0432\u043b\u0435\u043a\u0430\u0435\u0442\u0441\u044f \u0438\u0437 \u0434\u0435\u0440\u0435\u0432\u0430 (\u043f\u043e \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u0443 \u0434\u0435\u0440\u0435\u0432\u0430 \u043f\u043e\u0438\u0441\u043a\u0430 \u0443\u0437\u0435\u043b \u0441 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u043c \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u043c \u0433\u0430\u0440\u0430\u043d\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e \u043d\u0435 \u0438\u043c\u0435\u0435\u0442 \u043f\u0440\u0430\u0432\u043e\u0433\u043e \u043f\u043e\u0442\u043e\u043c\u043a\u0430, \u0430 \u0441 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u043c \u2014 \u043b\u0435\u0432\u043e\u0433\u043e, \u0442\u0430\u043a \u0447\u0442\u043e \u044d\u0442\u043e \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u0435 \u0434\u0435\u043b\u0430\u0435\u0442\u0441\u044f \u043f\u0440\u043e\u0441\u0442\u043e) \u0438 \u0441\u0442\u0430\u0432\u0438\u0442\u0441\u044f \u043d\u0430 \u043c\u0435\u0441\u0442\u043e \u0443\u0434\u0430\u043b\u044f\u0435\u043c\u043e\u0439 \u0437\u0430\u043f\u0438\u0441\u0438.<\/li>\n<\/ol>\n<p>  <\/p>\n<p>\u041d\u043e \u043f\u043e\u0441\u043b\u0435 \u044d\u0442\u043e\u0433\u043e \u043c\u043e\u0436\u0435\u0442 \u043d\u0430\u0440\u0443\u0448\u0438\u0442\u044c\u0441\u044f \u0431\u0430\u043b\u0430\u043d\u0441 \u0434\u0435\u0440\u0435\u0432\u0430, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u043e\u0442 \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044f \u0443\u0434\u0430\u043b\u0451\u043d\u043d\u043e\u0433\u043e \u0443\u0437\u043b\u0430 \u043d\u0443\u0436\u043d\u043e \u043f\u0440\u043e\u0439\u0442\u0438\u0441\u044c \u0432\u0432\u0435\u0440\u0445, \u0432\u043e\u0441\u0441\u0442\u0430\u043d\u0430\u0432\u043b\u0438\u0432\u0430\u044f \u0435\u0433\u043e. \u0417\u0430\u043c\u0435\u0442\u0438\u043c, \u0447\u0442\u043e \u0432 \u0441\u0430\u043c\u043e\u043c \u043d\u0430\u0447\u0430\u043b\u0435 \u0433\u0430\u0440\u0430\u043d\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e \u043e\u0434\u0438\u043d \u0438\u0437 \u043f\u043e\u0442\u043e\u043c\u043a\u043e\u0432 \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0435\u043c\u043e\u0433\u043e \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044f \u0443\u043c\u0435\u043d\u044c\u0448\u0438\u043b \u0432\u044b\u0441\u043e\u0442\u0443 \u043d\u0430 1. \u0421 \u0443\u0447\u0451\u0442\u043e\u043c \u044d\u0442\u043e\u0433\u043e \u043d\u0443\u0436\u043d\u043e \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0435\u0442\u044c \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u044b (\u043a\u0440\u0430\u0441\u043d\u044b\u043c \u043f\u043e\u043a\u0430\u0437\u0430\u043d\u044b \u0443\u0437\u043b\u044b, \u043f\u043e\u043c\u0435\u043d\u044f\u0432\u0448\u0438\u0435 \u0432\u044b\u0441\u043e\u0442\u0443, \u043e\u0431\u0440\u0430\u0431\u0430\u0442\u044b\u0432\u0430\u0435\u043c\u044b\u0439 \u0443\u0437\u0435\u043b \u2014 \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u0441\u043a\u0438\u0439 \u043e\u0442 \u043a\u0440\u0430\u0441\u043d\u043e\u0433\u043e):<\/p>\n<p>  <\/p>\n<p><strong>\u0421\u043b\u0443\u0447\u0430\u0439 1<\/strong><br \/>  \u041d\u0443\u043b\u0435\u0432\u043e\u0439 \u0434\u0438\u0441\u0431\u0430\u043b\u0430\u043d\u0441. \u0417\u043d\u0430\u0447\u0438\u0442, \u0434\u043e \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044f \u043e\u043d \u0431\u044b\u043b 1 \u043f\u043e \u043c\u043e\u0434\u0443\u043b\u044e, \u0438 \u0442\u0435\u043f\u0435\u0440\u044c \u0434\u043e\u0447\u0435\u0440\u043d\u0438\u0435 \u0443\u0437\u043b\u044b \u043d\u0430 2 \u043d\u0438\u0436\u0435 \u043c\u0430\u0442\u0435\u0440\u0438\u043d\u0441\u043a\u043e\u0433\u043e.<br \/>  <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/mo\/cm\/a_\/mocma_jzetjrizjwiesbdtx1rtu.png\"><br \/>  \u041d\u0443\u0436\u043d\u043e \u043e\u043f\u0443\u0441\u0442\u0438\u0442\u044c \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u0441\u043a\u0438\u0439 \u0443\u0437\u0435\u043b \u043d\u0430 1 \u0438 \u043f\u0440\u043e\u0434\u043e\u043b\u0436\u0438\u0442\u044c \u0434\u0432\u0438\u0436\u0435\u043d\u0438\u0435 \u0432\u0432\u0435\u0440\u0445.<br \/>  <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/j8\/6y\/yi\/j86yyi7cxkzasggld6pzo9fldwu.png\"><\/p>\n<p>  <\/p>\n<p><strong>\u0421\u043b\u0443\u0447\u0430\u0439 2<\/strong><br \/>  \u0414\u0438\u0441\u0431\u0430\u043b\u0430\u043d\u0441 1 \u043f\u043e \u043c\u043e\u0434\u0443\u043b\u044e.<br \/>  <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/hn\/8v\/cx\/hn8vcxpvolbjnafm9h3u08kpnoo.png\"><br \/>  \u0410\u0412\u041b-\u0443\u0441\u043b\u043e\u0432\u0438\u0435 \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u043e, \u043c\u043e\u0436\u043d\u043e \u043e\u0441\u0442\u0430\u043d\u043e\u0432\u0438\u0442\u044c\u0441\u044f.<\/p>\n<p>  <\/p>\n<p><strong>\u0421\u043b\u0443\u0447\u0430\u0439 3<\/strong><br \/>  \u0414\u0438\u0441\u0431\u0430\u043b\u0430\u043d\u0441 2 \u043f\u043e \u043c\u043e\u0434\u0443\u043b\u044e, \u0441\u0435\u0441\u0442\u0440\u0438\u043d\u0441\u043a\u0438\u0439 \u0443\u0437\u0435\u043b \u043a \u043e\u043f\u0443\u0441\u0442\u0438\u0432\u0448\u0435\u043c\u0443\u0441\u044f \u0438\u043c\u0435\u0435\u0442 \u043d\u0435\u043d\u0443\u043b\u0435\u0432\u043e\u0439 \u0434\u0438\u0441\u0431\u0430\u043b\u0430\u043d\u0441.<br \/>  <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/vr\/_f\/jc\/vr_fjcvwl3zxc6ocy622l2sszrw.png\"><br \/>  \u0412\u043e\u0441\u0441\u0442\u0430\u043d\u0430\u0432\u043b\u0438\u0432\u0430\u0435\u043c \u0431\u0430\u043b\u0430\u043d\u0441 \u043f\u0440\u043e\u0441\u0442\u044b\u043c (\u0435\u0441\u043b\u0438 T<sub>1<\/sub> \u043d\u0438\u0436\u0435, \u0447\u0435\u043c T<sub>2<\/sub>) \u0438\u043b\u0438 \u0434\u0432\u043e\u0439\u043d\u044b\u043c (\u0432 \u043e\u0431\u0440\u0430\u0442\u043d\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435) \u043f\u043e\u0432\u043e\u0440\u043e\u0442\u043e\u043c, \u043a\u0430\u043a \u0434\u0435\u043b\u0430\u043b\u0438 \u043f\u0440\u0438 \u0432\u0441\u0442\u0430\u0432\u043a\u0435. \u0412\u044b\u0441\u043e\u0442\u0430 \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u0430 \u043f\u0440\u0438 \u044d\u0442\u043e\u043c \u0443\u043c\u0435\u043d\u044c\u0448\u0430\u0435\u0442\u0441\u044f, \u0442.\u0435. \u043c\u043e\u0436\u0435\u0442 \u0432\u043e\u0437\u043d\u0438\u043a\u043d\u0443\u0442\u044c \u043d\u0430\u0440\u0443\u0448\u0435\u043d\u0438\u0435 \u0432\u044b\u0448\u0435 \u043f\u043e \u0434\u0435\u0440\u0435\u0432\u0443.<br \/>  <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/h9\/5f\/qx\/h95fqxdbbqukr_eyjbhbjyyoju4.png\"><\/p>\n<p>  <\/p>\n<p><strong>\u0421\u043b\u0443\u0447\u0430\u0439 4<\/strong><br \/>  \u0414\u0438\u0441\u0431\u0430\u043b\u0430\u043d\u0441 2 \u043f\u043e \u043c\u043e\u0434\u0443\u043b\u044e, \u0441\u0435\u0441\u0442\u0440\u0438\u043d\u0441\u043a\u0438\u0439 \u0443\u0437\u0435\u043b \u0438\u043c\u0435\u0435\u0442 \u043d\u0443\u043b\u0435\u0432\u043e\u0439 \u0434\u0438\u0441\u0431\u0430\u043b\u0430\u043d\u0441.<br \/>  <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/o6\/rl\/mq\/o6rlmq62rxnxxyh6knsz3xne4te.png\"><br \/>  \u041f\u0440\u043e\u0441\u0442\u043e\u0439 \u043f\u043e\u0432\u043e\u0440\u043e\u0442 \u0432\u043e\u0441\u0441\u0442\u0430\u043d\u0430\u0432\u043b\u0438\u0432\u0430\u0435\u0442 \u0443\u0441\u043b\u043e\u0432\u0438\u0435 \u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u043e\u0432\u043a\u0438, \u0432\u044b\u0441\u043e\u0442\u0430 \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u0430 \u043f\u0440\u0438 \u044d\u0442\u043e\u043c \u043d\u0435 \u043c\u0435\u043d\u044f\u0435\u0442\u0441\u044f \u2014 \u043e\u0441\u0442\u0430\u043d\u0430\u0432\u043b\u0438\u0432\u0430\u0435\u043c \u0434\u0432\u0438\u0436\u0435\u043d\u0438\u0435 \u043d\u0430\u0432\u0435\u0440\u0445.<br \/>  <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/sw\/c-\/d5\/swc-d56rswsunltv7_3g60tvufq.png\"><\/p>\n<p>  <\/p>\n<div class=\"spoiler\"><b class=\"spoiler_title\">\u041a\u043e\u0434 \u0434\u043b\u044f \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044f \u043a\u043b\u044e\u0447\u0430<\/b><\/p>\n<div class=\"spoiler_text\">\n<pre><code class=\"julia\">function next_node(node::AVLNode)     next = node.right     if next == nothing         p = node.parent         next = p.parent         while (next !== p) &amp;&amp; (next.key &lt; p.key)             p, next = next, next.parent         end         return (next === p ? nothing : next)     else         while next.left != nothing             next = next.left         end         return next     end  end  function Base.delete!(avlt::AVLTree{K,V}, key) where {K,V}     key = convert(K, key)     candidate = avlt.entry.left     dir = 0     while candidate.key != key         dir = 2 * (key &gt; candidate.key) - 1         candidate = child(candidate, dir)         candidate == nothing &amp;&amp; return     end     val = candidate.value     for side in (-1, 1)         if child(candidate, side) == nothing             p, s = candidate.parent, child(candidate, -side)             if p === p.parent                 insert_child!(p, s, 1)                 insert_child!(p, s, -1)             else                 insert_child!(p, s, dir)                 fix_deletion!(p)             end             return         end     end     swap = next_node(candidate)     cp, sp, sr = candidate.parent, swap.parent, swap.right     swap.height = candidate.height     insert_child!(swap, candidate.left, -1)     for side in (-1, 1)         child(cp, side) === candidate &amp;&amp; insert_child!(cp, swap, side)     end     if sp === candidate         fix_deletion!(swap)     else         insert_child!(swap, candidate.right, 1)         insert_child!(sp, sr, -1)         fix_deletion!(sp)     end     return end  function fix_deletion!(start::AVLNode)     node = start     skew = imbalance(node)     while (node !== node.parent) &amp;&amp; (abs(skew) != 1)         if skew != 0             @assert abs(skew) == 2             dir = -skew \u00f7 2             n = child(node, -dir)             prev_skew = imbalance(n)             @assert abs(prev_skew) &lt; 2             if prev_skew == dir                 node = double_rotate!(child(n, dir), dir)             else                 node = rotate!(n, dir)                 prev_skew != 0 || break             end         else             node.height -= 1         end         node = node.parent         skew = imbalance(node)     end end<\/code><\/pre>\n<\/div>\n<\/div>\n<p>  <\/p>\n<h3 id=\"vzlyot-i-padenie-avl-derevev\">\u0412\u0437\u043b\u0451\u0442 \u0438 \u043f\u0430\u0434\u0435\u043d\u0438\u0435 \u0410\u0412\u041b-\u0434\u0435\u0440\u0435\u0432\u044c\u0435\u0432<\/h3>\n<p>  <\/p>\n<p>\u041d\u0435 \u043e\u0447\u0435\u043d\u044c \u043f\u0440\u0438\u044f\u0442\u043d\u043e\u0435 \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u043e \u043a\u043b\u0430\u0441\u0441\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u0410\u0412\u041b-\u0434\u0435\u0440\u0435\u0432\u044c\u0435\u0432 \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0432 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u0438 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044f \u0437\u0430\u043f\u0438\u0441\u0438: \u0442.\u043a. \u043f\u043e\u0432\u043e\u0440\u043e\u0442 \u043c\u043e\u0436\u0435\u0442 &#171;\u0441\u0431\u0440\u043e\u0441\u0438\u0442\u044c&#187; \u0432\u0441\u0451 \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u043e \u043d\u0430 \u0443\u0440\u043e\u0432\u0435\u043d\u044c \u0432\u043d\u0438\u0437, \u0442\u043e \u0432 \u0445\u0443\u0434\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u0435 \u0442\u0440\u0435\u0431\u0443\u0435\u0442 <em>O<\/em>(log<sub>2<\/sub><em>N<\/em>) \u043f\u043e\u0432\u043e\u0440\u043e\u0442\u043e\u0432 \u0434\u0435\u0440\u0435\u0432\u0430 \u2014 \u043f\u0440\u0438 \u043a\u0430\u0436\u0434\u043e\u043c \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u0435 \u043d\u0430 \u0443\u0440\u043e\u0432\u0435\u043d\u044c \u0432\u0432\u0435\u0440\u0445 \u0432 <code>fix_deletion!()<\/code>.<\/p>\n<p>  <\/p>\n<p>\u0418\u0437-\u0437\u0430 \u044d\u0442\u043e\u0439 \u043d\u0435 \u043e\u0447\u0435\u043d\u044c \u0445\u043e\u0440\u043e\u0448\u0435\u0439 \u0430\u0441\u0438\u043c\u043f\u0442\u043e\u0442\u0438\u043a\u0438 \u0410\u0412\u041b-\u0434\u0435\u0440\u0435\u0432\u044c\u044f \u0443\u0441\u0442\u0443\u043f\u0438\u043b\u0438 \u043c\u0435\u0441\u0442\u043e \u043f\u043e\u044f\u0432\u0438\u0432\u0448\u0438\u043c\u0441\u044f \u0432 1970-\u0445 \u043a\u0440\u0430\u0441\u043d\u043e-\u0447\u0451\u0440\u043d\u044b\u043c \u0434\u0435\u0440\u0435\u0432\u044c\u044f\u043c, \u0443 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0431\u043e\u043b\u0435\u0435 \u0441\u043b\u0430\u0431\u043e\u0435 \u0443\u0441\u043b\u043e\u0432\u0438\u0435 \u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u043e\u0432\u043a\u0438 \u2014 \u043f\u0443\u0442\u044c \u043e\u0442 \u043a\u043e\u0440\u043d\u044f \u0434\u043e \u0441\u0430\u043c\u043e\u0433\u043e \u0434\u0430\u043b\u044c\u043d\u0435\u0433\u043e \u043b\u0438\u0441\u0442\u0430 \u043d\u0435 \u0431\u043e\u043b\u0435\u0435 \u0447\u0435\u043c \u0432\u0434\u0432\u043e\u0435 \u043f\u0440\u0435\u0432\u044b\u0448\u0430\u0435\u0442 \u043f\u0443\u0442\u044c \u043e\u0442 \u043a\u043e\u0440\u043d\u044f \u0434\u043e \u0441\u0430\u043c\u043e\u0433\u043e \u0431\u043b\u0438\u0436\u043d\u0435\u0433\u043e \u043b\u0438\u0441\u0442\u0430. \u0418\u0437-\u0437\u0430 \u044d\u0442\u043e\u0433\u043e \u0432\u044b\u0441\u043e\u0442\u0430 \u043a\u0440\u0430\u0441\u043d\u043e-\u0447\u0451\u0440\u043d\u044b\u0445 \u0434\u0435\u0440\u0435\u0432\u044c\u0435\u0432 \u0441\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442 \u0432 \u0445\u0443\u0434\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435 2log<sub>2<\/sub><em>N<\/em> \u043f\u0440\u043e\u0442\u0438\u0432 1,44log<sub>2<\/sub><em>N<\/em> \u0443 \u0410\u0412\u041b-\u0434\u0435\u0440\u0435\u0432\u044c\u0435\u0432, \u0437\u0430\u0442\u043e \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u0435 \u0437\u0430\u043f\u0438\u0441\u0438 \u0442\u0440\u0435\u0431\u0443\u0435\u0442 \u043d\u0435 \u0431\u043e\u043b\u0435\u0435 \u0442\u0440\u0451\u0445 \u043f\u0440\u043e\u0441\u0442\u044b\u0445 \u043f\u043e\u0432\u043e\u0440\u043e\u0442\u043e\u0432. \u0422\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, \u043f\u043e\u0438\u0441\u043a \u0438 \u0432\u0441\u0442\u0430\u0432\u043a\u0430 \u0437\u0430 \u0441\u0447\u0451\u0442 \u0431\u043e\u043b\u0435\u0435 \u0432\u044b\u0441\u043e\u043a\u043e\u0439 \u0432\u044b\u0441\u043e\u0442\u044b \u0434\u0435\u0440\u0435\u0432\u0430 \u043f\u043e\u0442\u0435\u043d\u0446\u0438\u0430\u043b\u044c\u043d\u043e \u043f\u0440\u043e\u0438\u0433\u0440\u044b\u0432\u0430\u044e\u0442 \u0432 \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438, \u0437\u0430\u0442\u043e \u0435\u0441\u0442\u044c \u043f\u043e\u0442\u0435\u043d\u0446\u0438\u0430\u043b\u044c\u043d\u044b\u0439 \u0432\u044b\u0438\u0433\u0440\u044b\u0448, \u0435\u0441\u043b\u0438 \u0432\u0441\u0442\u0430\u0432\u043a\u0438 \u0447\u0430\u0441\u0442\u043e \u043f\u0435\u0440\u0435\u043c\u0435\u0436\u0430\u044e\u0442\u0441\u044f \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044f\u043c\u0438.<\/p>\n<p>  <\/p>\n<h3 id=\"avl-nanosyat-otvetnyy-udar\">\u0410\u0412\u041b \u043d\u0430\u043d\u043e\u0441\u044f\u0442 \u043e\u0442\u0432\u0435\u0442\u043d\u044b\u0439 \u0443\u0434\u0430\u0440<\/h3>\n<p>  <\/p>\n<p>\u041f\u043e\u043b\u0443\u0447\u0430\u0435\u0442\u0441\u044f, \u0447\u0442\u043e &#171;\u0438\u0434\u0435\u0430\u043b\u044c\u043d\u044b\u0439&#187; \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u044f \u0434\u0432\u043e\u0438\u0447\u043d\u044b\u0445 \u0434\u0435\u0440\u0435\u0432\u044c\u0435\u0432 \u043f\u043e\u0438\u0441\u043a\u0430 \u0434\u043e\u043b\u0436\u0435\u043d \u0433\u0430\u0440\u0430\u043d\u0442\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u043d\u0435\u0431\u043e\u043b\u044c\u0448\u0443\u044e \u0432\u044b\u0441\u043e\u0442\u0443 (\u043d\u0430 \u0443\u0440\u043e\u0432\u043d\u0435 \u043a\u043b\u0430\u0441\u0441\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u0410\u0412\u041b-\u0434\u0435\u0440\u0435\u0432\u0430) \u0438 \u043a\u043e\u043d\u0441\u0442\u0430\u043d\u0442\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e \u043f\u043e\u0432\u043e\u0440\u043e\u0442\u043e\u0432 \u043a\u0430\u043a \u043f\u0440\u0438 \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u0438, \u0442\u0430\u043a \u0438 \u043f\u0440\u0438 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u0438 \u0437\u0430\u043f\u0438\u0441\u0438. \u0422\u0430\u043a\u043e\u0433\u043e \u043f\u043e\u043a\u0430 \u043d\u0435 \u043f\u0440\u0438\u0434\u0443\u043c\u0430\u043d\u043e, \u043d\u043e \u0432 2015 \u0433\u043e\u0434\u0443 \u0431\u044b\u043b\u0430 \u043e\u043f\u0443\u0431\u043b\u0438\u043a\u043e\u0432\u0430\u043d\u0430 <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/publication\/rank-balanced-trees-2\/\">\u0440\u0430\u0431\u043e\u0442\u0430<\/a>, \u0433\u0434\u0435 \u043f\u0440\u0435\u0434\u043b\u043e\u0436\u0435\u043d\u0430 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430, \u0443\u043b\u0443\u0447\u0448\u0430\u044e\u0449\u0430\u044f \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u0430 \u043a\u0430\u043a \u0410\u0412\u041b, \u0442\u0430\u043a \u0438 \u043a\u0440\u0430\u0441\u043d\u043e-\u0447\u0451\u0440\u043d\u044b\u0445 \u0434\u0435\u0440\u0435\u0432\u044c\u0435\u0432. \u0418\u0434\u0435\u044f \u043b\u0435\u0436\u0438\u0442 \u0431\u043b\u0438\u0436\u0435 \u043a \u0410\u0412\u041b \u0434\u0435\u0440\u0435\u0432\u044c\u044f\u043c, \u043d\u043e \u0443\u0441\u043b\u043e\u0432\u0438\u0435 \u0431\u0430\u043b\u0430\u043d\u0441\u0430 \u043e\u0441\u043b\u0430\u0431\u043b\u0435\u043d\u043e, \u0447\u0442\u043e\u0431\u044b \u043f\u043e\u0437\u0432\u043e\u043b\u0438\u0442\u044c \u0431\u043e\u043b\u0435\u0435 \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u043e\u0435 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u0435 \u0437\u0430\u043f\u0438\u0441\u0435\u0439. \u0421\u0432\u043e\u0439\u0441\u0442\u0432\u0430 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b, \u043d\u0430\u0437\u0432\u0430\u043d\u043d\u043e\u0439 &#171;\u0441\u043b\u0430\u0431\u044b\u043c \u0410\u0412\u041b-\u0434\u0435\u0440\u0435\u0432\u043e\u043c&#187; (W(eak)AVL-\u0434\u0435\u0440\u0435\u0432\u043e\u043c) \u0444\u043e\u0440\u043c\u0443\u043b\u0438\u0440\u0443\u044e\u0442\u0441\u044f \u0442\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c:<\/p>\n<p>  <\/p>\n<ol>\n<li>\u0423\u043f\u043e\u0440\u044f\u0434\u043e\u0447\u0435\u043d\u043d\u043e\u0441\u0442\u044c: \u0434\u043b\u044f \u043b\u044e\u0431\u043e\u0433\u043e \u0443\u0437\u043b\u0430 \u043a\u043b\u044e\u0447 \u0432 \u0432\u0435\u0440\u0448\u0438\u043d\u0435 \u043b\u0435\u0432\u043e\u0433\u043e \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u0430 \u043c\u0435\u043d\u044c\u0448\u0435, \u0430 \u0432 \u0432\u0435\u0440\u0448\u0438\u043d\u0435 \u043f\u0440\u0430\u0432\u043e\u0433\u043e \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u0430 \u2014 \u0431\u043e\u043b\u044c\u0448\u0435, \u0447\u0435\u043c \u043a\u043b\u044e\u0447 \u0441\u0430\u043c\u043e\u0433\u043e \u0443\u0437\u043b\u0430 (\u0435\u0441\u043b\u0438 \u043f\u043e\u0442\u043e\u043c\u043a\u0438 \u043d\u0435 \u044f\u0432\u043b\u044f\u044e\u0442\u0441\u044f \u043f\u0443\u0441\u0442\u044b\u043c\u0438 \u0443\u0437\u043b\u0430\u043c\u0438).<\/li>\n<li>\u0412\u043e\u0437\u0440\u0430\u0441\u0442\u0430\u043d\u0438\u0435 \u0440\u0430\u043d\u0433\u0430. \u041a\u0430\u0436\u0434\u043e\u043c\u0443 \u0443\u0437\u043b\u0443 \u043f\u0440\u0438\u043f\u0438\u0441\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u0440\u0430\u043d\u0433. \u0420\u0430\u043d\u0433 \u0432\u0441\u0435\u0445 \u043f\u0443\u0441\u0442\u044b\u0445 \u0443\u0437\u043b\u043e\u0432 \u0440\u0430\u0432\u0435\u043d \u043d\u0443\u043b\u044e, \u0440\u0430\u043d\u0433 \u043b\u0438\u0441\u0442\u043e\u0432 \u2014 1. \u0420\u0430\u043d\u0433 \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u0441\u043a\u043e\u0433\u043e \u0443\u0437\u043b\u0430 \u0441\u0442\u0440\u043e\u0433\u043e \u0431\u043e\u043b\u044c\u0448\u0435 \u0440\u0430\u043d\u0433\u0430 \u0434\u043e\u0447\u0435\u0440\u043d\u0435\u0433\u043e.<\/li>\n<li>\u0421\u043b\u0430\u0431\u0430\u044f \u0410\u0412\u041b-\u0441\u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0441\u0442\u044c: \u0440\u0430\u043d\u0433 \u0443\u0437\u043b\u0430 \u043e\u0442\u043b\u0438\u0447\u0430\u0435\u0442\u0441\u044f \u043e\u0442 \u0440\u0430\u043d\u0433\u0430 \u0434\u043e\u0447\u0435\u0440\u043d\u0438\u0445 \u0443\u0437\u043b\u043e\u0432 \u043d\u0435 \u0431\u043e\u043b\u0435\u0435 \u0447\u0435\u043c \u043d\u0430 2.<\/li>\n<\/ol>\n<p>  <\/p>\n<p>\u041e\u043a\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f, \u0447\u0442\u043e \u0442\u0430\u043a\u0430\u044f \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u0432\u043a\u043b\u044e\u0447\u0430\u0435\u0442 \u0432 \u0441\u0435\u0431\u044f \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u0430 \u0438 \u043a\u043b\u0430\u0441\u0441\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u0410\u0412\u041b-\u0434\u0435\u0440\u0435\u0432\u044c\u0435\u0432, \u0438 \u043a\u0440\u0430\u0441\u043d\u043e-\u0447\u0451\u0440\u043d\u044b\u0445 \u0434\u0435\u0440\u0435\u0432\u044c\u0435\u0432. \u0412 \u0447\u0430\u0441\u0442\u043d\u043e\u0441\u0442\u0438, \u0435\u0441\u043b\u0438 \u0432\u0432\u0435\u0441\u0442\u0438 \u0443\u0441\u043b\u043e\u0432\u0438\u0435, \u0447\u0442\u043e <em>\u043e\u0431\u0430<\/em> \u0434\u043e\u0447\u0435\u0440\u043d\u0438\u0445 \u0443\u0437\u043b\u0430 \u043d\u0435 \u043c\u043e\u0433\u0443\u0442 \u043e\u0442\u043b\u0438\u0447\u0430\u0442\u044c\u0441\u044f \u043e\u0442 \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u0441\u043a\u043e\u0433\u043e \u043f\u043e \u0440\u0430\u043d\u0433\u0443 \u043d\u0430 2, \u0442\u043e \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u0441\u044f \u043e\u0431\u044b\u0447\u043d\u043e\u0435 \u0410\u0412\u041b \u0434\u0435\u0440\u0435\u0432\u043e, \u0430 \u0440\u0430\u043d\u0433 \u0431\u0443\u0434\u0435\u0442 \u0442\u043e\u0447\u043d\u043e \u0441\u043e\u0432\u043f\u0430\u0434\u0430\u0442\u044c \u0441 \u0432\u044b\u0441\u043e\u0442\u043e\u0439 \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u0430.<br \/>  \u041f\u0440\u0435\u043b\u0435\u0441\u0442\u044c \u0421\u0410\u0412\u041b-\u0434\u0435\u0440\u0435\u0432\u044c\u0435\u0432 \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e \u043d\u0435\u0431\u043e\u043b\u044c\u0448\u043e\u0435 \u043e\u0441\u043b\u0430\u0431\u043b\u0435\u043d\u0438\u0435 \u0410\u0412\u041b-\u0443\u0441\u043b\u043e\u0432\u0438\u044f \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0434\u0435\u0440\u0435\u0432\u043e \u043f\u0440\u0438 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u0438 \u0437\u0430\u043f\u0438\u0441\u0438 \u043d\u0435 \u0431\u043e\u043b\u0435\u0435 \u0447\u0435\u043c \u0434\u0432\u0443\u043c\u044f \u043f\u043e\u0432\u043e\u0440\u043e\u0442\u0430\u043c\u0438! \u041e\u0446\u0435\u043d\u043a\u0430 \u043d\u0430 \u0432\u044b\u0441\u043e\u0442\u0443 \u0434\u0435\u0440\u0435\u0432\u0430 \u0441\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442 h &lt; min(1,44log<sub>2<\/sub><em>M<\/em>, 2log<sub>2<\/sub><em>N<\/em>), \u0433\u0434\u0435 <em>N<\/em> \u2014 \u0447\u0438\u0441\u043b\u043e \u0437\u0430\u043f\u0438\u0441\u0435\u0439 \u0432 \u0434\u0435\u0440\u0435\u0432\u0435, <em>M<\/em> \u2014 \u0447\u0438\u0441\u043b\u043e \u0432\u0441\u0442\u0430\u0432\u043e\u043a, \u043f\u043e \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044e \u0441 h &lt; 2log<sub>2<\/sub><em>N<\/em> \u0434\u043b\u044f \u043a\u0440\u0430\u0441\u043d\u043e-\u0447\u0451\u0440\u043d\u044b\u0445 \u0434\u0435\u0440\u0435\u0432\u044c\u0435\u0432. \u0411\u043e\u043b\u0435\u0435 \u0442\u043e\u0433\u043e, \u0435\u0441\u043b\u0438 \u0421\u0410\u0412\u041b-\u0434\u0435\u0440\u0435\u0432\u043e \u0441\u0442\u0440\u043e\u0438\u0442\u0441\u044f \u0442\u043e\u043b\u044c\u043a\u043e \u0432\u0441\u0442\u0430\u0432\u043a\u0430\u043c\u0438, \u0442\u043e \u043e\u043d\u043e \u0431\u0443\u0434\u0435\u0442 \u0438\u0434\u0435\u043d\u0442\u0438\u0447\u043d\u043e \u043a\u043b\u0430\u0441\u0441\u0438\u0447\u0435\u0441\u043a\u043e\u043c\u0443 \u0410\u0412\u041b \u0434\u0435\u0440\u0435\u0432\u0443, \u043f\u043e\u043b\u0443\u0447\u0435\u043d\u043d\u043e\u043c\u0443 \u0438\u0437 \u0442\u043e\u0439 \u0436\u0435 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u043a\u043b\u044e\u0447\u0435\u0439.<\/p>\n<p>  <\/p>\n<p>\u041e\u0441\u043b\u0430\u0431\u043b\u0435\u043d\u0438\u0435 \u0410\u0412\u041b-\u0443\u0441\u043b\u043e\u0432\u0438\u044f \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u043f\u0440\u0438 \u043f\u043e\u0432\u043e\u0440\u043e\u0442\u0435 \u0434\u0435\u0440\u0435\u0432\u0430 \u043f\u043e\u0441\u043b\u0435 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044f \u043d\u0435 \u043f\u043e\u043d\u0438\u0436\u0430\u0442\u044c \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 \u0440\u0430\u043d\u0433 \u0443\u0437\u043b\u0430 \u0432 \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u0435, \u0447\u0442\u043e \u043e\u0437\u043d\u0430\u0447\u0430\u0435\u0442 \u043e\u0442\u0441\u0443\u0442\u0441\u0442\u0432\u0438\u0435 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e\u0441\u0442\u0438 \u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u043e\u0432\u043a\u0438 \u0432\u044b\u0448\u0435 \u043f\u043e \u0434\u0435\u0440\u0435\u0432\u0443 \u043f\u043e\u0441\u043b\u0435 \u043f\u043e\u0432\u043e\u0440\u043e\u0442\u0430. \u0418\u043c\u0435\u043d\u043d\u043e \u0438\u0437-\u0437\u0430 \u044d\u0442\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u043e \u043f\u043e\u0432\u043e\u0440\u043e\u0442\u043e\u0432 \u043f\u0440\u0438 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u0438 \u0438 \u0441\u0442\u0430\u043d\u043e\u0432\u0438\u0442\u0441\u044f \u043a\u043e\u043d\u0441\u0442\u0430\u043d\u0442\u043d\u044b\u043c.<\/p>\n<p>  <\/p>\n<h4 id=\"struktura-hraneniya\">\u0421\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u0445\u0440\u0430\u043d\u0435\u043d\u0438\u044f.<\/h4>\n<p>  <\/p>\n<p>\u041c\u043e\u0436\u043d\u043e \u043e\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0443 \u043e\u0431\u044b\u0447\u043d\u043e\u0433\u043e \u0410\u0412\u041b-\u0434\u0435\u0440\u0435\u0432\u0430, \u0442\u043e\u043b\u044c\u043a\u043e &#171;\u0432\u044b\u0441\u043e\u0442\u0430&#187; \u0434\u043e\u043b\u0436\u043d\u0430 \u043f\u043e\u043d\u0438\u043c\u0430\u0442\u044c\u0441\u044f \u043a\u0430\u043a &#171;\u0440\u0430\u043d\u0433&#187;. \u0414\u043b\u044f \u043f\u043e\u043d\u044f\u0442\u043d\u043e\u0441\u0442\u0438, \u0441\u0434\u0435\u043b\u0430\u0435\u043c \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u0443\u044e \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0443:<\/p>\n<p>  <\/p>\n<pre><code class=\"julia\">mutable struct WAVLNode     rank::UInt8      key::K     value::V     left::Union{Nothing, WAVLNode{K,V}}     right::Union{Nothing, WAVLNode{K,V}}     parent::WAVLNode{K,V}     # \u043f\u0443\u0441\u0442\u043e\u0439 \u043a\u043e\u043d\u0441\u0442\u0440\u0443\u043a\u0442\u043e\u0440     function WAVLNode{K,V}() where {K,V}         node = new{K,V}()         node.rank = 1         node.parent = node         node.left = node.right = nothing         return node     end     # \u043a\u043e\u043d\u0441\u0442\u0440\u0443\u043a\u0442\u043e\u0440 \u0441 \u043f\u0430\u0440\u043e\u0439 \u043a\u043b\u044e\u0447-\u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435     function WAVLNode{K,V}(key, value) where {K,V}         key, value = convert(K, key), convert(V, value)         node = new{K,V}()         node.rank = 1         node.parent = node         node.left = node.right = nothing         node.key, node.value = key, value         return node     end end  struct WAVLTree{K, V}     entry::WAVLNode{K,V}     WAVLTree{K,V}() where {K,V} = new{K,V}(WAVLNode{K,V}()) end  function child(root::WAVLNode, side::Signed)     if side == -1         root.left     elseif side == 1         root.right     else         throw(ArgumentError(\"Expecting side=-1 to get the left child or side=1 to get the right child\"))     end end  function Base.getindex(avlt::WAVLTree{K,V}, key) where {K,V}     key = convert(K, key)     node = avlt.entry.left     while node != nothing         key == node.key &amp;&amp; return node.value         node = (key &lt; node.key ? node.left : node.right)     end     throw(KeyError(key)) end<\/code><\/pre>\n<p>  <\/p>\n<h4 id=\"vstavka-zapisi-1\">\u0412\u0441\u0442\u0430\u0432\u043a\u0430 \u0437\u0430\u043f\u0438\u0441\u0438<\/h4>\n<p>  <\/p>\n<p>\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u0440\u0430\u043a\u0442\u0438\u0447\u0435\u0441\u043a\u0438 \u0442\u0430\u043a\u043e\u0439 \u0436\u0435, \u043a\u0430\u043a \u0438 \u0432 \u043e\u0431\u044b\u0447\u043d\u043e\u043c \u0410\u0412\u041b-\u0434\u0435\u0440\u0435\u0432\u0435. \u0415\u0434\u0438\u0441\u0442\u0432\u0435\u043d\u043d\u043e\u0435 \u043e\u0442\u043b\u0438\u0447\u0438\u0435: \u0435\u0441\u043b\u0438 \u0432 \u0431\u0430\u0437\u043e\u0432\u043e\u043c \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u0435 \u0434\u0438\u0441\u0431\u0430\u043b\u0430\u043d\u0441 1 \u043f\u043e\u0441\u043b\u0435 \u0432\u0441\u0442\u0430\u0432\u043a\u0438 \u0433\u0430\u0440\u0430\u043d\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e \u043e\u0437\u043d\u0430\u0447\u0430\u043b, \u0447\u0442\u043e \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u0441\u043a\u0438\u0439 \u0443\u0437\u0435\u043b \u043d\u0443\u0436\u043d\u043e \u043f\u043e\u0434\u043d\u044f\u0442\u044c \u2014 \u0442\u043e \u0432 \u043e\u0441\u043b\u0430\u0431\u043b\u0435\u043d\u043d\u043e\u043c \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u0435 \u043d\u0443\u0436\u043d\u043e \u043f\u0440\u043e\u0432\u0435\u0440\u0438\u0442\u044c, \u0440\u0430\u0437\u043d\u0438\u0446\u0430 \u0432 \u0440\u0430\u043d\u0433\u0430\u0445 \u0443 \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044f \u0441 \u0441\u0430\u043c\u044b\u043c \u0432\u044b\u0441\u043e\u043a\u0438\u043c \u043f\u043e\u0442\u043e\u043c\u043a\u043e\u043c 0 (\u0442\u043e\u0433\u0434\u0430 \u043d\u0443\u0436\u043d\u043e \u043f\u043e\u0434\u043d\u044f\u0442\u044c) \u0438\u043b\u0438 1 (\u0442\u043e\u0433\u0434\u0430 \u0434\u0435\u043b\u0430\u0442\u044c \u043d\u0438\u0447\u0435\u0433\u043e \u043d\u0435 \u043d\u0430\u0434\u043e). \u0414\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u043d\u0435\u043c\u043d\u043e\u0433\u043e \u0438\u0437\u043c\u0435\u043d\u0438\u043c \u0444\u0443\u043d\u043a\u0446\u0438\u044e <code>imbalance()<\/code>, \u0447\u0442\u043e\u0431\u044b \u043e\u043d\u0430 \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u043b\u0430 \u0438 \u0442\u043e, \u0438 \u0434\u0440\u0443\u0433\u043e\u0435.<\/p>\n<p>  <\/p>\n<pre><code class=\"julia\">wavlrank(node::Union{Nothing,WAVLNode}) = node == nothing ? 0 : Int(node.rank)  function imbalance(node::WAVLNode)     rr, lr = wavlrank(node.right), wavlrank(node.left)     skew = rr - lr     diff = node.rank - max(rr, lr)     skew, diff end<\/code><\/pre>\n<p>  <\/p>\n<p>\u041a\u043e\u0434 \u043f\u043e\u0432\u043e\u0440\u043e\u0442\u043e\u0432 \u043d\u0435\u043c\u043d\u043e\u0433\u043e \u043c\u0435\u043d\u044f\u0435\u0442\u0441\u044f, \u0447\u0442\u043e\u0431\u044b \u043d\u0435 \u043f\u0438\u0441\u0430\u0442\u044c \u0440\u0430\u0437\u043d\u044b\u0435 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u0434\u043b\u044f \u043f\u043e\u0432\u043e\u0440\u043e\u0442\u0430 \u043f\u0440\u0438 \u0432\u0441\u0442\u0430\u0432\u043a\u0435 \u0438 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u0438. \u041f\u0440\u0438 \u0432\u0441\u0442\u0430\u0432\u043a\u0435, \u0443\u0447\u0438\u0442\u044b\u0432\u0430\u044f \u043a\u043e\u043d\u0444\u0438\u0433\u0443\u0440\u0430\u0446\u0438\u0438, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0442\u0430\u043c \u043c\u043e\u0433\u0443\u0442 \u0432\u043e\u0437\u043d\u0438\u043a\u0430\u0442\u044c, \u043e\u043d \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u0442\u0430\u043a \u0436\u0435, \u043a\u0430\u043a \u0432 \u043e\u0431\u044b\u0447\u043d\u043e\u043c \u0410\u0412\u041b-\u0434\u0435\u0440\u0435\u0432\u0435, \u0434\u043b\u044f \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044f \u0447\u0443\u0442\u044c-\u0447\u0443\u0442\u044c \u0438\u043d\u0430\u0447\u0435.<\/p>\n<p>  <\/p>\n<div class=\"spoiler\"><b class=\"spoiler_title\">\u041e\u0441\u0442\u0430\u0432\u0448\u0438\u0439\u0441\u044f \u043a\u043e\u0434 \u0434\u043b\u044f \u0432\u0441\u0442\u0430\u0432\u043a\u0438<\/b><\/p>\n<div class=\"spoiler_text\">\n<pre><code class=\"julia\"># pivot \u043e\u043a\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u0432 \u043a\u043e\u043d\u0446\u0435 \u043d\u0430 \u0441\u0430\u043c\u043e\u043c \u0432\u0435\u0440\u0445\u0443 function rotate!(pivot::AVLNode, dir::Signed)     dir in (-1, 1) || throw(ArgumentError(\"Unknown rotation direction\"))     p = pivot.parent     g = p.parent     p.height = avlheight(child(pivot, dir)) + 1     pivot.height = p.height + 1     # \"\u043f\u0435\u0440\u0435\u0446\u0435\u043f\u043b\u044f\u0435\u043c\" pivot \u043a g     pivot.parent = g     g.left === p &amp;&amp; (g.left = pivot)     g.right === p &amp;&amp; (g.right = pivot)     c = child(pivot, dir)     # \u043f\u0435\u0440\u0435\u0446\u0435\u043f\u043b\u044f\u0435\u043c c \u043a p     insert_child!(p, c, -dir)     # \u043f\u0435\u0440\u0435\u0446\u0435\u043f\u043b\u044f\u0435\u043c p \u043a pivot     insert_child!(pivot, p, dir)     pivot end  # pivot \u043e\u043a\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u0432 \u043a\u043e\u043d\u0446\u0435 \u043d\u0430 \u0441\u0430\u043c\u043e\u043c \u0432\u0435\u0440\u0445\u0443 function double_rotate!(pivot::AVLNode, dir::Signed)     dir in (-1, 1) || throw(ArgumentError(\"Unknown rotation direction\"))     n = pivot.parent     p = n.parent     g = p.parent     pivot.height = n.height     n.height = p.height = pivot.height - 1     # \"\u043f\u0435\u0440\u0435\u0446\u0435\u043f\u043b\u044f\u0435\u043c\" pivot \u043a g     pivot.parent = g     g.left === p &amp;&amp; (g.left = pivot)     g.right === p &amp;&amp; (g.right = pivot)     t2, t3 = child(pivot, -dir), child(pivot, dir)     # \u043f\u0435\u0440\u0435\u0446\u0435\u043f\u043b\u044f\u0435\u043c n \u043a pivot \u0438 t2 \u043a n     insert_child!(n, t2, dir)     insert_child!(pivot, n, -dir)     # \u043f\u0435\u0440\u0435\u0446\u0435\u043f\u043b\u044f\u0435\u043c p \u043a pivot \u0438 t3 \u043a p     insert_child!(p, t3, -dir)     insert_child!(pivot, p, dir)     pivot end  imbalance(node::AVLNode) = avlheight(node.right) - avlheight(node.left)  function fix_insertion!(start::AVLNode)     node = start.parent     skew = imbalance(node)     while abs(skew) == 1         node.height += 1         node = node.parent         skew = imbalance(node)     end     @assert abs(skew) == 2 || skew == 0     if skew != 0         dir = -skew \u00f7 2         n = child(node, -dir)         prev_skew = imbalance(n)         @assert abs(prev_skew) == 1         if prev_skew == dir             double_rotate!(child(n, dir), dir)         else             rotate!(n, dir)         end     end end  function Base.setindex!(avlt::AVLTree{K,V}, val, key) where {K,V}     key, value = convert(K, key), convert(V, val)     parent = avlt.entry.left     # \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u044b\u0439 \u0441\u043b\u0443\u0447\u0430\u0439 - \u0432\u0441\u0442\u0430\u0432\u043a\u0430 \u0432 \u043f\u0443\u0441\u0442\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e     if parent == nothing         newnode = AVLNode{K,V}(key, value)         newnode.parent = avlt.entry         avlt.entry.left = avlt.entry.right = newnode         return val     end      key_found = false     while !key_found         key_found = key == parent.key         if key_found             parent.value = value         else             side = (key &gt; parent.key) * 2 - 1             next = child(parent, side)             if next == nothing                 newnode = AVLNode{K,V}(key, value)                 insert_child!(parent, newnode, side)                 fix_insertion!(newnode)                 key_found = true             else                 parent = next             end         end     end     return val end<\/code><\/pre>\n<\/div>\n<\/div>\n<p>  <\/p>\n<h4 id=\"udalenie-zapisi-1\">\u0423\u0434\u0430\u043b\u0435\u043d\u0438\u0435 \u0437\u0430\u043f\u0438\u0441\u0438<\/h4>\n<p>  <\/p>\n<p>\u041f\u043e\u0438\u0441\u043a \u0443\u0437\u043b\u0430 \u0434\u043b\u044f \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044f, \u043f\u043e\u0438\u0441\u043a \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0433\u043e \u0438 \u0437\u0430\u043c\u0435\u043d\u0430 \u2014 \u043f\u043e\u043b\u043d\u043e\u0441\u0442\u044c\u044e \u0438\u0434\u0435\u043d\u0442\u0438\u0447\u043d\u044b \u043e\u0431\u044b\u0447\u043d\u044b\u043c \u0410\u0412\u041b-\u0434\u0435\u0440\u0435\u0432\u044c\u044f\u043c. \u0414\u043b\u044f \u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u043e\u0432\u043a\u0438 \u043f\u0440\u0438 \u043e\u0431\u0440\u0430\u0442\u043d\u043e\u043c \u043f\u0440\u043e\u0445\u043e\u0434\u0435 \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u044e\u0442\u0441\u044f \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0435 \u0441\u043b\u0443\u0447\u0430\u0438.<br \/>  <strong>\u0421\u043b\u0443\u0447\u0430\u0439 0<\/strong><br \/>  \u041d\u0438 \u043e\u0434\u043d\u043e \u0438\u0437 \u0443\u0441\u043b\u043e\u0432\u0438\u0439 \u0431\u0430\u043b\u0430\u043d\u0441\u0430 \u043d\u0435 \u043d\u0430\u0440\u0443\u0448\u0435\u043d\u043e, \u0442.\u0435.:<\/p>\n<p>  <\/p>\n<ol>\n<li>\u0414\u0438\u0441\u0431\u0430\u043b\u0430\u043d\u0441 1, \u0441\u0430\u043c\u043e\u0435 \u0432\u044b\u0441\u043e\u043a\u043e\u0435 \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u043e \u043d\u0430 1 \u043d\u0438\u0436\u0435 \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044f<\/li>\n<li>\u0414\u0438\u0441\u0431\u0430\u043b\u0430\u043d\u0441 0, \u043e\u0431\u0430 \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u0430 \u043d\u0430 2 \u043d\u0438\u0436\u0435 \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044f, \u043f\u0440\u0438 \u044d\u0442\u043e\u043c \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u044c\u044f \u043d\u0435 \u043f\u0443\u0441\u0442\u044b\u0435.<br \/>  \u0411\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u043e\u0432\u043a\u0430 \u043d\u0430 \u044d\u0442\u043e\u043c \u0437\u0430\u0432\u0435\u0440\u0448\u0430\u0435\u0442\u0441\u044f.<\/li>\n<\/ol>\n<p>  <\/p>\n<p><strong>\u0421\u043b\u0443\u0447\u0430\u0439 1<\/strong><br \/>  \u0418\u043c\u0435\u0435\u043c \u043b\u0438\u0441\u0442 \u0441 \u0440\u0430\u043d\u0433\u043e\u043c 2 (\u0434\u0438\u0441\u0431\u0430\u043b\u0430\u043d\u0441 0, \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u044c\u044f \u043d\u0430 2 \u043d\u0438\u0436\u0435 \u0438 \u043f\u0443\u0441\u0442\u044b\u0435).<br \/>  \u041f\u0440\u0438\u0441\u0432\u0430\u0438\u0432\u0430\u0435\u043c \u0443\u0437\u043b\u0443 \u0440\u0430\u043d\u0433 1 \u0438 \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u0438\u043c \u0432\u044b\u0448\u0435.<\/p>\n<p>  <\/p>\n<p><strong>\u0421\u043b\u0443\u0447\u0430\u0439 2<\/strong><br \/>  \u0414\u0438\u0441\u0431\u0430\u043b\u0430\u043d\u0441 1, \u0440\u0430\u0437\u043d\u0438\u0446\u0430 \u0441 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u043c \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u043e\u043c 2.<br \/>  <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/q0\/gq\/3h\/q0gq3hi6g7k8modechdmavys-to.png\"><br \/>  \u0423\u043c\u0435\u043d\u044c\u0448\u0430\u0435\u043c \u0443 \u0443\u0437\u043b\u0430 \u0440\u0430\u043d\u0433 \u043d\u0430 1, \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u0438\u043c \u0432\u044b\u0448\u0435.<br \/>  <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/28\/ss\/oc\/28ssoc1ki3flzroiinnigcsguhg.png\"><\/p>\n<p>  <\/p>\n<p><strong>\u0421\u043b\u0443\u0447\u0430\u0439 3<\/strong><br \/>  \u0414\u0438\u0441\u0431\u0430\u043b\u0430\u043d\u0441 2 (\u0440\u0430\u0437\u043d\u0438\u0446\u0430 \u0441 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u043c \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u043e\u043c \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u0438 1, \u0442.\u043a. \u0438\u043d\u0430\u0447\u0435 \u0441\u043b\u0430\u0431\u043e\u0435 \u0410\u0412\u041b \u0443\u0441\u043b\u043e\u0432\u0438\u0435 \u0431\u044b\u043b\u043e \u0431\u044b \u043d\u0430\u0440\u0443\u0448\u0435\u043d\u043e \u0435\u0449\u0451 \u0434\u043e \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044f), \u0443 \u0431\u043e\u043b\u0435\u0435 \u0432\u044b\u0441\u043e\u043a\u043e\u0433\u043e \u043f\u043e\u0442\u043e\u043c\u043a\u0430 \u043e\u0431\u0430 \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u0430 \u0440\u0430\u043d\u0433\u043e\u043c \u043d\u0430 2 \u043d\u0438\u0436\u0435 \u0435\u0433\u043e.<br \/>  <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/oi\/tl\/qd\/oitlqdhhc83lttdsw6s0az_kr5y.png\"><br \/>  \u0421\u043f\u0443\u0441\u043a\u0430\u0435\u043c \u043d\u0430 \u0440\u0430\u043d\u0433 \u043d\u0438\u0436\u0435 \u0438 \u0441\u0430\u043c \u0443\u0437\u0435\u043b, \u0438 \u0431\u043e\u043b\u0435\u0435 \u0432\u044b\u0441\u043e\u043a\u043e\u0433\u043e \u043f\u043e\u0442\u043e\u043c\u043a\u0430. \u041f\u0435\u0440\u0435\u0445\u043e\u0434\u0438\u043c \u0432\u044b\u0448\u0435.<br \/>  <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/st\/pn\/se\/stpnsenr-ygtamabscwra_yd2dy.png\"><\/p>\n<p>  <\/p>\n<p><strong>\u0421\u043b\u0443\u0447\u0430\u0439 4<\/strong><br \/>  <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/fp\/l-\/h1\/fpl-h1yg-9gl3wrucoiq-lhefwq.png\"><br \/>  \u041b\u0435\u0447\u0438\u0442\u0441\u044f \u043f\u0440\u043e\u0441\u0442\u044b\u043c \u043f\u043e\u0432\u043e\u0440\u043e\u0442\u043e\u043c.<br \/>  <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/s3\/qy\/0u\/s3qy0uwfz87t5uroqynp4rvchwi.png\"><br \/>  \u041e\u0431\u0440\u0430\u0442\u0438\u0442\u0435 \u0432\u043d\u0438\u043c\u0430\u043d\u0438\u0435, \u0447\u0442\u043e \u0437\u0430 \u0441\u0447\u0451\u0442 \u043e\u0441\u043b\u0430\u0431\u043b\u0435\u043d\u043d\u043e\u0433\u043e \u0410\u0412\u041b \u0443\u0441\u043b\u043e\u0432\u0438\u044f \u043f\u043e\u0432\u043e\u0440\u043e\u0442 \u043c\u043e\u0436\u043d\u043e \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u0442\u0430\u043a, \u0447\u0442\u043e \u0432\u0441\u0451 \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u043e \u043d\u0435 \u043c\u0435\u043d\u044f\u0435\u0442 \u0432\u044b\u0441\u043e\u0442\u0443, \u0442.\u0435. \u0432\u044b\u0448\u0435 \u043f\u043e \u0434\u0435\u0440\u0435\u0432\u0443 \u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u043e\u0432\u043a\u0430 \u043d\u0435 \u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f.<br \/>  \u0415\u0434\u0438\u043d\u0441\u0442\u0432\u0435\u043d\u043d\u0430\u044f \u0442\u043e\u043d\u043a\u043e\u0441\u0442\u044c \u2014 \u0435\u0441\u043b\u0438 \u0434\u0435\u0440\u0435\u0432\u044c\u044f T<sub>1<\/sub> \u0438 T<sub>2<\/sub> \u043e\u0431\u0430 \u043f\u0443\u0441\u0442\u044b\u0435, \u0442\u043e <em>p<\/em> \u0441\u0442\u0430\u043d\u043e\u0432\u0438\u0442\u0441\u044f \u043b\u0438\u0441\u0442\u043e\u043c \u0441 \u0440\u0430\u043d\u0433\u043e\u043c 2, \u0447\u0442\u043e \u043b\u0435\u0447\u0438\u0442\u0441\u044f \u043f\u0440\u0438\u0441\u0432\u0430\u0438\u0432\u0430\u043d\u0438\u0435\u043c <em>p<\/em> \u0432 \u044d\u0442\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u0440\u0430\u043d\u0433\u0430 1.<\/p>\n<p>  <\/p>\n<p><strong>\u0421\u043b\u0443\u0447\u0430\u0439 5<\/strong><br \/>  <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/5m\/pn\/sb\/5mpnsb8edlrtcazgox852h6rrsm.png\"><br \/>  \u041b\u0435\u0447\u0438\u0442\u0441\u044f \u0434\u0432\u043e\u0439\u043d\u044b\u043c \u043f\u043e\u0432\u043e\u0440\u043e\u0442\u043e\u043c.<br \/>  <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/im\/vt\/7c\/imvt7cnylf5_dja5jc6xx9km-xo.png\"><br \/>  \u0410\u043d\u0430\u043b\u043e\u0433\u0438\u0447\u043d\u043e, \u0432\u044b\u0441\u043e\u0442\u0430 \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u0430 \u043d\u0435 \u043c\u0435\u043d\u044f\u0435\u0442\u0441\u044f, \u0438 \u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u043e\u0432\u043a\u0443 \u043c\u043e\u0436\u043d\u043e \u043d\u0430 \u044d\u0442\u043e\u043c \u0437\u0430\u043a\u0430\u043d\u0447\u0438\u0432\u0430\u0442\u044c.<\/p>\n<p>  <\/p>\n<div class=\"spoiler\"><b class=\"spoiler_title\">\u041a\u043e\u0434 \u0434\u043b\u044f \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044f \u0437\u0430\u043f\u0438\u0441\u0438<\/b><\/p>\n<div class=\"spoiler_text\">\n<pre><code class=\"julia\">function next_node(node::WAVLNode)     next = node.right     if next == nothing         p = node.parent         next = p.parent         while (next !== p) &amp;&amp; (next.key &lt; p.key)             p, next = next, next.parent         end         return (next === p ? nothing : next)     else         while next.left != nothing             next = next.left         end         return next     end  end  function Base.delete!(avlt::WAVLTree{K,V}, key) where {K,V}     key = convert(K, key)     candidate = avlt.entry.left     dir = 0     while candidate.key != key         dir = 2 * (key &gt; candidate.key) - 1         candidate = child(candidate, dir)         candidate == nothing &amp;&amp; return     end     val = candidate.value     for side in (-1, 1)         if child(candidate, side) == nothing             p, s = candidate.parent, child(candidate, -side)             if p === p.parent                 insert_child!(p, s, 1)                 insert_child!(p, s, -1)             else                 insert_child!(p, s, dir)                 fix_deletion!(p)             end             return         end     end     swap = next_node(candidate)     cp, sp, sr = candidate.parent, swap.parent, swap.right     swap.height = candidate.height     insert_child!(swap, candidate.left, -1)     for side in (-1, 1)         child(cp, side) === candidate &amp;&amp; insert_child!(cp, swap, side)     end     if sp === candidate         fix_deletion!(swap)     else         insert_child!(swap, candidate.right, 1)         insert_child!(sp, sr, -1)         fix_deletion!(sp)     end     return end  function fix_deletion!(start::WAVLNode)     node = start     skew, diff = imbalance(node)     while (node !== node.parent)         if skew == 0             if node.right == nothing                 node.rank = 1             else                 break             end         elseif abs(skew) == 1             if diff == 1                 break             else                 node.rank -= 1             end         else             dir = -skew \u00f7 2             n = child(node, -dir)             prev_skew, prev_diff = imbalance(n)             if prev_diff == 2                 @assert prev_skew == 0                 n.rank -= 1                 node.rank -= 1             elseif prev_skew == dir                 double_rotate!(child(n, dir), dir)                 break             else                 rotate!(n, dir)                 break             end         end         node = node.parent         skew, diff = imbalance(node)     end end<\/code><\/pre>\n<\/div>\n<\/div>\n<p>  <\/p>\n<p>\u041f\u0440\u043e\u0432\u0435\u0440\u0438\u043c \u0432 \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0438 \u0441\u043e \u0432\u0441\u0442\u0440\u043e\u0435\u043d\u043d\u044b\u043c\u0438 \u0445\u044d\u0448-\u0442\u0430\u0431\u043b\u0438\u0446\u0430\u043c\u0438.<\/p>\n<p>  <\/p>\n<pre><code class=\"julia\">julia&gt; const wavl = WAVLTree{Int, Int}() julia&gt; const avl = AVLTree{Int, Int}() julia&gt; const dd = Dict{Int,Int}() julia&gt; x = trues(1_000_000) # \u0437\u0430\u043f\u043e\u043b\u043d\u0438\u043c \u0447\u0438\u0441\u043b\u0430\u043c\u0438 \u0438 \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u044b\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c \u0443\u0434\u0430\u043b\u0438\u043c ~ \u043f\u043e\u043b\u043e\u0432\u0438\u043d\u0443 julia&gt; for i = 1:1_000_000; dd[i] = avl[i] = wavl[i] = i * i; end julia&gt; for i=1:500_000        k = rand(1:1_000_000)        x[k] = false        delete!(avl, k)        delete!(wavl, k)        delete!(dd, k)        end  # \u0437\u0430\u043f\u043e\u043c\u043d\u0438\u043b\u0438, \u043a\u0430\u043a\u0438\u0435 \u043a\u043b\u044e\u0447\u0438 \u043d\u0435 \u0443\u0434\u0430\u043b\u044f\u043b\u0438\u0441\u044c julia&gt; const y = Int[] julia&gt; for i in eachindex(x); if x[i] push!(y, i); end; end  julia&gt; @btime let s = 0.0; for idx in y; s += dd[idx]; end; s; end   57.626 ms (0 allocations: 0 bytes) 2.0238199367708794e17 julia&gt; @btime let s = 0.0; for idx in y; s += wavl[idx]; end; s; end   57.796 ms (0 allocations: 0 bytes) 2.0238199367708794e17 julia&gt; @btime let s = 0.0; for idx in y; s += avl[idx]; end; s; end   53.884 ms (0 allocations: 0 bytes) 2.0238199367708794e17<\/code><\/pre>\n<p>  <\/p>\n<p>\u0418\u0442\u0430\u043a, \u0441\u043a\u043e\u0440\u043e\u0441\u0442\u044c \u043f\u043e\u0438\u0441\u043a\u0430 \u043f\u043e \u043a\u043b\u044e\u0447\u0443 \u0432\u044b\u0448\u043b\u0430 \u043f\u0440\u0438\u043c\u0435\u0440\u043d\u043e \u0442\u0430\u043a\u0430\u044f \u0436\u0435, \u043a\u0430\u043a \u0432\u043e \u0432\u0441\u0442\u0440\u043e\u0435\u043d\u043d\u044b\u0445 \u0441\u043b\u043e\u0432\u0430\u0440\u044f\u0445. \u0418, \u043e\u0436\u0438\u0434\u0430\u0435\u043c\u043e, \u0432 \u043a\u043b\u0430\u0441\u0441\u0438\u0447\u0435\u0441\u043a\u043e\u043c \u0410\u0412\u041b-\u0434\u0435\u0440\u0435\u0432\u0435 \u0441\u043a\u043e\u0440\u043e\u0441\u0442\u044c \u043f\u043e\u0438\u0441\u043a\u0430 \u0447\u0443\u0442\u044c \u0432\u044b\u0448\u0435, \u0447\u0435\u043c \u0432 \u0421\u0410\u0412\u041b-\u0434\u0435\u0440\u0435\u0432\u0435, \u0437\u0430 \u0441\u0447\u0451\u0442 \u043b\u0443\u0447\u0448\u0435\u0439 \u0441\u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0441\u0442\u0438.<\/p>\n<p>  <\/p>\n<h3 id=\"primenenie-derevev-poiska\">\u041f\u0440\u0438\u043c\u0435\u043d\u0435\u043d\u0438\u0435 \u0434\u0435\u0440\u0435\u0432\u044c\u0435\u0432 \u043f\u043e\u0438\u0441\u043a\u0430<\/h3>\n<p>  <\/p>\n<p>\u0418 \u043e\u0441\u043d\u043e\u0432\u043d\u043e\u0439 \u0432\u043e\u043f\u0440\u043e\u0441 \u2014 \u0437\u0430\u0447\u0435\u043c \u044d\u0442\u043e \u043d\u0443\u0436\u043d\u043e?<br \/>  \u041f\u0440\u043e\u0441\u0442\u0435\u0439\u0448\u0438\u0439 \u043e\u0442\u0432\u0435\u0442 \u2014 \u0434\u0435\u0440\u0435\u0432\u044c\u044f \u043f\u043e\u0438\u0441\u043a\u0430 \u043d\u0443\u0436\u043d\u044b, \u0447\u0442\u043e\u0431\u044b \u0438\u0441\u043a\u0430\u0442\u044c \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u044e. \u041d\u043e, \u043d\u0430 \u0441\u0430\u043c\u043e\u043c \u0434\u0435\u043b\u0435, \u043d\u0435 \u0442\u043e\u043b\u044c\u043a\u043e.<br \/>  \u041d\u0430 \u043e\u0441\u043d\u043e\u0432\u0435 \u0434\u0432\u043e\u0438\u0447\u043d\u044b\u0445 \u0434\u0435\u0440\u0435\u0432\u044c\u0435\u0432 \u043f\u043e\u0438\u0441\u043a\u0430 \u043c\u043e\u0436\u043d\u043e \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u0442\u044c \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u0435 \u0430\u0431\u0441\u0442\u0440\u0430\u043a\u0442\u043d\u044b\u0435 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0434\u0430\u043d\u043d\u044b\u0445.<\/p>\n<p>  <\/p>\n<h4 id=\"uporyadochennoe-mnozhestvo\">\u0423\u043f\u043e\u0440\u044f\u0434\u043e\u0447\u0435\u043d\u043d\u043e\u0435 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e<\/h4>\n<p>  <\/p>\n<p>\u0417\u0430\u0434\u0430\u0447\u0430 \u0443\u043f\u043e\u0440\u044f\u0434\u043e\u0447\u0435\u043d\u043d\u043e\u0433\u043e \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430 \u2014 \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0442\u0430\u043a, \u0447\u0442\u043e\u0431\u044b \u043a \u043d\u0438\u043c \u043c\u043e\u0436\u043d\u043e \u0431\u044b\u043b\u043e \u0434\u043e\u0441\u0442\u0443\u043f\u0430\u0442\u044c\u0441\u044f \u0432 \u043f\u043e\u0440\u044f\u0434\u043a\u0435 \u0432\u043e\u0437\u0440\u0430\u0441\u0442\u0430\u043d\u0438\u044f \u0438\u043b\u0438 \u0443\u0431\u044b\u0432\u0430\u043d\u0438\u044f. \u0422\u0430\u043a\u0436\u0435 \u043c\u043e\u0436\u043d\u043e \u0432\u0432\u0435\u0441\u0442\u0438 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044e \u043f\u043e\u0438\u0441\u043a\u0430 <em>n<\/em>-\u0433\u043e \u043f\u043e \u0432\u0435\u043b\u0438\u0447\u0438\u043d\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430. \u0415\u0441\u0442\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u043e, \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0443 \u0434\u0430\u043d\u043d\u044b\u0445 \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0435\u043c \u043a\u0430\u043a \u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u0443\u044e, \u0442.\u0435. \u043a\u0440\u043e\u043c\u0435 \u043f\u0435\u0440\u0435\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f, \u043c\u044b \u0445\u043e\u0442\u0438\u043c \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0442\u044c \u0438\u043b\u0438 \u0443\u0434\u0430\u043b\u044f\u0442\u044c \u043e\u0442\u0442\u0443\u0434\u0430 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b.<\/p>\n<p>  <\/p>\n<div class=\"scrollable-table\">\n<table>\n<thead>\n<tr>\n<th>\u041e\u043f\u0435\u0440\u0430\u0446\u0438\u044f<\/th>\n<th>\u0410\u0412\u041b \u0434\u0435\u0440\u0435\u0432\u043e<\/th>\n<th>\u0421\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0439 \u043c\u0430\u0441\u0441\u0438\u0432<\/th>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<td>\u041f\u0435\u0440\u0435\u0447\u0438\u0441\u043b\u0438\u0442\u044c \u0432\u0441\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b<\/td>\n<td><em>O<\/em>(<em>N<\/em>)<\/td>\n<td><em>O<\/em>(<em>N<\/em>)<\/td>\n<\/tr>\n<tr>\n<td>\u0412\u0441\u0442\u0430\u0432\u043a\u0430<\/td>\n<td><em>O<\/em>(log<em>N<\/em>)<\/td>\n<td><em>O<\/em>(<em>N<\/em>)<\/td>\n<\/tr>\n<tr>\n<td>\u0423\u0434\u0430\u043b\u0435\u043d\u0438\u0435<\/td>\n<td><em>O<\/em>(log<em>N<\/em>)<\/td>\n<td><em>O<\/em>(<em>N<\/em>)<\/td>\n<\/tr>\n<tr>\n<td><em>n<\/em>-\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442<\/td>\n<td><em>O<\/em>(log<em>N<\/em>)*<\/td>\n<td><em>O<\/em>(1)<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n<p>  <\/p>\n<p>* \u0435\u0441\u043b\u0438 \u0432 \u0443\u0437\u043b\u0430\u0445 \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u044e \u043e \u0440\u0430\u0437\u043c\u0435\u0440\u0435 \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u0430<\/p>\n<p>  <\/p>\n<h4 id=\"associativnyy-massiv\">\u0410\u0441\u0441\u043e\u0446\u0438\u0430\u0442\u0438\u0432\u043d\u044b\u0439 \u043c\u0430\u0441\u0441\u0438\u0432<\/h4>\n<p>  <\/p>\n<p>\u0410\u0441\u0441\u043e\u0446\u0438\u0430\u0442\u0438\u0432\u043d\u044b\u0439 \u043c\u0430\u0441\u0441\u0438\u0432 \u2014 \u0430\u0431\u0441\u0442\u0440\u0430\u043a\u0442\u043d\u0430\u044f \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u0434\u0430\u043d\u043d\u044b\u0445, \u0434\u043b\u044f \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u043e\u0441\u043d\u043e\u0432\u043d\u044b\u043c\u0438 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044f\u043c\u0438 \u044f\u0432\u043b\u044f\u044e\u0442\u0441\u044f &#171;\u043d\u0430\u0439\u0442\u0438 \u0437\u0430\u043f\u0438\u0441\u044c \u043f\u043e \u043a\u043b\u044e\u0447\u0443&#187;, &#171;\u043f\u0440\u043e\u0432\u0435\u0440\u0438\u0442\u044c \u043d\u0430\u043b\u0438\u0447\u0438\u0435 \u043a\u043b\u044e\u0447\u0430 \u0432 \u043c\u0430\u0441\u0441\u0438\u0432\u0435&#187;, &#171;\u0434\u043e\u0431\u0430\u0432\u0438\u0442\u044c \u043f\u0430\u0440\u0443 \u043a\u043b\u044e\u0447-\u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435&#187;, &#171;\u0443\u0434\u0430\u043b\u0438\u0442\u044c \u0437\u0430\u043f\u0438\u0441\u044c&#187;. \u0412\u043e \u043c\u043d\u043e\u0433\u0438\u0445 \u044f\u0437\u044b\u043a\u0430\u0445 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f, \u0433\u0434\u0435 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u0432\u043a\u043b\u044e\u0447\u0435\u043d\u0430 \u0432 \u0441\u0442\u0430\u043d\u0434\u0430\u0440\u0442\u043d\u0443\u044e \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0443, \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u0441\u0434\u0435\u043b\u0430\u043d\u0430 \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u0434\u0432\u043e\u0438\u0447\u043d\u044b\u0445 \u0434\u0435\u0440\u0435\u0432\u044c\u0435\u0432 \u0438\u043b\u0438 \u0445\u044d\u0448-\u0442\u0430\u0431\u043b\u0438\u0446. \u042f\u0437\u044b\u043a\u0438 \u0441\u0435\u043c\u0435\u0439\u0441\u0442\u0432\u0430 \u041b\u0438\u0441\u043f \u043f\u043e\u0434\u0434\u0435\u0440\u0436\u0438\u0432\u0430\u044e\u0442 \u0430\u0441\u0441\u043e\u0446\u0438\u0430\u0442\u0438\u0432\u043d\u044b\u0435 \u0441\u043f\u0438\u0441\u043a\u0438. \u0412 \u043a\u043e\u043d\u0446\u0435 \u043a\u043e\u043d\u0446\u043e\u0432, \u0437\u0430\u043f\u0438\u0441\u0438 \u043c\u043e\u0436\u043d\u043e \u0434\u0430\u0436\u0435 \u043f\u0440\u043e\u0441\u0442\u043e \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u0432 \u043c\u0430\u0441\u0441\u0438\u0432\u0435 \u0432 \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u043c \u043f\u043e\u0440\u044f\u0434\u043a\u0435.<\/p>\n<p>  <\/p>\n<div class=\"scrollable-table\">\n<table>\n<thead>\n<tr>\n<th>\u041e\u043f\u0435\u0440\u0430\u0446\u0438\u044f<\/th>\n<th>\u0410\u0412\u041b \u0434\u0435\u0440\u0435\u0432\u043e<\/th>\n<th>\u0445\u044d\u0448-\u0442\u0430\u0431\u043b\u0438\u0446\u0430<\/th>\n<th>\u0421\u043f\u0438\u0441\u043e\u043a<\/th>\n<th>\u0421\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0439 \u043c\u0430\u0441\u0441\u0438\u0432<\/th>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<td>\u041f\u043e\u0438\u0441\u043a<\/td>\n<td><em>O<\/em>(log<em>N<\/em>)<\/td>\n<td><em>O<\/em>(1)*<\/td>\n<td><em>O<\/em>(<em>N<\/em>)<\/td>\n<td><em>O<\/em>(log<em>N<\/em>)<\/td>\n<\/tr>\n<tr>\n<td>\u0412\u0441\u0442\u0430\u0432\u043a\u0430<\/td>\n<td><em>O<\/em>(log<em>N<\/em>)<\/td>\n<td><em>O<\/em>(1)*<\/td>\n<td><em>O<\/em>(1)<\/td>\n<td><em>O<\/em>(<em>N<\/em>)<\/td>\n<\/tr>\n<tr>\n<td>\u0423\u0434\u0430\u043b\u0435\u043d\u0438\u0435<\/td>\n<td><em>O<\/em>(log<em>N<\/em>)<\/td>\n<td><em>O<\/em>(1)*<\/td>\n<td><em>O<\/em>(<em>N<\/em>)**<\/td>\n<td><em>O<\/em>(<em>N<\/em>)<\/td>\n<\/tr>\n<tr>\n<td>\u041f\u043e\u0438\u0441\u043a \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0435\u0433\u043e \u043a\u043b\u044e\u0447\u0430<\/td>\n<td><em>O<\/em>(log<em>N<\/em>)<\/td>\n<td><em>O<\/em>(<em>N<\/em>)<\/td>\n<td><em>O<\/em>(<em>N<\/em>)<\/td>\n<td><em>O<\/em>(log<em>N<\/em>)<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n<p>  <\/p>\n<p>* \u0430\u043c\u043e\u0440\u0442\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u0430\u044f \u0441\u0442\u043e\u0438\u043c\u043e\u0441\u0442\u044c \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438<br \/>  ** \u0441\u0430\u043c\u043e \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u0435 \u0434\u0435\u043b\u0430\u0435\u0442\u0441\u044f \u0437\u0430 <em>O<\/em>(1), \u043d\u043e \u043a\u043b\u044e\u0447 \u0435\u0449\u0451 \u043d\u0443\u0436\u043d\u043e \u043d\u0430\u0439\u0442\u0438&#8230;<\/p>\n<p>  <\/p>\n<h4 id=\"ochered-s-prioritetami\">\u041e\u0447\u0435\u0440\u0435\u0434\u044c \u0441 \u043f\u0440\u0438\u043e\u0440\u0438\u0442\u0435\u0442\u0430\u043c\u0438<\/h4>\n<p>  <\/p>\n<p>\u042d\u0442\u043e \u0442\u0430\u043a\u0430\u044f \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u0434\u0430\u043d\u043d\u044b\u0445, \u0433\u0434\u0435 \u0445\u0440\u0430\u043d\u044f\u0442\u0441\u044f \u0437\u0430\u043f\u0438\u0441\u0438 \u0432 \u0432\u0438\u0434\u0435 \u043f\u0430\u0440 &#171;\u043f\u0440\u0438\u043e\u0440\u0438\u0442\u0435\u0442 \u2014 \u0434\u0430\u043d\u043d\u044b\u0435&#187;. \u0418\u0437\u0432\u043b\u0435\u043a\u0430\u044e\u0442\u0441\u044f \u0437\u0430\u043f\u0438\u0441\u0438 \u043d\u0435 \u0432 \u043f\u043e\u0440\u044f\u0434\u043a\u0435 \u043f\u043e\u0441\u0442\u0443\u043f\u043b\u0435\u043d\u0438\u044f, \u0430 \u0432 \u043f\u043e\u0440\u044f\u0434\u043a\u0435 \u043f\u0440\u0438\u043e\u0440\u0438\u0442\u0435\u0442\u0430. \u041e\u0441\u043d\u043e\u0432\u043d\u044b\u0435 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u2014 \u043f\u043e\u0441\u043c\u043e\u0442\u0440\u0435\u0442\u044c \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0441 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u043c (\u0438\u043b\u0438 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u043c) \u043f\u0440\u0438\u043e\u0440\u0438\u0442\u0435\u0442\u043e\u043c, \u0443\u0434\u0430\u043b\u0438\u0442\u044c \u0438\u0437 \u043e\u0447\u0435\u0440\u0435\u0434\u0438 \u0437\u0430\u043f\u0438\u0441\u044c \u0441\u043e \u0441\u0442\u0430\u0440\u0448\u0438\u043c \u043f\u0440\u0438\u043e\u0440\u0438\u0442\u0435\u0442\u043e\u043c, \u0434\u043e\u0431\u0430\u0432\u0438\u0442\u044c \u0437\u0430\u043f\u0438\u0441\u044c, \u0438\u0437\u043c\u0435\u043d\u0438\u0442\u044c \u043f\u0440\u0438\u043e\u0440\u0438\u0442\u0435\u0442 \u0437\u0430\u043f\u0438\u0441\u0438. \u0427\u0430\u0441\u0442\u043e \u0442\u0430\u043a\u0438\u0435 \u043e\u0447\u0435\u0440\u0435\u0434\u0438 \u0440\u0435\u0430\u043b\u0438\u0437\u0443\u044e\u0442\u0441\u044f \u043f\u0440\u0438 \u043f\u043e\u043c\u043e\u0449\u0438 <a href=\"https:\/\/habr.com\/ru\/post\/112222\/\">\u0434\u0432\u043e\u0438\u0447\u043d\u043e\u0439 \u043a\u0443\u0447\u0438<\/a>.<\/p>\n<p>  <\/p>\n<div class=\"scrollable-table\">\n<table>\n<thead>\n<tr>\n<th>\u041e\u043f\u0435\u0440\u0430\u0446\u0438\u044f<\/th>\n<th>\u0410\u0412\u041b \u0434\u0435\u0440\u0435\u0432\u043e<\/th>\n<th>\u0414\u0432\u043e\u0438\u0447\u043d\u0430\u044f \u043a\u0443\u0447\u0430<\/th>\n<th>\u0421\u043f\u0438\u0441\u043e\u043a<\/th>\n<th>\u0421\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0439 \u0441\u043f\u0438\u0441\u043e\u043a\/\u043c\u0430\u0441\u0441\u0438\u0432<\/th>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<td>\u041f\u043e\u0441\u043c\u043e\u0442\u0440\u0435\u0442\u044c \u043c\u0430\u043a\u0441\u0438\u043c\u0443\u043c<\/td>\n<td><em>O<\/em>(1)*<\/td>\n<td><em>O<\/em>(1)<\/td>\n<td><em>O<\/em>(<em>N<\/em>)<\/td>\n<td><em>O<\/em>(1)<\/td>\n<\/tr>\n<tr>\n<td>\u0423\u0434\u0430\u043b\u0438\u0442\u044c \u043c\u0430\u043a\u0441\u0438\u043c\u0443\u043c<\/td>\n<td><em>O<\/em>(log<em>N<\/em>)<\/td>\n<td><em>O<\/em>(log<em>N<\/em>)<\/td>\n<td><em>O<\/em>(<em>N<\/em>)<\/td>\n<td><em>O<\/em>(1)**<\/td>\n<\/tr>\n<tr>\n<td>\u0414\u043e\u0431\u0430\u0432\u0438\u0442\u044c \u0437\u0430\u043f\u0438\u0441\u044c<\/td>\n<td><em>O<\/em>(log<em>N<\/em>)<\/td>\n<td><em>O<\/em>(log<em>N<\/em>)<\/td>\n<td><em>O<\/em>(1)<\/td>\n<td><em>O<\/em>(<em>N<\/em>)<\/td>\n<\/tr>\n<tr>\n<td>\u0418\u0437\u043c\u0435\u043d\u0438\u0442\u044c \u043f\u0440\u0438\u043e\u0440\u0438\u0442\u0435\u0442<\/td>\n<td><em>O<\/em>(log<em>N<\/em>)<\/td>\n<td><em>O<\/em>(log<em>N<\/em>)<\/td>\n<td><em>O<\/em>(<em>N<\/em>)<\/td>\n<td><em>O<\/em>(<em>N<\/em>)<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n<p>  <\/p>\n<p>* \u0435\u0441\u043b\u0438 \u0434\u043e\u0431\u0430\u0432\u0438\u0442\u044c \u0432 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0443 \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c \u043d\u0430 \u043c\u0430\u043a\u0441\u0438\u043c\u0443\u043c<br \/>  ** \u0435\u0441\u043b\u0438 \u0441\u0447\u0438\u0442\u0430\u0442\u044c, \u0447\u0442\u043e \u043c\u0430\u043a\u0441\u0438\u043c\u0443\u043c \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u0441\u044f \u0432 \u043a\u043e\u043d\u0446\u0435 \u043c\u0430\u0441\u0441\u0438\u0432\u0430<\/p>\n<p>  <\/p>\n<h3 id=\"vyvod\">\u0412\u044b\u0432\u043e\u0434<\/h3>\n<p>  <\/p>\n<p>(\u0441\u0430\u043c\u043e\u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u0443\u044e\u0449\u0438\u0435\u0441\u044f) \u0414\u0432\u043e\u0438\u0447\u043d\u044b\u0435 \u0434\u0435\u0440\u0435\u0432\u044c\u044f \u043f\u043e\u0438\u0441\u043a\u0430 \u2014 \u043d\u0435\u043f\u043b\u043e\u0445\u0430\u044f \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u0434\u0430\u043d\u043d\u044b\u0445 \u0434\u043b\u044f \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u0430\u0441\u0441\u043e\u0446\u0438\u0430\u0442\u0438\u0432\u043d\u044b\u0445 \u043c\u0430\u0441\u0441\u0438\u0432\u043e\u0432, \u043e\u0447\u0435\u0440\u0435\u0434\u0435\u0439 \u0441 \u043f\u0440\u0438\u043e\u0440\u0438\u0442\u0435\u0442\u0430\u043c\u0438, \u0438, \u0432 \u043f\u0435\u0440\u0432\u0443\u044e \u043e\u0447\u0435\u0440\u0435\u0434\u044c, \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432, \u0433\u0434\u0435 \u0432\u0430\u0436\u043d\u043e \u0443\u043f\u043e\u0440\u044f\u0434\u043e\u0447\u0435\u043d\u0438\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432. \u0413\u043b\u0430\u0432\u043d\u0430\u044f \u0441\u0438\u043b\u044c\u043d\u0430\u044f \u0447\u0435\u0440\u0442\u0430 \u0434\u0435\u0440\u0435\u0432\u044c\u0435\u0432 \u043f\u043e\u0438\u0441\u043a\u0430 \u2014 \u0433\u0438\u0431\u043a\u043e\u0441\u0442\u044c \u0432 \u043f\u043b\u0430\u043d\u0435 \u043e\u0431\u043b\u0430\u0441\u0442\u0438 \u043f\u0440\u0438\u043c\u0435\u043d\u0435\u043d\u0438\u044f, \u0442.\u043a. \u043d\u0435\u043b\u044c\u0437\u044f \u0441\u043a\u0430\u0437\u0430\u0442\u044c, \u0447\u0442\u043e \u0434\u043b\u044f \u043b\u044e\u0431\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0438 \u0434\u0435\u0440\u0435\u0432\u044c\u044f \u043f\u043e\u0438\u0441\u043a\u0430 \u043e\u0431\u0435\u0441\u043f\u0435\u0447\u0430\u0442 \u043b\u0443\u0447\u0448\u0443\u044e \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c, \u0447\u0435\u043c \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.<\/p>\n<p>  <\/p>\n<h2 id=\"ssylki\">\u0421\u0441\u044b\u043b\u043a\u0438<\/h2>\n<p>  <\/p>\n<ol>\n<li><a href=\"https:\/\/habr.com\/ru\/post\/150732\/\">&#171;\u0410\u0412\u041b-\u0434\u0435\u0440\u0435\u0432\u044c\u044f&#187;<\/a> \u043e\u0442 <a href=\"https:\/\/habr.com\/ru\/users\/nickme\/\" class=\"user_link\">nickme<\/a> <\/li>\n<li>Rank-Balanced Trees by Bernhard Haeupler, Siddhartha Sen, Robert E. Tarjan \/\/ ACM Transactions on Algorithms | June 2015, Vol 11(4) <a href=\"http:\/\/sidsen.org\/papers\/rb-trees-talg.pdf\">pdf<\/a><\/li>\n<li>Goodrich M.T., Tamassia R. Algorithm Design and Applications<\/li>\n<\/ol>\n<\/div>\n<p>               <script class=\"js-mediator-script\">!function(e){function t(t,n){if(!(n in e)){for(var r,a=e.document,i=a.scripts,o=i.length;o--;)if(-1!==i[o].src.indexOf(t)){r=i[o];break}if(!r){r=a.createElement(\"script\"),r.type=\"text\/javascript\",r.async=!0,r.defer=!0,r.src=t,r.charset=\"UTF-8\";var d=function(){var e=a.getElementsByTagName(\"script\")[0];e.parentNode.insertBefore(r,e)};\"[object Opera]\"==e.opera?a.addEventListener?a.addEventListener(\"DOMContentLoaded\",d,!1):e.attachEvent(\"onload\",d):d()}}}t(\"\/\/mediator.mail.ru\/script\/2820404\/\",\"_mediator\")}(window);<\/script>     <br \/> \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\/455172\/\"> https:\/\/habr.com\/ru\/post\/455172\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"\n<div class=\"post__text post__text-html js-mediator-article\">\n<p><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/5q\/ek\/4n\/5qek4nssuu4dsjepoaa2g9tgmw0.png\"><br \/>  <em>\u0418\u043b\u043b\u044e\u0441\u0442\u0440\u0430\u0446\u0438\u044f \u0438\u0437 \u0440\u0430\u0431\u043e\u0442\u044b \u0413.\u041c. \u0410\u0434\u0435\u043b\u044c\u0441\u043e\u043d-\u0412\u0435\u043b\u044c\u0441\u043a\u043e\u0433\u043e \u0438 \u0415.\u041c. \u041b\u0430\u043d\u0434\u0438\u0441\u0430 1962 \u0433\u043e\u0434\u0430<\/em><\/p>\n<p>  <\/p>\n<p>\u0414\u0435\u0440\u0435\u0432\u044c\u044f \u043f\u043e\u0438\u0441\u043a\u0430 \u2014 \u044d\u0442\u043e \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0434\u0430\u043d\u043d\u044b\u0445 \u0434\u043b\u044f \u0443\u043f\u043e\u0440\u044f\u0434\u043e\u0447\u0435\u043d\u043d\u043e\u0433\u043e \u0445\u0440\u0430\u043d\u0435\u043d\u0438\u044f \u0438 \u043f\u0440\u043e\u0441\u0442\u043e\u0433\u043e \u043f\u043e\u0438\u0441\u043a\u0430 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432. \u0428\u0438\u0440\u043e\u043a\u043e \u043f\u0440\u0438\u043c\u0435\u043d\u044f\u044e\u0442\u0441\u044f <em>\u0434\u0432\u043e\u0438\u0447\u043d\u044b\u0435<\/em> \u0434\u0435\u0440\u0435\u0432\u044c\u044f \u043f\u043e\u0438\u0441\u043a\u0430, \u0432 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0443 \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0443\u0437\u043b\u0430 \u0435\u0441\u0442\u044c \u0442\u043e\u043b\u044c\u043a\u043e \u0434\u0432\u0430 \u043f\u043e\u0442\u043e\u043c\u043a\u0430. \u0412 \u044d\u0442\u043e\u0439 \u0441\u0442\u0430\u0442\u044c\u0435 \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u0434\u0432\u0430 \u043c\u0435\u0442\u043e\u0434\u0430 \u043e\u0440\u0433\u0430\u043d\u0438\u0437\u0430\u0446\u0438\u0438 \u0434\u0432\u043e\u0438\u0447\u043d\u044b\u0445 \u0434\u0435\u0440\u0435\u0432\u044c\u0435\u0432 \u043f\u043e\u0438\u0441\u043a\u0430: \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0410\u0434\u0435\u043b\u044c\u0441\u043e\u043d-\u0412\u0435\u043b\u044c\u0441\u043a\u043e\u0433\u043e \u0438 \u041b\u0430\u043d\u0434\u0438\u0441\u0430 (\u0410\u0412\u041b-\u0434\u0435\u0440\u0435\u0432\u044c\u044f) \u0438 \u043e\u0441\u043b\u0430\u0431\u043b\u0435\u043d\u043d\u044b\u0435 \u0410\u0412\u041b-\u0434\u0435\u0440\u0435\u0432\u044c\u044f (WAVL-\u0434\u0435\u0440\u0435\u0432\u044c\u044f).<\/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-292887","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/292887","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=292887"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/292887\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=292887"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=292887"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=292887"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}