{"id":505,"date":"2015-12-20T23:12:26","date_gmt":"2015-12-20T20:12:26","guid":{"rendered":"http:\/\/java.mazurok.com\/?p=505"},"modified":"2015-12-28T01:18:59","modified_gmt":"2015-12-27T22:18:59","slug":"%d0%b0%d0%b2%d0%bb-%d0%b4%d0%b5%d1%80%d0%b5%d0%b2%d0%be","status":"publish","type":"post","link":"https:\/\/java.mazurok.com\/?p=505","title":{"rendered":"\u0410\u0412\u041b-\u0434\u0435\u0440\u0435\u0432\u043e"},"content":{"rendered":"<p>\u041e\u043f\u0438\u0441\u0430\u043d\u0438\u0435 \u0410\u0412\u041b-\u0434\u0435\u0440\u0435\u0432\u0430 \u0432\u044b \u043c\u043e\u0436\u0435\u0442\u0435 \u043f\u0440\u043e\u0447\u0438\u0442\u0430\u0442\u044c \u0432 <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\">\u0412\u0438\u043a\u0438\u043f\u0435\u0434\u0438\u0438.<\/a><\/p>\n<p>\u0417\u0434\u0435\u0441\u044c \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d \u043a\u043e\u0434 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u043e\u0433\u043e \u0410\u0412\u041b-\u0434\u0435\u0440\u0435\u0432\u0430. \u041e\u0442\u043b\u0438\u0447\u0430\u0435\u0442\u0441\u044f \u043e\u0442 \u043e\u0431\u044b\u0447\u043d\u043e \u0431\u0438\u043d\u0430\u0440\u043d\u043e\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430 \u0442\u0435\u043c, \u0447\u0442\u043e \u0443 \u0443\u0437\u043b\u043e\u0432 \u0435\u0441\u0442\u044c \u0432\u044b\u0441\u043e\u0442\u0430 \u0438 \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c \u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u043e\u0432\u043a\u0438. \u0411\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u043e\u0432\u043a\u0430 \u043c\u043e\u0436\u0435\u0442 \u043c\u0435\u043d\u044f\u0442\u044c\u0441\u044f \u043f\u0440\u0438 \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u0438 \u0438\u043b\u0438 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u0438, \u0438 \u0432\u043e\u0441\u0441\u0442\u0430\u043d\u0430\u0432\u043b\u0438\u0432\u0430\u0435\u0442\u0441\u044f \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u043c\u0430\u043b\u043e\u0433\u043e \u043b\u0435\u0432\u043e\u0433\u043e(\u043f\u0440\u0430\u0432\u043e\u0433\u043e), \u0438\u043b\u0438 \u0431\u043e\u043b\u044c\u0448\u043e\u0433\u043e \u043b\u0435\u0432\u043e\u0433\u043e(\u043f\u0440\u0430\u0432\u043e\u0433\u043e) \u043f\u043e\u0432\u043e\u0440\u043e\u0442\u043e\u0432. \u041a\u0430\u043a \u044d\u0442\u043e \u0432\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u043c\u043e\u0436\u043d\u043e \u0443\u0432\u0438\u0434\u0435\u0442\u044c \u0432 \u0442\u043e\u0439 \u0436\u0435 \u0412\u0438\u043a\u0438\u043f\u0435\u0434\u0438\u0438.<\/p>\n<p>\u041f\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c \u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u043e\u0432\u043a\u0438 \u043f\u043e\u0434\u0441\u0447\u0438\u0442\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u0441\u043f\u0435\u0446\u0438\u0430\u043b\u044c\u043d\u043e\u0439 \u0444\u0443\u043d\u043a\u0446\u0438\u0435\u0439, \u043a\u0430\u043a \u0438 \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c \u0432\u044b\u0441\u043e\u0442\u044b.<\/p>\n<p>\u0414\u043b\u044f \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e\u0441\u0442\u0438 \u0431\u0435\u0433\u0430\u0442\u044c \u043f\u043e \u0443\u0437\u043b\u0430\u043c \u0434\u0435\u0440\u0435\u0432\u0430, \u0435\u0441\u0442\u044c \u043f\u0440\u0438\u0432\u0430\u0442\u043d\u044b\u0435 \u0444\u0443\u043d\u043a\u0446\u0438\u044f getHigherNode, getLowerNode. \u041a \u043a\u043e\u0442\u043e\u0440\u044b\u043c \u0435\u0441\u0442\u044c \u0434\u043e\u0441\u0442\u0443\u043f \u0443 \u0443\u0437\u043b\u043e\u0432. \u041a \u043f\u0440\u0438\u043c\u0435\u0440\u0443 \u043c\u044b \u0432 \u0441\u0430\u043c\u043e\u0439 \u043b\u0435\u0432\u043e\u0439 \u0432\u0435\u0440\u0448\u0438\u043d\u0435 \u0434\u0435\u0440\u0435\u0432\u0430, \u043b\u0438\u0431\u043e \u043c\u044b \u043b\u0438\u0441\u0442, \u043b\u0438\u0431\u043e \u0443 \u043d\u0430\u0441 \u0435\u0441\u0442\u044c \u043f\u0440\u0430\u0432\u043e\u0435 \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u043e. \u0415\u0441\u043b\u0438 \u043c\u044b \u043b\u0438\u0441\u0442, \u0442\u043e \u043d\u0430\u0434\u043e \u0432\u0435\u0440\u043d\u0443\u0442\u044c \u043f\u0440\u043e\u0441\u0442\u043e \u043d\u0430\u0448\u0435\u0433\u043e \u043f\u0440\u0435\u0434\u043a\u0430. \u0415\u0441\u043b\u0438 \u0436\u0435 \u0435\u0441\u0442\u044c \u043f\u0440\u0430\u0432\u043e\u0435 \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u043e. \u0422\u043e \u043d\u0430\u0434\u043e \u0432\u044b\u0432\u0435\u0441\u0442\u0438 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0443\u044e \u0432\u0435\u0440\u0448\u0438\u043d\u0443 \u0441\u043f\u0440\u0430\u0432\u0430. \u041c\u044b \u043f\u043e\u043f\u0430\u043b\u0438 \u0432 \u044d\u0442\u0443 \u0432\u0435\u0440\u0448\u0438\u043d\u0443. \u041c\u044b \u0441\u043d\u043e\u0432\u0430 \u043b\u0438\u0431\u043e \u043b\u0438\u0441\u0442, \u043b\u0438\u0431\u043e \u0435\u0441\u0442\u044c \u043f\u0440\u0430\u0432\u043e\u0435 \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u043e, \u043b\u0438\u0431\u043e \u0435\u0441\u0442\u044c \u043b\u0435\u0432\u043e\u0435 \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u043e, \u043b\u0438\u0431\u043e \u0441\u0440\u0430\u0437\u0443 \u043e\u0431\u0430. \u0415\u0441\u043b\u0438 \u043c\u044b \u043b\u0438\u0441\u0442, \u0442\u043e \u043d\u0430\u043c \u043d\u0430\u0434\u043e \u043f\u043e\u0434\u043d\u044f\u0442\u044c\u0441\u044f \u0432\u0432\u0435\u0440\u0445 \u043f\u043e \u0434\u0435\u0440\u0435\u0432\u0443, \u043f\u043e\u043a\u0430 \u043c\u044b \u044f\u0432\u043b\u044f\u0435\u043c\u0441\u044f \u043f\u0440\u0430\u0432\u044b\u043c \u0441\u044b\u043d\u043e\u043c \u043d\u0430\u0448\u0435\u0433\u043e \u043f\u0440\u0435\u0434\u043a\u0430, \u043a\u0430\u043a \u0442\u043e\u043b\u044c\u043a\u043e \u043c\u044b \u043f\u043e\u043f\u0430\u0434\u0435\u043c \u0432 \u043d\u0430\u0448 \u043f\u0435\u0440\u0432\u043e\u043d\u0430\u0447\u0430\u043b\u044c\u043d\u044b\u0439 \u0441\u0430\u043c\u044b\u0439 \u043c\u0430\u043b\u0435\u043d\u044c\u043a\u0438\u0439 \u0443\u0437\u0435\u043b, \u043c\u044b \u043f\u0435\u0440\u0435\u0441\u0442\u0430\u0435\u043c \u0431\u044b\u0442\u044c \u043f\u0440\u0430\u0432\u044b\u043c \u0441\u044b\u043d\u043e\u043c, \u0437\u043d\u0430\u0447\u0438\u0442 \u043d\u0430\u043c \u043f\u043e\u0440\u0430 \u043e\u0441\u0442\u0430\u043d\u043e\u0432\u0438\u0442\u044c\u0441\u044f, \u0438 \u0432\u0435\u0440\u043d\u0443\u0442\u044c \u043e\u0442\u0446\u0430 \u0441\u0430\u043c\u043e\u0433\u043e \u043c\u0430\u043b\u0435\u043d\u044c\u043a\u043e\u0433\u043e \u0443\u0437\u043b\u0430. \u0415\u0441\u043b\u0438 \u0436\u0435 \u0435\u0441\u0442\u044c \u0442\u043e\u043b\u044c\u043a\u043e \u043f\u0440\u0430\u0432\u043e\u0435 \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u043e(\u0432\u0435\u0440\u043d\u0443\u043b\u0438\u0441\u044c \u043a \u043c\u043e\u043c\u0435\u043d\u0442\u0443, \u0433\u0434\u0435 \u043c\u044b \u043f\u0440\u0430\u0432\u044b\u0439 \u0443\u0437\u0435\u043b \u043e\u0442 \u0441\u0430\u043c\u043e\u0433\u043e \u043c\u0430\u043b\u0435\u043d\u044c\u043a\u043e\u0433\u043e), \u0442\u043e \u0441\u043f\u0443\u0441\u043a\u0430\u0435\u043c\u0441\u044f \u0441\u043d\u043e\u0432\u0430 \u0432\u043f\u0440\u0430\u0432\u043e \u0438 \u0438\u043c\u0435\u0435\u043c \u0442\u0435 \u0436\u0435 \u0441\u0438\u0442\u0443\u0430\u0446\u0438\u0438. \u0415\u0441\u043b\u0438 \u0436\u0435 \u0435\u0441\u0442\u044c \u0442\u043e\u043b\u044c\u043a\u043e \u043b\u0435\u0432\u043e\u0435 \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u043e, \u0442\u043e \u0437\u0430\u0445\u043e\u0434\u0438\u043c \u0432 \u043d\u0435\u0433\u043e \u0438 \u0434\u0435\u0439\u0441\u0442\u0432\u0443\u0435\u043c \u043f\u043e \u0442\u0435\u043c \u0436\u0435 \u043f\u0440\u0430\u0432\u0438\u043b\u0430\u043c. \u0415\u0441\u043b\u0438 \u0435\u0441\u0442\u044c \u043e\u0431\u0430, \u0442\u043e \u0441\u043d\u0430\u0447\u0430\u043b\u0430 \u043f\u043e\u0439\u0434\u0435\u043c \u0432 \u043b\u0435\u0432\u043e\u0435 \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u043e, \u043f\u043e\u0441\u043b\u0435 \u0442\u043e\u0433\u043e, \u043a\u0430\u043a \u043c\u044b \u0442\u0430\u043c \u043f\u043e\u0431\u044b\u0432\u0430\u0435\u043c \u0438 \u0432\u0435\u0440\u043d\u0435\u043c\u0441\u044f \u043a \u0443\u0437\u043b\u0443, \u043d\u0430\u043c \u043d\u0430\u0434\u043e \u0431\u0443\u0434\u0435\u0442 \u043f\u0440\u043e\u0434\u043e\u043b\u0436\u0438\u0442\u044c \u043e\u0431\u0445\u043e\u0434\u0438\u0442\u044c \u043f\u0440\u0430\u0432\u043e\u0435 \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u043e.<\/p>\n<p>\u041f\u043e\u043f\u0440\u043e\u0431\u0443\u0439\u0442\u0435 \u0434\u0430\u043d\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0434\u0435\u0439\u0441\u0442\u0432\u0438\u044f, \u0434\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430.<\/p>\n<ul>\n<li>\u041e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u0435 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0434\u043b\u044f \u0443\u0437\u043b\u0430 0001.<\/li>\n<li>\u041e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u0435 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0434\u043b\u044f \u0443\u0437\u043b\u0430 0003.<\/li>\n<li>\u041e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u0435 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0434\u043b\u044f \u0443\u0437\u043b\u0430 0004.<\/li>\n<li>\u041e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u0435 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0434\u043b\u044f \u0443\u0437\u043b\u0430 0005.<\/li>\n<li>\u041e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u0435 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0434\u043b\u044f \u0443\u0437\u043b\u0430 0007, \u0437\u043d\u0430\u044f, \u0447\u0442\u043e \u043f\u0440\u0435\u0434\u043e\u043a \u043a\u043e\u0440\u043d\u044f &#8212; \u044d\u0442\u043e null.<\/li>\n<\/ul>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-536\" src=\"http:\/\/java.mazurok.com\/wp-content\/uploads\/\u0414\u0435\u0440\u0435\u0432\u043e.png\" alt=\"\u0414\u0435\u0440\u0435\u0432\u043e\" width=\"195\" height=\"206\" \/><\/p>\n<p>\u0412 \u043a\u043e\u0434\u0435 \u043f\u0440\u0438\u0441\u0443\u0442\u0441\u0442\u0432\u0443\u0435\u0442 \u043f\u043e\u044d\u0442\u0430\u043f\u043d\u044b\u0439 \u0432\u044b\u0432\u043e\u0434 \u0434\u0435\u0440\u0435\u0432\u0430. \u0427\u0442\u043e\u0431\u044b \u0443\u0431\u0435\u0434\u0438\u0442\u044c\u0441\u044f \u0432 \u043a\u043e\u0440\u0440\u0435\u043a\u0442\u043d\u043e\u0441\u0442\u0438 \u043c\u0435\u0442\u043e\u0434\u043e\u0432. \u0421\u043d\u0430\u0447\u0430\u043b\u0430 \u0432\u0432\u043e\u0434\u044f\u0442\u0441\u044f \u0442\u0430\u043a \u0434\u0430\u043d\u043d\u044b\u0435, \u0447\u0442\u043e\u0431\u044b \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u043c\u0430\u043b\u044b\u0439 \u043b\u0435\u0432\u044b\u0439 \u043f\u043e\u0432\u043e\u0440\u043e\u0442. \u041f\u043e\u0442\u043e\u043c \u0442\u0430\u043a, \u0447\u0442\u043e\u0431\u044b \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u0431\u043e\u043b\u044c\u0448\u043e\u0439 \u043b\u0435\u0432\u044b\u0439 \u043f\u043e\u0432\u043e\u0440\u043e\u0442 \u0438 \u043c\u0430\u043b\u044b\u0439 \u043f\u0440\u0430\u0432\u044b\u0439. \u041f\u043e\u0441\u043b\u0435 \u044d\u0442\u043e\u0433\u043e \u0443\u0434\u0430\u043b\u044f\u044e\u0442\u0441\u044f \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0442\u0430\u043a \u0436\u0435, \u043a\u0430\u043a \u0438 \u0432 \u0431\u0438\u043d\u0430\u0440\u043d\u043e\u043c \u0434\u0435\u0440\u0435\u0432\u0435, \u0442\u043e\u043b\u044c\u043a\u043e \u043f\u043e\u0441\u043b\u0435 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u0435 \u043d\u0430\u0434\u043e \u043f\u0440\u043e\u0432\u0435\u0440\u0438\u0442\u044c \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c \u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u043e\u0432\u043a\u0438 \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0438\u0437 \u0443\u0437\u043b\u043e\u0432, \u0438 \u0435\u0441\u043b\u0438 \u043d\u0430\u0434\u043e, \u0442\u043e \u0441\u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u043e\u0432\u0430\u0442\u044c.<\/p>\n<p>&nbsp;<\/p>\n<pre class=\"lang:java decode:true\">\/**\r\n * Created by green on 19.12.15.\r\n *\/\r\n\r\nclass AVL &lt;Key extends Comparable&lt;Key&gt;, Value&gt; {\r\n    public class Node {\r\n        private int h;\r\n        private int balance;\r\n        Key key;\r\n        Value value;\r\n        private Node left, right, father;\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            this.h = 1;\r\n            this.balance = 0;\r\n        }\r\n        public Node next(){\r\n            return getHigherNode(this.key);\r\n        }\r\n        public Node previus(){\r\n            return getLowerNode(this.key);\r\n        }\r\n    }\r\n\r\n    private Node root;\r\n\r\n    \/\/\u0412\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442 \u0431\u043b\u0438\u0436\u0430\u0439\u0449\u0438\u0439 \u0443\u0437\u0435\u043b , \u0431\u043e\u043b\u044c\u0448\u0435 \u0434\u0430\u043d\u043d\u043e\u0433\u043e \u043a\u043b\u044e\u0447\u0430, \r\n\/\/\u0435\u0441\u043b\u0438 \u0443\u0437\u043b\u0430 \u0441 \u0442\u0430\u043a\u0438\u043c \u043a\u043b\u044e\u0447\u043e\u043c \u043d\u0435\u0442, \u0442\u043e \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442 \u0431\u043b\u0438\u0436\u0430\u0439\u0449\u0438\u0439 \u0443\u0437\u0435\u043b, \u0431\u043e\u043b\u044c\u0448\u0435 \u0437\u0430\u0434\u0430\u043d\u043d\u043e\u0433\u043e \u043a\u043b\u044e\u0447\u0430. \r\n\/\/\u0415\u0441\u043b\u0438 \u043d\u0435\u0442 \u0431\u043b\u0438\u0436\u0430\u0439\u0449\u0435\u0433\u043e \u0431\u043e\u043b\u044c\u0448\u0435\u0433\u043e \u043f\u043e\u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044e,\u0447\u0435\u043c \u0437\u0430\u0434\u0430\u043d\u044b\u0439 \u043a\u043b\u044e\u0447, \u0442\u043e \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442 null\r\n    private Node getHigherNode(Key key) {\r\n        Node p = root;\r\n        while (p != null) {\r\n            int cmp = key.compareTo(p.key);\r\n            if (cmp &lt; 0) {\r\n                if (p.left != null)\r\n                    p = p.left;\r\n                else\r\n                    return p;\r\n            } else {\r\n                if (p.right != null) {\r\n                    p = p.right;\r\n                } else {\r\n                    Node father = p.father;\r\n                    Node ch = p;\r\n                    while (father != null &amp;&amp; ch == father.right) {\r\n                        ch = father;\r\n                        father = father.father;\r\n                    }\r\n                    return father;\r\n                }\r\n            }\r\n        }\r\n        return null;\r\n    }\r\n    \/\/\u0412\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442 \u0431\u043b\u0438\u0436\u0430\u0439\u0449\u0438\u0439 \u0443\u0437\u0435\u043b , \u043c\u0435\u043d\u044c\u0448\u0435 \u0434\u0430\u043d\u043d\u043e\u0433\u043e \u043a\u043b\u044e\u0447\u0430, \r\n\/\/\u0435\u0441\u043b\u0438 \u0443\u0437\u043b\u0430 \u0441 \u0442\u0430\u043a\u0438\u043c \u043a\u043b\u044e\u0447\u043e\u043c \u043d\u0435\u0442, \u0442\u043e \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442 \u0431\u043b\u0438\u0436\u0430\u0439\u0449\u0438\u0439 \u0443\u0437\u0435\u043b, \u043c\u0435\u043d\u044c\u0448\u0435 \u0437\u0430\u0434\u0430\u043d\u043d\u043e\u0433\u043e \u043a\u043b\u044e\u0447\u0430. \r\n\/\/\u0415\u0441\u043b\u0438 \u043d\u0435\u0442 \u0431\u043b\u0438\u0436\u0430\u0439\u0449\u0435\u0433\u043e \u0431\u043e\u043b\u044c\u0448\u0435\u0433\u043e \u043f\u043e\u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044e,\u0447\u0435\u043c \u0437\u0430\u0434\u0430\u043d\u044b\u0439 \u043a\u043b\u044e\u0447, \u0442\u043e \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442 null\r\n    private Node getLowerNode(Key key) {\r\n        Node p = root;\r\n        while (p != null) {\r\n            int cmp = key.compareTo(p.key);\r\n            if (cmp &gt; 0) {\r\n                if (p.right != null)\r\n                    p = p.right;\r\n                else\r\n                    return p;\r\n            } else {\r\n                if (p.left != null) {\r\n                    p = p.left;\r\n                } else {\r\n                    Node father = p.father;\r\n                    Node ch = p;\r\n                    while (father != null &amp;&amp; ch == father.left) {\r\n                        ch = father;\r\n                        father = father.father;\r\n                    }\r\n                    return father;\r\n                }\r\n            }\r\n        }\r\n        return null;\r\n    }\r\n\r\n    public Node getFirstNode(){\r\n        return min(root);\r\n    }\r\n\r\n    public Node getLastNode(){\r\n        return max(root);\r\n    }\r\n\r\n    private int height(Node x, Node y){\r\n        if(x == null &amp;&amp; y == null) return 0;\r\n        else if(x == null) return y.h;\r\n        else if(y == null) return x.h;\r\n        else return Math.max(x.h, y.h);\r\n    }\r\n\r\n    private int balance(Node x, Node y){\r\n        if(x == null &amp;&amp; y == null) return 0;\r\n        else if(x == null) return - y.h;\r\n        else if(y == null) return x.h;\r\n        else return x.h - y.h;\r\n    }\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); node.h = height(node.left, node.right) + 1;}\r\n        else if(compareResult &lt; 0){node.left = add(node.left, key, value, node); node.h = height(node.left, node.right) + 1;}\r\n        else{\r\n            node.value = value;\r\n        }\r\n        node.balance = balance(node.left, node.right);\r\n        if(node.balance == -2){\r\n            node = leftRotation(node);\r\n        }else if(node.balance == 2){\r\n            node = rightRotation(node);\r\n        }\r\n        return node;\r\n    }\r\n\r\n    private Node leftRotation(Node node) {\r\n        if(node.right.right == null &amp;&amp; node.right.left != null){\r\n            node.right = rightRotation(node.right);\r\n            node = leftRotation(node);\r\n        }else if(node.right.left == null || node.right.left.h &lt;= node.right.right.h){\r\n            Node newnode = node.right;\r\n            newnode.father = node.father;\r\n            node.right = newnode.left;\r\n            if(node.right != null)\r\n                node.right.father = node;\r\n            node.h = height(node.left, node.right)+1;\r\n            node.father = newnode;\r\n            node.balance = balance(node.left, node.right);\r\n            newnode.left = node;\r\n            node = newnode;\r\n            node.balance = balance(node.left, node.right);\r\n            node.h = height(node.left, node.right)+1;\r\n        }else{\r\n            node.right = rightRotation(node.right);\r\n            node = leftRotation(node);\r\n        }\r\n        return node;\r\n    }\r\n    private Node rightRotation(Node node){\r\n        if(node.left.right != null &amp;&amp; node.left.left == null){\r\n            node.left = leftRotation(node.left);\r\n            node = rightRotation(node);\r\n        }else if(node.left.right == null || node.left.right.h &lt;= node.left.left.h){\r\n            Node newnode = node.left;\r\n            newnode.father = node.father;\r\n            node.left = newnode.right;\r\n            if(node.left != null)\r\n                node.left.father = node;\r\n            node.h = height(node.left, node.right)+1;\r\n            node.father = newnode;\r\n            node.balance = balance(node.left, node.right);\r\n            newnode.right = node;\r\n            node = newnode;\r\n            node.balance = balance(node.left, node.right);\r\n            node.h = height(node.left, node.right)+1;\r\n        }else{\r\n            node.left = leftRotation(node.left);\r\n            node = rightRotation(node);\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, null);\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                node = null;\r\n            }else if(node.right == null){\r\n                node.left.father = node.father;\r\n                node = node.left;\r\n            }else if(node.left == null){\r\n                node.right.father = node.father;\r\n                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                    node.right.father = node.father;\r\n                    node.left.father = node.right;\r\n                    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                }\r\n            }\r\n        }\r\n        if(node != null) {\r\n            node.h = height(node.left, node.right) + 1;\r\n            node.balance = balance(node.left, node.right);\r\n            if (node.balance == -2) {\r\n                node = leftRotation(node);\r\n            } else if (node.balance == 2) {\r\n                node = rightRotation(node);\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+\" h=\"+node.h+\" balance=\"+node.balance);\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 avl_tree {\r\n    public static void main(String[] args){\r\n        AVL&lt;Integer, Integer&gt; tree = new AVL&lt;&gt;();\r\n        tree.add(10,10);\r\n        tree.print();\r\n        tree.add(11,11);\r\n        tree.print();\r\n        tree.add(15,12);\r\n        tree.print();\r\n        tree.add(13,12);\r\n        tree.print();\r\n        tree.add(16,12);\r\n        tree.print();\r\n        tree.add(12,12);\r\n        tree.print();\r\n        tree.add(3,2);\r\n        tree.print();\r\n        tree.add(1,1);\r\n        tree.print();\r\n        tree.add(0,1);\r\n        tree.print();\r\n        tree.add(2,1);\r\n        tree.print();\r\n        tree.delete(13);\r\n        tree.print();\r\n        tree.delete(10);\r\n        tree.print();\r\n        for(AVL.Node e = tree.getFirstNode(); e != null; e = e.next()){\r\n            System.out.println(e.key);\r\n        }\r\n    }\r\n}\r\n<\/pre>\n<p>&nbsp;<\/p>\n<p><a href=\"http:\/\/ideone.com\/0t9pkZ\">\u0421\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 ideone.<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u041e\u043f\u0438\u0441\u0430\u043d\u0438\u0435 \u0410\u0412\u041b-\u0434\u0435\u0440\u0435\u0432\u0430 \u0432\u044b \u043c\u043e\u0436\u0435\u0442\u0435 \u043f\u0440\u043e\u0447\u0438\u0442\u0430\u0442\u044c \u0432 \u0412\u0438\u043a\u0438\u043f\u0435\u0434\u0438\u0438. \u0417\u0434\u0435\u0441\u044c \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d \u043a\u043e\u0434 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u043e\u0433\u043e \u0410\u0412\u041b-\u0434\u0435\u0440\u0435\u0432\u0430. \u041e\u0442\u043b\u0438\u0447\u0430\u0435\u0442\u0441\u044f \u043e\u0442 \u043e\u0431\u044b\u0447\u043d\u043e \u0431\u0438\u043d\u0430\u0440\u043d\u043e\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430 \u0442\u0435\u043c, \u0447\u0442\u043e \u0443 \u0443\u0437\u043b\u043e\u0432 \u0435\u0441\u0442\u044c \u0432\u044b\u0441\u043e\u0442\u0430 \u0438 \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c \u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u043e\u0432\u043a\u0438. \u0411\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u043e\u0432\u043a\u0430 \u043c\u043e\u0436\u0435\u0442 \u043c\u0435\u043d\u044f\u0442\u044c\u0441\u044f \u043f\u0440\u0438 \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u0438 \u0438\u043b\u0438 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u0438, \u0438 \u0432\u043e\u0441\u0441\u0442\u0430\u043d\u0430\u0432\u043b\u0438\u0432\u0430\u0435\u0442\u0441\u044f \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u043c\u0430\u043b\u043e\u0433\u043e \u043b\u0435\u0432\u043e\u0433\u043e(\u043f\u0440\u0430\u0432\u043e\u0433\u043e), \u0438\u043b\u0438 \u0431\u043e\u043b\u044c\u0448\u043e\u0433\u043e \u043b\u0435\u0432\u043e\u0433\u043e(\u043f\u0440\u0430\u0432\u043e\u0433\u043e) \u043f\u043e\u0432\u043e\u0440\u043e\u0442\u043e\u0432. \u041a\u0430\u043a \u044d\u0442\u043e \u0432\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u043c\u043e\u0436\u043d\u043e \u0443\u0432\u0438\u0434\u0435\u0442\u044c \u0432 \u0442\u043e\u0439 \u0436\u0435 \u0412\u0438\u043a\u0438\u043f\u0435\u0434\u0438\u0438. \u041f\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c \u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u043e\u0432\u043a\u0438 &hellip; <a href=\"https:\/\/java.mazurok.com\/?p=505\" 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":[49],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/java.mazurok.com\/index.php?rest_route=\/wp\/v2\/posts\/505"}],"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=505"}],"version-history":[{"count":6,"href":"https:\/\/java.mazurok.com\/index.php?rest_route=\/wp\/v2\/posts\/505\/revisions"}],"predecessor-version":[{"id":540,"href":"https:\/\/java.mazurok.com\/index.php?rest_route=\/wp\/v2\/posts\/505\/revisions\/540"}],"wp:attachment":[{"href":"https:\/\/java.mazurok.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=505"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/java.mazurok.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=505"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/java.mazurok.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=505"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}