{"id":472,"date":"2015-12-16T16:33:19","date_gmt":"2015-12-16T13:33:19","guid":{"rendered":"http:\/\/java.mazurok.com\/?p=472"},"modified":"2015-12-21T00:07:43","modified_gmt":"2015-12-20T21:07:43","slug":"binarysearchtree","status":"publish","type":"post","link":"https:\/\/java.mazurok.com\/?p=472","title":{"rendered":"BinarySearchTree"},"content":{"rendered":"<p>\u0414\u0432\u043e\u0438\u0447\u043d\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e \u043f\u043e\u0438\u0441\u043a\u0430, \u0438\u043b\u0438 BST, &#8212; \u044d\u0442\u043e \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u0434\u0430\u043d\u043d\u044b\u0445, \u043f\u0440\u0435\u0434\u043d\u0430\u0437\u043d\u0430\u0447\u0435\u043d\u043d\u0430\u044f \u0434\u043b\u044f \u0440\u0430\u0431\u043e\u0442\u044b \u0441 \u0443\u043f\u043e\u0440\u044f\u0434\u043e\u0447\u0435\u043d\u043d\u044b\u043c\u0438 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430\u043c\u0438.<\/p>\n<p>\u0421\u0432\u043e\u0439\u0441\u0442\u0432\u043e \u0434\u0435\u0440\u0435\u0432\u0430: \u0435\u0441\u043b\u0438 \u043c\u044b \u043d\u0430\u0445\u043e\u0434\u0438\u043c\u0441\u044f \u0432 \u0432\u0435\u0440\u0448\u0438\u043d\u0435 \u0441 \u043a\u043b\u044e\u0447\u043e\u043c k, \u0442\u043e \u0432 \u043b\u0435\u0432\u043e\u043c \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u0435 \u043d\u0430\u0445\u043e\u0434\u044f\u0442\u0441\u044f \u0442\u043e\u043b\u044c\u043a\u043e \u043a\u043b\u044e\u0447\u0438, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0441\u0442\u0440\u043e\u0433\u043e \u043c\u0435\u043d\u044c\u0448\u0435 k, \u0430 \u0432 \u043f\u0440\u0430\u0432\u043e\u043c &#8212; \u0441\u0442\u0440\u043e\u0433\u043e \u0431\u043e\u043b\u044c\u0448\u0435.<\/p>\n<p>\u041e\u043f\u0438\u0441\u0430\u043d\u0438\u0435 \u043c\u0435\u0442\u043e\u0434\u043e\u0432, \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u043d\u043d\u044b\u0445 \u0432 \u043a\u043b\u0430\u0441\u0441\u0435 BinarySearchTree:<\/p>\n<ul>\n<li>\u043c\u0435\u0442\u043e\u0434 <strong>add()<\/strong>:\n<ul>\n<li>\u0435\u0441\u043b\u0438 \u0434\u0435\u0440\u0435\u0432\u043e \u043f\u0443\u0441\u0442\u043e\u0435, \u0442\u043e \u0433\u043e\u0432\u043e\u0440\u0438\u043c, \u0447\u0442\u043e \u043a\u043e\u0440\u0435\u043d\u044c &#8212; \u044d\u0442\u043e \u043d\u0430\u0448 \u0443\u0437\u0435\u043b;<\/li>\n<li>\u0441\u0440\u0430\u0432\u043d\u0438\u0432\u0430\u0435\u043c \u043f\u043e\u0441\u0442\u0443\u043f\u0438\u0432\u0448\u0438\u0439 \u043a\u043b\u044e\u0447 \u0441 \u043a\u043b\u044e\u0447\u043e\u043c \u0443\u0437\u043b\u0430:\n<ul>\n<li>\u0435\u0441\u043b\u0438 \u043a\u043b\u044e\u0447 \u043c\u0435\u043d\u044c\u0448\u0435, \u0442\u043e \u0438\u0434\u0451\u043c \u0432 \u043b\u0435\u0432\u043e\u0435 \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u043e;<\/li>\n<li>\u0435\u0441\u043b\u0438 \u043a\u043b\u044e\u0447 \u0440\u0430\u0432\u0435\u043d, \u0442\u043e \u0437\u0430\u0434\u0430\u0451\u043c \u0443\u0437\u043b\u0443\u00a0\u043d\u043e\u0432\u043e\u0435 \u043f\u043e\u0441\u0442\u0443\u043f\u0438\u0432\u0448\u0435\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435;<\/li>\n<li>\u0435\u0441\u043b\u0438 \u043a\u043b\u044e\u0447 \u0431\u043e\u043b\u044c\u0448\u0435, \u0442\u043e \u0438\u0434\u0451\u043c \u0432 \u043f\u0440\u0430\u0432\u043e\u0435 \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u043e;<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n<li>\u043c\u0435\u0442\u043e\u0434\u044b <strong>minKey()<\/strong> \u0438 <strong>maxKey()<\/strong>:\n<ul>\n<li>\u043f\u043e \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u0443 \u0434\u0435\u0440\u0435\u0432\u0430, \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 \u043a\u043b\u044e\u0447 \u0440\u0430\u0441\u043f\u043e\u043b\u0430\u0433\u0430\u0435\u0442\u0441\u044f \u0432 \u0441\u0430\u043c\u043e\u043c \u043b\u0435\u0432\u043e\u043c \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u0435, \u0430 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 &#8212; \u0432 \u0441\u0430\u043c\u043e\u043c \u043f\u0440\u0430\u0432\u043e\u043c;<\/li>\n<\/ul>\n<\/li>\n<li>\u043c\u0435\u0442\u043e\u0434 <strong>delete()<\/strong>:\n<ul>\n<li>\u0441\u043d\u0430\u0447\u0430\u043b\u0430 \u043d\u0430\u0445\u043e\u0434\u0438\u043c \u043d\u0443\u0436\u043d\u044b\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u043f\u043e \u043a\u043b\u044e\u0447\u0443 (\u0435\u0441\u043b\u0438 \u0442\u0430\u043a\u043e\u0432\u043e\u0433\u043e \u043d\u0435\u0442, \u0442\u043e \u0432\u044b\u0445\u043e\u0434\u0438\u043c \u0438\u0437 \u043c\u0435\u0442\u043e\u0434\u0430);<\/li>\n<li>\u0435\u0441\u043b\u0438 \u0443 \u0443\u0434\u0430\u043b\u044f\u0435\u043c\u043e\u0433\u043e \u0443\u0437\u043b\u0430 \u043d\u0435\u0442 \u043f\u0440\u0430\u0432\u043e\u0433\u043e \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u0430, \u0442\u043e \u043c\u044b \u043f\u0440\u043e\u0441\u0442\u043e \u0437\u0430\u043c\u0435\u0449\u0430\u0435\u043c \u0443\u0437\u0435\u043b \u0435\u0433\u043e \u043b\u0435\u0432\u044b\u043c \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u043e\u043c;<\/li>\n<li>\u0438\u043d\u0430\u0447\u0435\u00a0\u043d\u0430\u0445\u043e\u0434\u0438\u043c \u0432 \u043f\u0440\u0430\u0432\u043e\u043c \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u0435 \u0443\u0437\u0435\u043b \u0441 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u043c \u043a\u043b\u044e\u0447\u043e\u043c:\n<ul>\n<li>\u0435\u0441\u043b\u0438 \u0443 \u044d\u0442\u043e\u0433\u043e \u0443\u0437\u043b\u0430 \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044c &#8212; \u044d\u0442\u043e \u0443\u0434\u0430\u043b\u044f\u0435\u043c\u044b\u0439 \u0443\u0437\u0435\u043b, \u0442\u043e \u043c\u044b \u043f\u0440\u043e\u0441\u0442\u043e \u0433\u043e\u0432\u043e\u0440\u0438\u043c, \u0447\u0442\u043e \u043f\u0440\u0430\u0432\u043e\u0435 \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u043e \u0443\u0434\u0430\u043b\u044f\u0435\u043c\u043e\u0433\u043e \u0443\u0437\u043b\u0430 \u0435\u0441\u0442\u044c \u043f\u0440\u0430\u0432\u043e\u0435 \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u043e \u043d\u0430\u0439\u0434\u0435\u043d\u043d\u043e\u0433\u043e, \u0430 \u043a\u043b\u044e\u0447 \u0438 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0443\u0434\u0430\u043b\u044f\u0435\u043c\u043e\u0433\u043e \u0443\u0437\u043b\u0430 &#8212; \u044d\u0442\u043e \u043a\u043b\u044e\u0447 \u0438 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u043d\u0430\u0439\u0434\u0435\u043d\u043d\u043e\u0433\u043e;<\/li>\n<li>\u0435\u0441\u043b\u0438 \u0443 \u044d\u0442\u043e\u0433\u043e \u0443\u0437\u043b\u0430 \u0434\u0440\u0443\u0433\u043e\u0439 \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044c, \u0442\u043e \u043c\u044b \u0437\u0430\u043c\u0435\u0449\u0430\u0435\u043c \u043d\u0430\u0439\u0434\u0435\u043d\u043d\u044b\u0439 \u0443\u0437\u0435\u043b \u0435\u0433\u043e \u0436\u0435 \u043f\u0440\u0430\u0432\u044b\u043c \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u043e\u043c, \u0430\u00a0\u043a\u043b\u044e\u0447 \u0438 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0443\u0434\u0430\u043b\u044f\u0435\u043c\u043e\u0433\u043e \u0443\u0437\u043b\u0430 &#8212; \u044d\u0442\u043e \u043a\u043b\u044e\u0447 \u0438 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u043d\u0430\u0439\u0434\u0435\u043d\u043d\u043e\u0433\u043e;<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<p>\u041a\u043e\u0434 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u044b (<a href=\"http:\/\/ideone.com\/Z2hbBv\">http:\/\/ideone.com\/Z2hbBv<\/a>):<\/p>\n<pre class=\"lang:java decode:true\">import java.util.*;\r\nimport java.lang.*;\r\nimport java.io.*;\r\n \r\nclass BinarySearchTree &lt;Key extends Comparable&lt;Key&gt;, Value&gt; {\r\n\tprivate class Node {\r\n\t\tKey key;\r\n\t\tValue value;\r\n\t\tNode left, right;\r\n\t\tpublic Node (Key key, Value value) {\r\n\t\t\tthis.key = key;\r\n\t\t\tthis.value = value;\r\n\t\t\tthis.left = this.right = null;\r\n\t\t}\r\n\t}\r\n\tprivate Node root;\r\n\t\r\n\tprivate Node add(Node node, Key key, Value value) {\r\n\t\tif (node == null) node = new Node(key, value);\r\n\t\telse {\r\n\t\t\tint compareResult = key.compareTo(node.key);\r\n\t        if(compareResult &lt; 0) node.left = add(node.left, key, value);\r\n    \t    else if (compareResult == 0) node.value = value; \r\n        \telse node.right = add(node.right, key, value);\r\n\t\t}\r\n        return node;\r\n\t}\r\n\tpublic void add(Key key, Value value) {\r\n\t\troot = add(root, key, value);\r\n\t}\r\n        \r\n\tpublic Key MinKey(){\r\n        Node cur = root;\r\n        while (cur.left != null) cur = cur.left;\r\n        return cur.key;\r\n    }\r\n    \r\n\tpublic Key MaxKey(){\r\n        Node cur = root;\r\n        while (cur.right != null) cur = cur.right;\r\n        return cur.key;\r\n    }\r\n\r\n\tpublic void delete(Key key) {\r\n        Node cur = root;\r\n        Node prev = null;\r\n        while (true) {\r\n            if (cur == null) return;\r\n            int compareResult = key.compareTo(cur.key);\r\n            if (compareResult &lt; 0) {\r\n                prev = cur; \r\n                cur = cur.left;\r\n            }\r\n            else if (compareResult == 0) break;\r\n            else {\r\n            \tprev = cur;\r\n                cur = cur.right;\r\n            }\r\n        }\r\n        if (cur.right == null) {\r\n        \tif (cur == prev.left) prev.left = cur.left;\r\n        \telse prev.right = cur.left;\r\n        }\r\n        else {\r\n        \tNode minFromRight = cur.right;\r\n        \tprev = null;\r\n        \twhile (minFromRight.left != null) {\r\n        \t\tprev = minFromRight;\r\n        \t\tminFromRight = minFromRight.left;\r\n        \t}\r\n        \tif (prev == null) cur.right = minFromRight.right;\r\n        \telse prev.left = minFromRight.right;\r\n        \tcur.key = minFromRight.key;\r\n        \tcur.value = minFromRight.value;\r\n        }\r\n\t}\r\n\t\r\n\tpublic Value get(Key key) {\r\n        Node cur = root;\r\n        while (true) {\r\n            if (cur == null) break;\r\n            int compareResult = key.compareTo(cur.key);\r\n            if (compareResult &lt; 0) cur = cur.left;\r\n            else if (compareResult == 0) break;\r\n            else cur = cur.right;\r\n        }\r\n        return cur == null ? (Value)null : cur.value;\r\n\t}\r\n\t\r\n\tprivate void print(Node node, int level) {\r\n\t\tif (node != null) {\r\n\t\t\tprint(node.right, level + 1);\r\n\t\t\tfor (int i = 0; i &lt; level; i++) {\r\n\t\t\t\tSystem.out.print(\"\\t\");\r\n\t\t\t}\r\n\t\t\tSystem.out.println(node.key);\r\n\t\t\t\/\/System.out.println(node.key + \" -&gt; \" + node.value); \r\n\t\t\tprint(node.left, level + 1);\r\n\t\t}\r\n\t}\r\n\tpublic void print() {\r\n\t\tprint(root, 0);\r\n\t}\r\n}\r\n \r\nclass Ideone {\r\n\tpublic static void main (String[] args) {\r\n\t\tBinarySearchTree&lt;Integer, Integer&gt; a = new BinarySearchTree&lt;Integer, Integer&gt;();\r\n\t\tint n = 10;\r\n\t\tfor(int i = 0; i &lt; n; i++) {\r\n\t\t\ta.add((int)(Math.random()*10), (int)(Math.random()*1000));\r\n\t\t}\r\n\t\tSystem.out.println(a.MaxKey() + \" -&gt; \" + a.get(a.MaxKey()));\r\n\t\tSystem.out.println(a.MinKey() + \" -&gt; \" + a.get(a.MinKey()));\r\n\t\ta.print();\r\n\t\tSystem.out.println(\"\\n\\n\");\r\n\t\tInteger x = (int)(Math.random()*10);\r\n\t\tSystem.out.println(x);\r\n\t\tSystem.out.println(\"\\n\\n\");\r\n\t\ta.delete(x);\r\n\t\ta.print();\r\n\t}\r\n}<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u0414\u0432\u043e\u0438\u0447\u043d\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e \u043f\u043e\u0438\u0441\u043a\u0430, \u0438\u043b\u0438 BST, &#8212; \u044d\u0442\u043e \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u0434\u0430\u043d\u043d\u044b\u0445, \u043f\u0440\u0435\u0434\u043d\u0430\u0437\u043d\u0430\u0447\u0435\u043d\u043d\u0430\u044f \u0434\u043b\u044f \u0440\u0430\u0431\u043e\u0442\u044b \u0441 \u0443\u043f\u043e\u0440\u044f\u0434\u043e\u0447\u0435\u043d\u043d\u044b\u043c\u0438 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430\u043c\u0438. \u0421\u0432\u043e\u0439\u0441\u0442\u0432\u043e \u0434\u0435\u0440\u0435\u0432\u0430: \u0435\u0441\u043b\u0438 \u043c\u044b \u043d\u0430\u0445\u043e\u0434\u0438\u043c\u0441\u044f \u0432 \u0432\u0435\u0440\u0448\u0438\u043d\u0435 \u0441 \u043a\u043b\u044e\u0447\u043e\u043c k, \u0442\u043e \u0432 \u043b\u0435\u0432\u043e\u043c \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u0435 \u043d\u0430\u0445\u043e\u0434\u044f\u0442\u0441\u044f \u0442\u043e\u043b\u044c\u043a\u043e \u043a\u043b\u044e\u0447\u0438, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0441\u0442\u0440\u043e\u0433\u043e \u043c\u0435\u043d\u044c\u0448\u0435 k, \u0430 \u0432 \u043f\u0440\u0430\u0432\u043e\u043c &#8212; \u0441\u0442\u0440\u043e\u0433\u043e \u0431\u043e\u043b\u044c\u0448\u0435. \u041e\u043f\u0438\u0441\u0430\u043d\u0438\u0435 \u043c\u0435\u0442\u043e\u0434\u043e\u0432, \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u043d\u043d\u044b\u0445 \u0432 \u043a\u043b\u0430\u0441\u0441\u0435 BinarySearchTree: \u043c\u0435\u0442\u043e\u0434 add(): \u0435\u0441\u043b\u0438 \u0434\u0435\u0440\u0435\u0432\u043e \u043f\u0443\u0441\u0442\u043e\u0435, \u0442\u043e \u0433\u043e\u0432\u043e\u0440\u0438\u043c, &hellip; <a href=\"https:\/\/java.mazurok.com\/?p=472\" class=\"more-link\">Continue reading <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":20,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[49],"tags":[50,51,52],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/java.mazurok.com\/index.php?rest_route=\/wp\/v2\/posts\/472"}],"collection":[{"href":"https:\/\/java.mazurok.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/java.mazurok.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/java.mazurok.com\/index.php?rest_route=\/wp\/v2\/users\/20"}],"replies":[{"embeddable":true,"href":"https:\/\/java.mazurok.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=472"}],"version-history":[{"count":1,"href":"https:\/\/java.mazurok.com\/index.php?rest_route=\/wp\/v2\/posts\/472\/revisions"}],"predecessor-version":[{"id":473,"href":"https:\/\/java.mazurok.com\/index.php?rest_route=\/wp\/v2\/posts\/472\/revisions\/473"}],"wp:attachment":[{"href":"https:\/\/java.mazurok.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=472"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/java.mazurok.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=472"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/java.mazurok.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=472"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}