{"id":405,"date":"2015-11-28T11:10:48","date_gmt":"2015-11-28T08:10:48","guid":{"rendered":"http:\/\/java.mazurok.com\/?p=405"},"modified":"2016-06-29T18:13:19","modified_gmt":"2016-06-29T15:13:19","slug":"binary-tree-search","status":"publish","type":"post","link":"https:\/\/java.mazurok.com\/?p=405","title":{"rendered":"Binary Tree Search"},"content":{"rendered":"<p>\u041a\u043e\u0434 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u0411\u0438\u043d\u0430\u0440\u043d\u043e\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430 \u043d\u0430 Java \u0434\u043b\u044f \u0437\u0430\u0434\u0430\u043d\u0438\u044f \u0438\u0437 Word of Week. \u0421\u0430\u043c\u0443 \u0438\u0434\u0435\u044e \u0434\u0435\u0440\u0435\u0432\u0430 \u0438 \u0442\u0435\u043e\u0440\u0435\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043c\u043e\u0436\u043d\u043e \u043f\u043e\u0447\u0438\u0442\u0430\u0442\u044c \u0432 <a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%94%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D0%BE%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0\" target=\"_blank\">\u0412\u0438\u043a\u0438\u043f\u0435\u0434\u0438\u0438<\/a>. \u041e\u0442\u043b\u0438\u0447\u0430\u0435\u0442\u0441\u044f \u043e\u0442 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u043d\u0430 C++ \u0442\u0435\u043c, \u0447\u0442\u043e \u0432 Java \u043c\u044b \u043d\u0435 \u043e\u0431\u0440\u0430\u0449\u0430\u0435\u043c\u0441\u044f \u043a \u0430\u0434\u0440\u0435\u0441\u0430\u043c \u0443\u0437\u043b\u0430\u043c \u044f\u0432\u043d\u043e, \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0435 \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u0442 \u0447\u0435\u0440\u0435\u0437 \u043a\u043e\u043c\u043f\u0430\u0440\u0430\u0442\u043e\u0440 \u0438 \u0441\u0430\u043c \u043a\u043b\u0430\u0441\u0441 \u043f\u0440\u0438 \u0441\u043e\u0437\u0434\u0430\u043d\u0438\u0438 \u0438\u043c\u0435\u0435\u0442 \u0441\u0432\u043e\u0438 \u043e\u0441\u043e\u0431\u0435\u043d\u043d\u043e\u0441\u0442\u0438 \u043e\u0442 C++. \u0414\u043b\u044f \u0440\u0430\u0431\u043e\u0442\u044b \u0441\u0430\u043c\u043e\u0433\u043e \u043a\u043b\u0430\u0441\u0441\u0430, \u0432 \u043d\u0435\u043c \u043f\u0440\u0438\u0441\u0443\u0442\u0441\u0442\u0432\u0443\u044e\u0442 \u043f\u0440\u0438\u0432\u0430\u0442\u043d\u044b\u0435 \u043c\u0435\u0442\u043e\u0434\u044b, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0440\u0430\u0431\u043e\u0442\u0430\u044e\u0442 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u043e, \u0438 geter&#8217;\u044b, \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u044e\u0449\u0438\u0435 \u043f\u043e\u043b\u0443\u0447\u0430\u0442\u044c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u043e\u0442 \u0440\u0430\u0431\u043e\u0442\u044b \u043f\u0440\u0438\u0432\u0430\u0442\u043d\u044b\u0445 \u043c\u0435\u0442\u043e\u0434\u043e\u0432.<\/p>\n<p>\u0412 \u0442\u0435\u0441\u0442\u043e\u0432\u043e\u043c \u0432\u044b\u0432\u043e\u0434\u0435 \u043c\u043e\u0436\u043d\u043e \u043f\u0440\u043e\u043d\u0430\u0431\u043b\u044e\u0434\u0430\u0442\u044c(\u0435\u0441\u043b\u0438 \u0432\u044b \u0437\u0430\u043f\u0443\u0441\u0442\u0438\u0442\u0435 \u0434\u0430\u043d\u043d\u044b\u0439 \u043a\u043e\u0434) \u043a\u0430\u043a \u0432\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u0434\u0435\u0440\u0435\u0432\u043e \u043f\u043e\u0441\u043b\u0435 \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u0434\u0430\u043d\u043d\u044b\u0445, \u043f\u043e\u0442\u043e\u043c \u043a\u0430\u043a \u043e\u043d\u043e \u0432\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u043f\u043e\u0441\u043b\u0435 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044f \u043e\u0434\u043d\u043e\u0433\u043e \u0438\u0437 \u0443\u0437\u043b\u043e\u0432 \u0438 \u0434\u0430\u043b\u0435\u0435 \u0443\u0431\u0435\u0434\u0438\u0442\u044c\u0441\u044f \u0432 \u043f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u0445 \u0444\u0443\u043d\u043a\u0446\u0438\u0439.<\/p>\n<p><a href=\"http:\/\/ideone.com\/y2HpOt\">\u0421\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 ideone.<\/a><\/p>\n<pre class=\"lang:java decode:true \">import jdk.internal.org.objectweb.asm.tree.analysis.Value;\r\n\r\nimport java.security.Key;\r\n\r\n\/**\r\n * Created by green on 26.11.15.\r\n *\/\r\nclass BST &lt;Key extends Comparable&lt;Key&gt;, Value&gt; {\r\n\r\n    private class Node {\r\n        Key key;\r\n        Value value;\r\n        Node left, right, father;\r\n        public Node (Key key, Value value) {\r\n            this.key = key;\r\n            this.value = value;\r\n            this.left = this.right = null;\r\n            this.father = null;\r\n        }\r\n        public Node (Key key, Value value, Node father) {\r\n            this.key = key;\r\n            this.value = value;\r\n            this.left = this.right = null;\r\n            this.father = father;\r\n        }\r\n    }\r\n\r\n    private Node root;\r\n\r\n    private Node add (Node node,Key key, Value value, Node father){\r\n        if (node == null){\r\n            Node newnode = new Node(key,value, father);\r\n            return newnode;\r\n        }\r\n        int compareResult = key.compareTo(node.key);\r\n        if (compareResult &gt; 0) node.right = add(node.right, key, value, node);\r\n        else if(compareResult &lt; 0) node.left = add(node.left, key, value, node);\r\n        else{\r\n            node.value = value;\r\n        }\r\n        return node;\r\n    }\r\n\r\n    public void add(Key key, Value value) {\r\n        root = add(root, key, value, root);\r\n    }\r\n\r\n    private Node delete(Node node, Key key){\r\n        if(node == null) return null;\r\n        int compareResult = key.compareTo(node.key);\r\n        if(compareResult &gt; 0){\r\n            node.right = delete(node.right, key);\r\n        }else if(compareResult &lt; 0){\r\n            node.left = delete(node.left, key);\r\n        }else{\r\n            if(node.right == null &amp;&amp; node.left == null){\r\n                return node = null;\r\n            }else if(node.right == null){\r\n                return node = node.left;\r\n            }else if(node.left == null){\r\n                return node = node.right;\r\n            }else{\r\n                if(node.right.left == null){\r\n                    node.right.left = node.left;\r\n                    node.right.father = node.father;\r\n                    return node = node.right;\r\n                }else{\r\n                    Node res = min(node.right);\r\n                    node.key = res.key;\r\n                    node.value = res.value;\r\n                    delete(node.right, node.key);\r\n                    return node;\r\n                }\r\n            }\r\n        }\r\n        return node;\r\n    }\r\n\r\n    public void delete(Key key) {\r\n        root = delete(root, key);\r\n    }\r\n\r\n    public Key minKey(){\r\n        return min(root).key;\r\n    }\r\n\r\n    public Key maxKey(){\r\n        return max(root).key;\r\n    }\r\n\r\n    private Node min(Node node){\r\n        if(node.left == null) return node;\r\n        return min(node.left);\r\n    }\r\n\r\n    private Node max(Node node){\r\n        if(node.right == null) return node;\r\n        return min(node.right);\r\n    }\r\n\r\n    private Value get(Node node, Key key){\r\n        if(node == null) return null;\r\n        int compareResult = key.compareTo(node.key);\r\n        if(compareResult == 0){\r\n            return node.value;\r\n        }else if(compareResult &gt; 0){\r\n            return get(node.right, key);\r\n        }else{\r\n            return get(node.left, key);\r\n        }\r\n    }\r\n\r\n    public Value get(Key key) {\r\n        return get(root, key);\r\n    }\r\n\r\n    private void print(Node node, int level) {\r\n        if (node != null) {\r\n            print(node.right,level+1);\r\n            for (int i=0;i&lt;level;i++) {\r\n                System.out.print(\"\\t\");\r\n            }\r\n            System.out.println(node.key + \"-&gt;\" + node.value);\r\n            print(node.left,level+1);\r\n        }\r\n    }\r\n\r\n    public void print() {\r\n        print(root,0);\r\n    }\r\n\r\n}\r\n\r\npublic class Hello_World {\r\n    public static void main(String[] args) {\r\n        BST&lt;Integer, String&gt; tree = new BST&lt;&gt;();\r\n        tree.add(10, \"Test1\");\r\n        tree.add(12, \"Test2\");\r\n        tree.add(1, \"Test3\");\r\n        tree.add(5, \"Test4\");\r\n        tree.add(6, \"Test5\");\r\n        tree.add(3, \"Test5\");\r\n        tree.print();\r\n        tree.delete(5);\r\n        tree.print();\r\n        System.out.println(tree.get(1));\r\n        System.out.println(tree.minKey());\r\n        System.out.println(tree.maxKey());\r\n        System.out.println(tree.get(3));\r\n    }\r\n}<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>\u041a\u043e\u0434 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u0411\u0438\u043d\u0430\u0440\u043d\u043e\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430 \u043d\u0430 Java \u0434\u043b\u044f \u0437\u0430\u0434\u0430\u043d\u0438\u044f \u0438\u0437 Word of Week. \u0421\u0430\u043c\u0443 \u0438\u0434\u0435\u044e \u0434\u0435\u0440\u0435\u0432\u0430 \u0438 \u0442\u0435\u043e\u0440\u0435\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043c\u043e\u0436\u043d\u043e \u043f\u043e\u0447\u0438\u0442\u0430\u0442\u044c \u0432 \u0412\u0438\u043a\u0438\u043f\u0435\u0434\u0438\u0438. \u041e\u0442\u043b\u0438\u0447\u0430\u0435\u0442\u0441\u044f \u043e\u0442 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u043d\u0430 C++ \u0442\u0435\u043c, \u0447\u0442\u043e \u0432 Java \u043c\u044b \u043d\u0435 \u043e\u0431\u0440\u0430\u0449\u0430\u0435\u043c\u0441\u044f \u043a \u0430\u0434\u0440\u0435\u0441\u0430\u043c \u0443\u0437\u043b\u0430\u043c \u044f\u0432\u043d\u043e, \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0435 \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u0442 \u0447\u0435\u0440\u0435\u0437 \u043a\u043e\u043c\u043f\u0430\u0440\u0430\u0442\u043e\u0440 \u0438 \u0441\u0430\u043c \u043a\u043b\u0430\u0441\u0441 \u043f\u0440\u0438 \u0441\u043e\u0437\u0434\u0430\u043d\u0438\u0438 \u0438\u043c\u0435\u0435\u0442 \u0441\u0432\u043e\u0438 \u043e\u0441\u043e\u0431\u0435\u043d\u043d\u043e\u0441\u0442\u0438 \u043e\u0442 C++. \u0414\u043b\u044f \u0440\u0430\u0431\u043e\u0442\u044b \u0441\u0430\u043c\u043e\u0433\u043e &hellip; <a href=\"https:\/\/java.mazurok.com\/?p=405\" class=\"more-link\">Continue reading <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":33,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[27,49],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/java.mazurok.com\/index.php?rest_route=\/wp\/v2\/posts\/405"}],"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\/33"}],"replies":[{"embeddable":true,"href":"https:\/\/java.mazurok.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=405"}],"version-history":[{"count":7,"href":"https:\/\/java.mazurok.com\/index.php?rest_route=\/wp\/v2\/posts\/405\/revisions"}],"predecessor-version":[{"id":565,"href":"https:\/\/java.mazurok.com\/index.php?rest_route=\/wp\/v2\/posts\/405\/revisions\/565"}],"wp:attachment":[{"href":"https:\/\/java.mazurok.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=405"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/java.mazurok.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=405"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/java.mazurok.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=405"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}