{"id":316604,"date":"2021-01-19T15:00:42","date_gmt":"2021-01-19T15:00:42","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=316604"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=316604","title":{"rendered":"Splay-\u0434\u0435\u0440\u0435\u0432\u043e. \u0412\u0441\u0442\u0430\u0432\u043a\u0430"},"content":{"rendered":"\n<div class=\"post__text post__text_v2\" id=\"post-content-body\">\n<blockquote>\n<p>\u041f\u0440\u0438\u0432\u0435\u0442, \u0445\u0430\u0431\u0440\u043e\u0432\u0447\u0430\u043d\u0435. \u0412 \u043f\u0440\u0435\u0434\u0434\u0432\u0435\u0440\u0438\u0438 \u0441\u0442\u0430\u0440\u0442\u0430 \u043a\u0443\u0440\u0441\u0430 <a href=\"https:\/\/otus.pw\/Zwdi\/\">\u00ab\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u0438 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0434\u0430\u043d\u043d\u044b\u0445\u00bb<\/a> \u043f\u0440\u0438\u0433\u043b\u0430\u0448\u0430\u0435\u043c \u0431\u0443\u0434\u0443\u0449\u0438\u0445 \u0441\u0442\u0443\u0434\u0435\u043d\u0442\u043e\u0432 \u0438 \u0432\u0441\u0435\u0445 \u0436\u0435\u043b\u0430\u044e\u0449\u0438\u0445 \u043d\u0430 \u043e\u0442\u043a\u0440\u044b\u0442\u044b\u0439 \u0443\u0440\u043e\u043a \u043f\u043e \u0442\u0435\u043c\u0435 <a href=\"https:\/\/otus.pw\/JTu7\/\">\u00ab\u0417\u0430\u043f\u043e\u0432\u0435\u0434\u043d\u0438\u043a\u0438 \u0434\u0432\u043e\u0438\u0447\u043d\u044b\u0445 \u0434\u0435\u0440\u0435\u0432\u044c\u0435\u0432 \u043f\u043e\u0438\u0441\u043a\u0430\u00bb.<\/a><\/p>\n<p>\u0422\u0430\u043a\u0436\u0435 \u0434\u0435\u043b\u0438\u043c\u0441\u044f \u0442\u0440\u0430\u0434\u0438\u0446\u0438\u043e\u043d\u043d\u044b\u043c \u043f\u043e\u043b\u0435\u0437\u043d\u044b\u043c \u043f\u0435\u0440\u0435\u0432\u043e\u0434\u043e\u043c.<\/p>\n<\/blockquote>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/fdf\/98b\/6d2\/fdf98b6d2867a31634a293d5432073c9\" width=\"780\" height=\"439\"><figcaption><\/figcaption><\/figure>\n<\/p>\n<hr>\n<p><strong><em>\u041f\u0435\u0440\u0435\u0434 \u043f\u0440\u043e\u0447\u0442\u0435\u043d\u0438\u0435\u043c \u044d\u0442\u043e\u0439 \u0441\u0442\u0430\u0442\u044c\u0438 \u043d\u0430\u0441\u0442\u043e\u044f\u0442\u0435\u043b\u044c\u043d\u043e \u0440\u0435\u043a\u043e\u043c\u0435\u043d\u0434\u0443\u0435\u0442\u0441\u044f \u043e\u0437\u043d\u0430\u043a\u043e\u043c\u0438\u0442\u044c\u0441\u044f \u0441 \u043f\u0435\u0440\u0432\u043e\u0439 \u0447\u0430\u0441\u0442\u044c\u044e: <\/em><\/strong><a href=\"https:\/\/habr.com\/ru\/company\/otus\/blog\/535316\/\"><strong><em><u>Splay-\u0434\u0435\u0440\u0435\u0432\u043e. \u041f\u043e\u0438\u0441\u043a<\/u><\/em><\/strong><\/a><\/p>\n<p>\u041a\u0430\u043a \u0443\u043f\u043e\u043c\u0438\u043d\u0430\u043b\u043e\u0441\u044c \u0432 <a href=\"https:\/\/habr.com\/ru\/company\/otus\/blog\/535316\/\"><u>\u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0435\u0439 \u0441\u0442\u0430\u0442\u044c\u0435<\/u><\/a>, Splay-\u0434\u0435\u0440\u0435\u0432\u043e \u2014 \u044d\u0442\u043e \u0441\u0430\u043c\u043e\u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u0443\u044e\u0449\u0430\u044f\u0441\u044f \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u0434\u0430\u043d\u043d\u044b\u0445, \u0432 \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0438\u0439 \u043a\u043b\u044e\u0447, \u043a \u043a\u043e\u0442\u043e\u0440\u043e\u043c\u0443 \u043e\u0441\u0443\u0449\u0435\u0441\u0442\u0432\u043b\u044f\u043b\u0441\u044f \u0434\u043e\u0441\u0442\u0443\u043f, \u0432\u0441\u0435\u0433\u0434\u0430 \u043f\u043e\u043c\u0435\u0449\u0430\u0435\u0442\u0441\u044f \u0432 \u043a\u043e\u0440\u0435\u043d\u044c. \u041e\u043f\u0435\u0440\u0430\u0446\u0438\u044f \u0432\u0441\u0442\u0430\u0432\u043a\u0438 \u0430\u043d\u0430\u043b\u043e\u0433\u0438\u0447\u043d\u0430 \u0432\u0441\u0442\u0430\u0432\u043a\u0435 \u0432 \u0431\u0438\u043d\u0430\u0440\u043d\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e \u043f\u043e\u0438\u0441\u043a\u0430 \u0441 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u0438\u043c\u0438 \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u043c\u0438 \u0448\u0430\u0433\u0430\u043c\u0438, \u0446\u0435\u043b\u044c \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0443\u0431\u0435\u0434\u0438\u0442\u044c\u0441\u044f, \u0447\u0442\u043e \u0432\u043d\u043e\u0432\u044c \u0432\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u043d\u044b\u0439 \u043a\u043b\u044e\u0447 \u0441\u0442\u0430\u043d\u043e\u0432\u0438\u0442\u0441\u044f \u043d\u043e\u0432\u044b\u043c \u043a\u043e\u0440\u043d\u0435\u043c.<\/p>\n<p>\u041d\u0438\u0436\u0435 \u043f\u0440\u0438\u0432\u0435\u0434\u0435\u043d\u044b \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u0435 \u0441\u043b\u0443\u0447\u0430\u0438 \u043f\u0440\u0438 \u0432\u0441\u0442\u0430\u0432\u043a\u0435 \u043a\u043b\u044e\u0447\u0430 k \u0432 Splay-\u0434\u0435\u0440\u0435\u0432\u043e.<\/p>\n<p><strong>1)<\/strong> \u041a\u043e\u0440\u0435\u043d\u044c \u0440\u0430\u0432\u0435\u043d NULL: \u043c\u044b \u043f\u0440\u043e\u0441\u0442\u043e \u0441\u043e\u0437\u0434\u0430\u0435\u043c \u043d\u043e\u0432\u044b\u0439 \u0443\u0437\u0435\u043b \u0438 \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u043c \u0435\u0433\u043e \u043a\u0430\u043a \u043a\u043e\u0440\u043d\u0435\u0432\u043e\u0439.<\/p>\n<p><strong>2) <\/strong>\u0412\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u043c \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044e <a href=\"https:\/\/habr.com\/ru\/company\/otus\/blog\/535316\/\"><u>Splay<\/u><\/a> \u043d\u0430\u0434 \u0437\u0430\u0434\u0430\u043d\u043d\u044b\u0439 \u043a\u043b\u044e\u0447\u043e\u043c k. \u0415\u0441\u043b\u0438 k \u0443\u0436\u0435 \u043f\u0440\u0438\u0441\u0443\u0442\u0441\u0442\u0432\u0443\u0435\u0442, \u043e\u043d \u0441\u0442\u0430\u043d\u043e\u0432\u0438\u0442\u0441\u044f \u043d\u043e\u0432\u044b\u043c \u043a\u043e\u0440\u043d\u0435\u043c. \u0415\u0441\u043b\u0438 \u043e\u043d \u043e\u0442\u0441\u0443\u0442\u0441\u0442\u0432\u0443\u0435\u0442, \u0442\u043e \u043d\u043e\u0432\u044b\u043c \u043a\u043e\u0440\u043d\u0435\u0432\u044b\u043c \u0443\u0437\u043b\u043e\u043c \u0441\u0442\u0430\u043d\u043e\u0432\u0438\u0442\u0441\u044f \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0438\u0439 \u0443\u0437\u0435\u043b-\u043b\u0438\u0441\u0442, \u043a \u043a\u043e\u0442\u043e\u0440\u043e\u043c\u0443 \u0431\u044b\u043b \u043e\u0441\u0443\u0449\u0435\u0441\u0442\u0432\u043b\u0435\u043d \u0434\u043e\u0441\u0442\u0443\u043f.<\/p>\n<p><strong>3)<\/strong> \u0415\u0441\u043b\u0438 \u043d\u043e\u0432\u044b\u0439 \u043a\u043e\u0440\u043d\u0435\u0432\u043e\u0439 \u043a\u043b\u044e\u0447 \u0442\u0430\u043a\u043e\u0439 \u0436\u0435, \u043a\u0430\u043a k, \u043d\u0438\u0447\u0435\u0433\u043e \u043d\u0435 \u0434\u0435\u043b\u0430\u0435\u043c, \u043f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 k \u0443\u0436\u0435 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442.<\/p>\n<p><strong>4) <\/strong>\u0412 \u043f\u0440\u043e\u0442\u0438\u0432\u043d\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u0432\u044b\u0434\u0435\u043b\u044f\u0435\u043c \u043f\u0430\u043c\u044f\u0442\u044c \u0434\u043b\u044f \u043d\u043e\u0432\u043e\u0433\u043e \u0443\u0437\u043b\u0430 \u0438 \u0441\u0440\u0430\u0432\u043d\u0438\u0432\u0430\u0435\u043c \u043a\u043e\u0440\u043d\u0435\u0432\u043e\u0439 \u043a\u043b\u044e\u0447 \u0441 k.<\/p>\n<p>      <strong>4.a)<\/strong> \u0415\u0441\u043b\u0438 k \u043c\u0435\u043d\u044c\u0448\u0435 \u043a\u043e\u0440\u043d\u0435\u0432\u043e\u0433\u043e \u043a\u043b\u044e\u0447\u0430, \u0434\u0435\u043b\u0430\u0435\u043c \u043a\u043e\u0440\u0435\u043d\u044c \u043f\u0440\u0430\u0432\u044b\u043c \u0434\u043e\u0447\u0435\u0440\u043d\u0438\u043c \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u043c \u043d\u043e\u0432\u043e\u0433\u043e \u0443\u0437\u043b\u0430, \u043a\u043e\u043f\u0438\u0440\u0443\u0435\u043c \u043b\u0435\u0432\u044b\u0439 \u0434\u043e\u0447\u0435\u0440\u043d\u0438\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u043a\u043e\u0440\u043d\u044f \u0432 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u043b\u0435\u0432\u043e\u0433\u043e \u0434\u043e\u0447\u0435\u0440\u043d\u0435\u0433\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u043d\u043e\u0432\u043e\u0433\u043e \u0443\u0437\u043b\u0430 \u0438 \u0434\u0435\u043b\u0430\u0435\u043c \u043b\u0435\u0432\u044b\u0439 \u0434\u043e\u0447\u0435\u0440\u043d\u0438\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u043a\u043e\u0440\u043d\u044f \u0440\u0430\u0432\u043d\u044b\u043c NULL.<\/p>\n<p>      <strong>4.b)<\/strong> \u0415\u0441\u043b\u0438 k \u0431\u043e\u043b\u044c\u0448\u0435 \u043a\u043e\u0440\u043d\u0435\u0432\u043e\u0433\u043e \u043a\u043b\u044e\u0447\u0430, \u0434\u0435\u043b\u0430\u0435\u043c \u043a\u043e\u0440\u0435\u043d\u044c \u043b\u0435\u0432\u044b\u043c \u0434\u043e\u0447\u0435\u0440\u043d\u0438\u043c \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u043c \u043d\u043e\u0432\u043e\u0433\u043e \u0443\u0437\u043b\u0430, \u043a\u043e\u043f\u0438\u0440\u0443\u0435\u043c \u043f\u0440\u0430\u0432\u044b\u0439 \u0434\u043e\u0447\u0435\u0440\u043d\u0438\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u043a\u043e\u0440\u043d\u044f \u0432 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u043f\u0440\u0430\u0432\u043e\u0433\u043e \u0434\u043e\u0447\u0435\u0440\u043d\u0435\u0433\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u043d\u043e\u0432\u043e\u0433\u043e \u0443\u0437\u043b\u0430 \u0438 \u0434\u0435\u043b\u0430\u0435\u043c \u043f\u0440\u0430\u0432\u044b\u0439 \u0434\u043e\u0447\u0435\u0440\u043d\u0438\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u043a\u043e\u0440\u043d\u044f \u0440\u0430\u0432\u043d\u044b\u043c NULL.<\/p>\n<p><strong>5)<\/strong> \u0412\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u043c \u043d\u043e\u0432\u044b\u0439 \u0443\u0437\u0435\u043b \u0432 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u043d\u043e\u0432\u043e\u0433\u043e \u043a\u043e\u0440\u043d\u044f \u0434\u0435\u0440\u0435\u0432\u0430.<\/p>\n<p><strong>\u041f\u0440\u0438\u043c\u0435\u0440:<\/strong><\/p>\n<pre><code>           100                  [20]                             25                \/  \\                   \\                             \/  \\         50   200                  50                          20   50         \/          insert(25)     \/  \\        insert(25)           \/  \\         40          ======&gt;      30   100      ========&gt;           30  100          \/          1. Splay(25)    \\     \\      2. insert 25         \\    \\     30                          40    200                         40   200       \/                                                            [20] <\/code><\/pre>\n<h3>\u0421++<\/h3>\n<pre><code class=\"cpp\">#include &lt;bits\/stdc++.h&gt; using namespace std;    \/\/ \u0423\u0437\u0435\u043b \u0410\u0412\u041b-\u0434\u0435\u0440\u0435\u0432\u0430 class node  {      public:     int key;      node *left, *right;  };     \/* \u0412\u0441\u043f\u043e\u043c\u043e\u0433\u0430\u0442\u0435\u043b\u044c\u043d\u0430\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u044f, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0432\u044b\u0434\u0435\u043b\u044f\u0435\u0442  \u043d\u043e\u0432\u044b\u0439 \u0443\u0437\u0435\u043b \u0441 \u0437\u0430\u0434\u0430\u043d\u043d\u044b\u043c key \u0438 left \u0438 right, \u0443\u043a\u0430\u0437\u044b\u0432\u0430\u044e\u0449\u0438\u043c\u0438 \u0432 NULL. *\/ node* newNode(int key)  {      node* Node = new node();     Node-&gt;key = key;      Node-&gt;left = Node-&gt;right = NULL;      return (Node);  }     \/\/ \u0421\u043b\u0443\u0436\u0435\u0431\u043d\u0430\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u0434\u043b\u044f \u0440\u0430\u0437\u0432\u043e\u0440\u043e\u0442\u0430 \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u0430 \u0441 \u043a\u043e\u0440\u043d\u0435\u043c y \u0432\u043f\u0440\u0430\u0432\u043e. \/\/ \u0421\u043c\u043e\u0442\u0440\u0438\u0442\u0435 \u0434\u0438\u0430\u0433\u0440\u0430\u043c\u043c\u0443, \u043f\u0440\u0438\u0432\u0435\u0434\u0435\u043d\u043d\u0443\u044e \u0432\u044b\u0448\u0435. node *rightRotate(node *x)  {      node *y = x-&gt;left;      x-&gt;left = y-&gt;right;      y-&gt;right = x;      return y;  }     \/\/ \u0421\u043b\u0443\u0436\u0435\u0431\u043d\u0430\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u0434\u043b\u044f \u0440\u0430\u0437\u0432\u043e\u0440\u043e\u0442\u0430 \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u0430 \u0441 \u043a\u043e\u0440\u043d\u0435\u043c x \u0432\u043b\u0435\u0432\u043e  \/\/ \u0421\u043c\u043e\u0442\u0440\u0438\u0442\u0435 \u0434\u0438\u0430\u0433\u0440\u0430\u043c\u043c\u0443, \u043f\u0440\u0438\u0432\u0435\u0434\u0435\u043d\u043d\u0443\u044e \u0432\u044b\u0448\u0435.  node *leftRotate(node *x)  {      node *y = x-&gt;right;      x-&gt;right = y-&gt;left;      y-&gt;left = x;      return y;  }     \/\/ \u042d\u0442\u0430 \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u043f\u043e\u0434\u043d\u0438\u043c\u0435\u0442 \u043a\u043b\u044e\u0447 \/\/ \u0432 \u043a\u043e\u0440\u0435\u043d\u044c, \u0435\u0441\u043b\u0438 \u043e\u043d \u043f\u0440\u0438\u0441\u0443\u0442\u0441\u0442\u0432\u0443\u0435\u0442 \u0432 \u0434\u0435\u0440\u0435\u0432\u0435.  \/\/ \u0415\u0441\u043b\u0438 \u0442\u0430\u043a\u043e\u0439 \u043a\u043b\u044e\u0447 \u043e\u0442\u0441\u0443\u0442\u0441\u0442\u0432\u0443\u0435\u0442 \u0432 \u0434\u0435\u0440\u0435\u0432\u0435, \u043e\u043d\u0430 \/\/ \u043f\u043e\u0434\u043d\u0438\u043c\u0435\u0442 \u0432 \u043a\u043e\u0440\u0435\u043d\u044c \u0441\u0430\u043c\u044b\u0439 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0438\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442, \/\/ \u043a \u043a\u043e\u0442\u043e\u0440\u043e\u043c\u0443 \u0431\u044b\u043b \u043e\u0441\u0443\u0449\u0435\u0441\u0442\u0432\u043b\u0435\u043d \u0434\u043e\u0441\u0442\u0443\u043f. \/\/ \u042d\u0442\u0430 \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u0438\u0437\u043c\u0435\u043d\u044f\u0435\u0442 \u0434\u0435\u0440\u0435\u0432\u043e \/\/ \u0438 \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442 \u043d\u043e\u0432\u044b\u0439 \u043a\u043e\u0440\u0435\u043d\u044c (root). node *splay(node *root, int key)  {      \/\/ \u0411\u0430\u0437\u043e\u0432\u044b\u0435 \u0441\u043b\u0443\u0447\u0430\u0438: root \u0440\u0430\u0432\u0435\u043d NULL \u0438\u043b\u0438     \/\/ \u043a\u043b\u044e\u0447 \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u0441\u044f \u0432 \u043a\u043e\u0440\u043d\u0435     if (root == NULL || root-&gt;key == key)          return root;         \/\/ \u041a\u043b\u044e\u0447 \u043b\u0435\u0436\u0438\u0442 \u0432 \u043b\u0435\u0432\u043e\u043c \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u0435     if (root-&gt;key &gt; key)      {          \/\/ \u041a\u043b\u044e\u0447\u0430 \u043d\u0435\u0442 \u0432 \u0434\u0435\u0440\u0435\u0432\u0435, \u043c\u044b \u0437\u0430\u043a\u043e\u043d\u0447\u0438\u043b\u0438         if (root-&gt;left == NULL) return root;             \/\/ Zig-Zig (\u041b\u0435\u0432\u044b\u0439-\u043b\u0435\u0432\u044b\u0439)         if (root-&gt;left-&gt;key &gt; key)          {              \/\/ \u0421\u043d\u0430\u0447\u0430\u043b\u0430 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u043e \u043f\u043e\u0434\u043d\u0438\u043c\u0435\u043c              \/\/ \u043a\u043b\u044e\u0447 \u0432 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u043a\u043e\u0440\u043d\u044f left-left             root-&gt;left-&gt;left = splay(root-&gt;left-&gt;left, key);                 \/\/ \u041f\u0435\u0440\u0432\u044b\u0439 \u0440\u0430\u0437\u0432\u043e\u0440\u043e\u0442 \u0434\u043b\u044f root,               \/\/ \u0432\u0442\u043e\u0440\u043e\u0439 \u0440\u0430\u0437\u0432\u043e\u0440\u043e\u0442 \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442\u0441\u044f \u043f\u043e\u0441\u043b\u0435 else              root = rightRotate(root);          }          else if (root-&gt;left-&gt;key &lt; key) \/\/ Zig-Zag (Left Right)          {              \/\/ \u0421\u043d\u0430\u0447\u0430\u043b\u0430 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u043e \u043f\u043e\u0434\u043d\u0438\u043c\u0430\u0435\u043c              \/\/ \u043a\u043b\u044e\u0447 \u0432 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u043a\u043e\u0440\u0435\u043d\u044f left-right             root-&gt;left-&gt;right = splay(root-&gt;left-&gt;right, key);                 \/\/ \u0412\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u043c \u043f\u0435\u0440\u0432\u044b\u0439 \u0440\u0430\u0437\u0432\u043e\u0440\u043e\u0442 \u0434\u043b\u044f root-&gt;left             if (root-&gt;left-&gt;right != NULL)                  root-&gt;left = leftRotate(root-&gt;left);          }             \/\/ \u0412\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u043c \u0432\u0442\u043e\u0440\u043e\u0439 \u0440\u0430\u0437\u0432\u043e\u0440\u043e\u0442 \u0434\u043b\u044f \u043a\u043e\u0440\u043d\u044f         return (root-&gt;left == NULL)? root: rightRotate(root);      }      else \/\/ \u041a\u043b\u044e\u0447 \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u0441\u044f \u0432 \u043f\u0440\u0430\u0432\u043e\u043c \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u0435     {          \/\/ \u041a\u043b\u044e\u0447\u0430 \u043d\u0435\u0442 \u0432 \u0434\u0435\u0440\u0435\u0432\u0435, \u043c\u044b \u0437\u0430\u043a\u043e\u043d\u0447\u0438\u043b\u0438         if (root-&gt;right == NULL) return root;             \/\/ Zag-Zig (\u041f\u0440\u0430\u0432\u044b\u0439-\u043b\u0435\u0432\u044b\u0439)         if (root-&gt;right-&gt;key &gt; key)          {              \/\/ \u041f\u043e\u0434\u043d\u044f\u0442\u044c \u043a\u043b\u044e\u0447 \u0432 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u043a\u043e\u0440\u0435\u043d\u044f right-left             root-&gt;right-&gt;left = splay(root-&gt;right-&gt;left, key);                 \/\/ \u0412\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u043c \u043f\u0435\u0440\u0432\u044b\u0439 \u043f\u043e\u0432\u043e\u0440\u043e\u0442 \u0434\u043b\u044f root-&gt;right             if (root-&gt;right-&gt;left != NULL)                  root-&gt;right = rightRotate(root-&gt;right);          }          else if (root-&gt;right-&gt;key &lt; key)\/\/ Zag-Zag (\u041f\u0440\u0430\u0432\u044b\u0439-\u043f\u0440\u0430\u0432\u044b\u0439)          {              \/\/ \u041f\u043e\u0434\u043d\u0438\u043c\u0430\u0435\u043c \u043a\u043b\u044e\u0447 \u0432 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u043a\u043e\u0440\u043d\u044f               \/\/ right-right \u0438 \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u043c \u043f\u0435\u0440\u0432\u044b\u0439 \u0440\u0430\u0437\u0432\u043e\u0440\u043e\u0442             root-&gt;right-&gt;right = splay(root-&gt;right-&gt;right, key);              root = leftRotate(root);          }             \/\/ \u0412\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u043c \u0432\u0442\u043e\u0440\u043e\u0439 \u0440\u0430\u0437\u0432\u043e\u0440\u043e\u0442 \u0434\u043b\u044f root         return (root-&gt;right == NULL)? root: leftRotate(root);      }  }     \/\/ \u0424\u0443\u043d\u043a\u0446\u0438\u044f \u0434\u043b\u044f \u0432\u0441\u0442\u0430\u0432\u043a\u0438 \u043d\u043e\u0432\u043e\u0433\u043e \u043a\u043b\u044e\u0447\u0430 k \u0432 splay-\u0434\u0435\u0440\u0435\u0432\u043e \u0441 \u0437\u0430\u0434\u0430\u043d\u043d\u044b\u043c \u043a\u043e\u0440\u043d\u0435\u043c node *insert(node *root, int k)  {      \/\/ \u041f\u0440\u043e\u0441\u0442\u043e\u0439 \u0441\u043b\u0443\u0447\u0430\u0439: \u0435\u0441\u043b\u0438 \u0434\u0435\u0440\u0435\u0432\u043e \u043f\u0443\u0441\u0442\u043e     if (root == NULL) return newNode(k);         \/\/ \u0414\u0435\u043b\u0430\u0435\u043c \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0439 \u0443\u0437\u0435\u043b-\u043b\u0438\u0441\u0442 \u043a\u043e\u0440\u043d\u0435\u043c      root = splay(root, k);         \/\/ \u0415\u0441\u043b\u0438 \u043a\u043b\u044e\u0447 \u0443\u0436\u0435 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442, \u0442\u043e \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u043c \u0435\u0433\u043e     if (root-&gt;key == k) return root;         \/\/ \u0412 \u043f\u0440\u043e\u0442\u0438\u0432\u043d\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u0432\u044b\u0434\u0435\u043b\u044f\u0435\u043c \u043f\u0430\u043c\u044f\u0442\u044c \u043f\u043e\u0434 \u043d\u043e\u0432\u044b\u0439 \u0443\u0437\u0435\u043b     node *newnode = newNode(k);         \/\/ \u0415\u0441\u043b\u0438 \u043a\u043e\u0440\u043d\u0435\u0432\u043e\u0439 \u043a\u043b\u044e\u0447 \u0431\u043e\u043b\u044c\u0448\u0435, \u0434\u0435\u043b\u0430\u0435\u043c \u043a\u043e\u0440\u0435\u043d\u044c \u043f\u0440\u0430\u0432\u044b\u043c \u0434\u043e\u0447\u0435\u0440\u043d\u0438\u043c \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u043c \u043d\u043e\u0432\u043e\u0433\u043e \u0443\u0437\u043b\u0430, \u043a\u043e\u043f\u0438\u0440\u0443\u0435\u043c \u043b\u0435\u0432\u044b\u0439 \u0434\u043e\u0447\u0435\u0440\u043d\u0438\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u043a\u043e\u0440\u043d\u044f \u0432 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u043b\u0435\u0432\u043e\u0433\u043e \u0434\u043e\u0447\u0435\u0440\u043d\u0435\u0433\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u043d\u043e\u0432\u043e\u0433\u043e \u0443\u0437\u043b\u0430     if (root-&gt;key &gt; k)      {          newnode-&gt;right = root;          newnode-&gt;left = root-&gt;left;          root-&gt;left = NULL;      }         \/\/ \u0415\u0441\u043b\u0438 \u043a\u043e\u0440\u043d\u0435\u0432\u043e\u0439 \u043a\u043b\u044e\u0447 \u043c\u0435\u043d\u044c\u0448\u0435, \u0434\u0435\u043b\u0430\u0435\u043c \u043a\u043e\u0440\u0435\u043d\u044c \u043b\u0435\u0432\u044b\u043c \u0434\u043e\u0447\u0435\u0440\u043d\u0438\u043c \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u043c \u043d\u043e\u0432\u043e\u0433\u043e \u0443\u0437\u043b\u0430, \u043a\u043e\u043f\u0438\u0440\u0443\u0435\u043c \u043f\u0440\u0430\u0432\u044b\u0439 \u0434\u043e\u0447\u0435\u0440\u043d\u0438\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u043a\u043e\u0440\u043d\u044f \u0432 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u043f\u0440\u0430\u0432\u043e\u0433\u043e \u0434\u043e\u0447\u0435\u0440\u043d\u0435\u0433\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u043d\u043e\u0432\u043e\u0433\u043e \u0443\u0437\u043b\u0430     else     {          newnode-&gt;left = root;          newnode-&gt;right = root-&gt;right;          root-&gt;right = NULL;      }         return newnode; \/\/ \u043d\u043e\u0432\u044b\u0439 \u0443\u0437\u0435\u043b \u0441\u0442\u0430\u043d\u043e\u0432\u0438\u0442\u0441\u044f \u043d\u043e\u0432\u044b\u043c \u043a\u043e\u0440\u043d\u0435\u043c }     \/\/ \u0421\u043b\u0443\u0436\u0435\u0431\u043d\u0430\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u0434\u043b\u044f \u0432\u044b\u0432\u043e\u0434\u0430  \/\/ \u043e\u0431\u0445\u043e\u0434\u0430 \u0432 \u0434\u0435\u0440\u0435\u0432\u0430 \u0448\u0438\u0440\u0438\u043d\u0443.  \/\/ \u0424\u0443\u043d\u043a\u0446\u0438\u044f \u0442\u0430\u043a\u0436\u0435 \u0432\u044b\u0432\u043e\u0434\u0438\u0442 \u0432\u044b\u0441\u043e\u0442\u0443 \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0443\u0437\u043b\u0430 void preOrder(node *root)  {      if (root != NULL)      {          cout&lt;&lt;root-&gt;key&lt;&lt;\" \";          preOrder(root-&gt;left);          preOrder(root-&gt;right);      }  }     \/* \u0423\u043f\u0440\u0430\u0432\u043b\u044f\u044e\u0449\u0438\u0439 \u043a\u043e\u0434 *\/ int main()  {      node *root = newNode(100);      root-&gt;left = newNode(50);      root-&gt;right = newNode(200);      root-&gt;left-&gt;left = newNode(40);      root-&gt;left-&gt;left-&gt;left = newNode(30);      root-&gt;left-&gt;left-&gt;left-&gt;left = newNode(20);      root = insert(root, 25);      cout&lt;&lt;\"Preorder traversal of the modified Splay tree is \\n\";      preOrder(root);      return 0;  }     \/\/ \u042d\u0442\u043e\u0442 \u043a\u043e\u0434 \u043b\u044e\u0431\u0435\u0437\u043d\u043e \u043f\u0440\u0435\u0434\u043e\u0441\u0442\u0430\u0432\u043b\u0435\u043d rathbhupendra <\/code><\/pre>\n<h3>C<\/h3>\n<pre><code class=\"cpp\">\/\/ \u041a\u043e\u0434 \u043f\u043e\u0437\u0430\u0438\u043c\u0441\u0442\u0432\u043e\u0432\u0430\u043d c http:\/\/algs4.cs.princeton.edu\/33balanced\/SplayBST.java.html #include&lt;stdio.h&gt; #include&lt;stdlib.h&gt;    \/\/ \u0423\u0437\u0435\u043b \u0410\u0412\u041b-\u0434\u0435\u0440\u0435\u0432\u0430 struct node {     int key;     struct node *left, *right; };    \/* \u0412\u0441\u043f\u043e\u043c\u043e\u0433\u0430\u0442\u0435\u043b\u044c\u043d\u0430\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u044f, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0441\u043e\u0437\u0434\u0430\u0435\u0442  \u043d\u043e\u0432\u044b\u0439 \u0443\u0437\u0435\u043b \u0441 \u0437\u0430\u0434\u0430\u043d\u043d\u044b\u043c key \u0438 left \u0438 right, \u0443\u043a\u0430\u0437\u044b\u0432\u0430\u044e\u0449\u0438\u043c\u0438 \u0432 NULL. *\/ struct node* newNode(int key) {     struct node* node = (struct node*)malloc(sizeof(struct node));     node-&gt;key   = key;     node-&gt;left  = node-&gt;right  = NULL;     return (node); }    \/\/ \u0421\u043b\u0443\u0436\u0435\u0431\u043d\u0430\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u0434\u043b\u044f \u0440\u0430\u0437\u0432\u043e\u0440\u043e\u0442\u0430 \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u0430 \u0441 \u043a\u043e\u0440\u043d\u0435\u043c y \u0432\u043f\u0440\u0430\u0432\u043e. \/\/ \u0421\u043c\u043e\u0442\u0440\u0438\u0442\u0435 \u0434\u0438\u0430\u0433\u0440\u0430\u043c\u043c\u0443, \u043f\u0440\u0438\u0432\u0435\u0434\u0435\u043d\u043d\u0443\u044e \u0432\u044b\u0448\u0435. struct node *rightRotate(struct node *x) {     struct node *y = x-&gt;left;     x-&gt;left = y-&gt;right;     y-&gt;right = x;     return y; }    \/\/ \u0421\u043b\u0443\u0436\u0435\u0431\u043d\u0430\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u0434\u043b\u044f \u0440\u0430\u0437\u0432\u043e\u0440\u043e\u0442\u0430 \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u0430 \u0441 \u043a\u043e\u0440\u043d\u0435\u043c x \u0432\u043b\u0435\u0432\u043e  \/\/ \u0421\u043c\u043e\u0442\u0440\u0438\u0442\u0435 \u0434\u0438\u0430\u0433\u0440\u0430\u043c\u043c\u0443, \u043f\u0440\u0438\u0432\u0435\u0434\u0435\u043d\u043d\u0443\u044e \u0432\u044b\u0448\u0435.  struct node *leftRotate(struct node *x) {     struct node *y = x-&gt;right;     x-&gt;right = y-&gt;left;     y-&gt;left = x;     return y; }    \/\/ \u042d\u0442\u0430 \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u043f\u043e\u0434\u043d\u0438\u043c\u0435\u0442 \u043a\u043b\u044e\u0447 \/\/ \u0432 \u043a\u043e\u0440\u0435\u043d\u044c, \u0435\u0441\u043b\u0438 \u043e\u043d \u043f\u0440\u0438\u0441\u0443\u0442\u0441\u0442\u0432\u0443\u0435\u0442 \u0432 \u0434\u0435\u0440\u0435\u0432\u0435.  \/\/ \u0415\u0441\u043b\u0438 \u0442\u0430\u043a\u043e\u0439 \u043a\u043b\u044e\u0447 \u043e\u0442\u0441\u0443\u0442\u0441\u0442\u0432\u0443\u0435\u0442 \u0432 \u0434\u0435\u0440\u0435\u0432\u0435, \u043e\u043d\u0430 \/\/ \u043f\u043e\u0434\u043d\u0438\u043c\u0435\u0442 \u0432 \u043a\u043e\u0440\u0435\u043d\u044c \u0441\u0430\u043c\u044b\u0439 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0438\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442, \/\/ \u043a \u043a\u043e\u0442\u043e\u0440\u043e\u043c\u0443 \u0431\u044b\u043b \u043e\u0441\u0443\u0449\u0435\u0441\u0442\u0432\u043b\u0435\u043d \u0434\u043e\u0441\u0442\u0443\u043f. \/\/ \u042d\u0442\u0430 \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u0438\u0437\u043c\u0435\u043d\u044f\u0435\u0442 \u0434\u0435\u0440\u0435\u0432\u043e \/\/ \u0438 \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442 \u043d\u043e\u0432\u044b\u0439 \u043a\u043e\u0440\u0435\u043d\u044c. struct node *splay(struct node *root, int key) {     \/\/ \u0411\u0430\u0437\u043e\u0432\u044b\u0435 \u0441\u043b\u0443\u0447\u0430\u0438: \u043a\u043e\u0440\u0435\u043d\u044c \u0440\u0430\u0432\u0435\u043d NULL \u0438\u043b\u0438     \/\/ \u043a\u043b\u044e\u0447 \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u0441\u044f \u0432 \u043a\u043e\u0440\u043d\u0435     if (root == NULL || root-&gt;key == key)         return root;        \/\/ \u041a\u043b\u044e\u0447 \u043b\u0435\u0436\u0438\u0442 \u0432 \u043b\u0435\u0432\u043e\u043c \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u0435     if (root-&gt;key &gt; key)     {         \/\/ \u041a\u043b\u044e\u0447\u0430 \u043d\u0435\u0442 \u0432 \u0434\u0435\u0440\u0435\u0432\u0435, \u043c\u044b \u0437\u0430\u043a\u043e\u043d\u0447\u0438\u043b\u0438         if (root-&gt;left == NULL) return root;            \/\/ Zig-Zig (\u041b\u0435\u0432\u044b\u0439-\u043b\u0435\u0432\u044b\u0439)         if (root-&gt;left-&gt;key &gt; key)         {             \/\/ \u0421\u043d\u0430\u0447\u0430\u043b\u0430 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u043e \u043f\u043e\u0434\u043d\u0438\u043c\u0435\u043c             \/\/ \u043a\u043b\u044e\u0447 \u043a\u0430\u043a \u043a\u043e\u0440\u0435\u043d\u044c left-left             root-&gt;left-&gt;left = splay(root-&gt;left-&gt;left, key);                \/\/ \u041f\u0435\u0440\u0432\u044b\u0439 \u0440\u0430\u0437\u0432\u043e\u0440\u043e\u0442 \u0434\u043b\u044f \u043a\u043e\u0440\u043d\u044f,              \/\/ \u0432\u0442\u043e\u0440\u043e\u0439 \u0440\u0430\u0437\u0432\u043e\u0440\u043e\u0442 \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442\u0441\u044f \u043f\u043e\u0441\u043b\u0435 else             root = rightRotate(root);         }         else if (root-&gt;left-&gt;key &lt; key) \/\/ Zig-Zag (\u041b\u0435\u0432\u044b\u0439-\u043f\u0440\u0430\u0432\u044b\u0439)         {             \/\/ \u0421\u043d\u0430\u0447\u0430\u043b\u0430 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u043e \u043f\u043e\u0434\u043d\u0438\u043c\u0430\u0435\u043c             \/\/ \u043a\u043b\u044e\u0447 \u043a\u0430\u043a \u043a\u043e\u0440\u0435\u043d\u044c left-right             root-&gt;left-&gt;right = splay(root-&gt;left-&gt;right, key);                \/\/ \u0412\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u043c \u043f\u0435\u0440\u0432\u044b\u0439 \u0440\u0430\u0437\u0432\u043e\u0440\u043e\u0442 \u0434\u043b\u044f root-&gt;left             if (root-&gt;left-&gt;right != NULL)                 root-&gt;left = leftRotate(root-&gt;left);         }            \/\/ \u0412\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u043c \u0432\u0442\u043e\u0440\u043e\u0439 \u0440\u0430\u0437\u0432\u043e\u0440\u043e\u0442 \u0434\u043b\u044f \u043a\u043e\u0440\u043d\u044f         return (root-&gt;left == NULL)? root: rightRotate(root);     }     else \/\/ \u041a\u043b\u044e\u0447 \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u0441\u044f \u0432 \u043f\u0440\u0430\u0432\u043e\u043c \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u0435     {         \/\/ \u041a\u043b\u044e\u0447\u0430 \u043d\u0435\u0442 \u0432 \u0434\u0435\u0440\u0435\u0432\u0435, \u043c\u044b \u0437\u0430\u043a\u043e\u043d\u0447\u0438\u043b\u0438         if (root-&gt;right == NULL) return root;            \/\/ Zag-Zig (\u041f\u0440\u0430\u0432\u044b\u0439-\u043b\u0435\u0432\u044b\u0439)         if (root-&gt;right-&gt;key &gt; key)         {             \/\/\u041f\u043e\u0434\u043d\u0438\u043c\u0430\u0435\u043c \u043a\u043b\u044e\u0447 \u0432 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u043a\u043e\u0440\u043d\u044f right-left             root-&gt;right-&gt;left = splay(root-&gt;right-&gt;left, key);                \/\/ \u0412\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u043c \u043f\u0435\u0440\u0432\u044b\u0439 \u043f\u043e\u0432\u043e\u0440\u043e\u0442 \u0434\u043b\u044f root-&gt;right             if (root-&gt;right-&gt;left != NULL)                 root-&gt;right = rightRotate(root-&gt;right);         }         else if (root-&gt;right-&gt;key &lt; key)\/\/ Zag-Zag (\u041f\u0440\u0430\u0432\u044b\u0439-\u043f\u0440\u0430\u0432\u044b\u0439)         {             \/\/ \u041f\u043e\u0434\u043d\u0438\u043c\u0430\u0435\u043c \u043a\u043b\u044e\u0447 \u0432 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u043a\u043e\u0440\u043d\u044f              \/\/ right-right \u0438 \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u043c \u043f\u0435\u0440\u0432\u044b\u0439 \u0440\u0430\u0437\u0432\u043e\u0440\u043e\u0442             root-&gt;right-&gt;right = splay(root-&gt;right-&gt;right, key);             root = leftRotate(root);         }            \/\/\u0412\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u043c \u0432\u0442\u043e\u0440\u043e\u0439 \u0440\u0430\u0437\u0432\u043e\u0440\u043e\u0442 \u0434\u043b\u044f \u043a\u043e\u0440\u043d\u044f         return (root-&gt;right == NULL)? root: leftRotate(root);     } }    \/\/ \u0424\u0443\u043d\u043a\u0446\u0438\u044f \u0434\u043b\u044f \u0432\u0441\u0442\u0430\u0432\u043a\u0438 \u043d\u043e\u0432\u043e\u0433\u043e \u043a\u043b\u044e\u0447\u0430 k \u0432 splay-\u0434\u0435\u0440\u0435\u0432\u043e \u0441 \u0437\u0430\u0434\u0430\u043d\u043d\u044b\u043c \u043a\u043e\u0440\u043d\u0435\u043c struct node *insert(struct node *root, int k) {     \/\/ \u041f\u0440\u043e\u0441\u0442\u043e\u0439 \u0441\u043b\u0443\u0447\u0430\u0439: \u0435\u0441\u043b\u0438 \u0434\u0435\u0440\u0435\u0432\u043e \u043f\u0443\u0441\u0442\u043e     if (root == NULL) return newNode(k);        \/\/ \u0414\u0435\u043b\u0430\u0435\u043c \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0439 \u0443\u0437\u0435\u043b-\u043b\u0438\u0441\u0442 \u043a\u043e\u0440\u043d\u0435\u043c     root = splay(root, k);        \/\/ \u0415\u0441\u043b\u0438 \u043a\u043b\u044e\u0447 \u0443\u0436\u0435 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442, \u0442\u043e \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u043c \u0435\u0433\u043e     if (root-&gt;key == k) return root;        \/\/ \u0412 \u043f\u0440\u043e\u0442\u0438\u0432\u043d\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u0432\u044b\u0434\u0435\u043b\u044f\u0435\u043c \u043f\u0430\u043c\u044f\u0442\u044c \u043f\u043e\u0434 \u043d\u043e\u0432\u044b\u0439 \u0443\u0437\u0435\u043b     struct node *newnode  = newNode(k);        \/\/ \u0415\u0441\u043b\u0438 \u043a\u043e\u0440\u043d\u0435\u0432\u043e\u0439 \u043a\u043b\u044e\u0447 \u0431\u043e\u043b\u044c\u0448\u0435, \u0434\u0435\u043b\u0430\u0435\u043c \u043a\u043e\u0440\u0435\u043d\u044c \u043f\u0440\u0430\u0432\u044b\u043c \u0434\u043e\u0447\u0435\u0440\u043d\u0438\u043c \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u043c \u043d\u043e\u0432\u043e\u0433\u043e \u0443\u0437\u043b\u0430, \u043a\u043e\u043f\u0438\u0440\u0443\u0435\u043c \u043b\u0435\u0432\u044b\u0439 \u0434\u043e\u0447\u0435\u0440\u043d\u0438\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u043a\u043e\u0440\u043d\u044f \u0432 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u043b\u0435\u0432\u043e\u0433\u043e \u0434\u043e\u0447\u0435\u0440\u043d\u0435\u0433\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u043d\u043e\u0432\u043e\u0433\u043e \u0443\u0437\u043b\u0430     if (root-&gt;key &gt; k)     {         newnode-&gt;right = root;         newnode-&gt;left = root-&gt;left;         root-&gt;left = NULL;     }        \/\/ \u0415\u0441\u043b\u0438 \u043a\u043e\u0440\u043d\u0435\u0432\u043e\u0439 \u043a\u043b\u044e\u0447 \u043c\u0435\u043d\u044c\u0448\u0435, \u0434\u0435\u043b\u0430\u0435\u043c \u043a\u043e\u0440\u0435\u043d\u044c \u043b\u0435\u0432\u044b\u043c \u0434\u043e\u0447\u0435\u0440\u043d\u0438\u043c \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u043c \u043d\u043e\u0432\u043e\u0433\u043e \u0443\u0437\u043b\u0430, \u043a\u043e\u043f\u0438\u0440\u0443\u0435\u043c \u043f\u0440\u0430\u0432\u044b\u0439 \u0434\u043e\u0447\u0435\u0440\u043d\u0438\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u043a\u043e\u0440\u043d\u044f \u0432 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u043f\u0440\u0430\u0432\u043e\u0433\u043e \u0434\u043e\u0447\u0435\u0440\u043d\u0435\u0433\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u043d\u043e\u0432\u043e\u0433\u043e \u0443\u0437\u043b\u0430     else     {         newnode-&gt;left = root;         newnode-&gt;right = root-&gt;right;         root-&gt;right = NULL;     }        return newnode; \/\/ \u043d\u043e\u0432\u044b\u0439 \u0443\u0437\u0435\u043b \u0441\u0442\u0430\u043d\u043e\u0432\u0438\u0442\u0441\u044f \u043d\u043e\u0432\u044b\u043c \u043a\u043e\u0440\u043d\u0435\u043c }    \/\/ \u0421\u043b\u0443\u0436\u0435\u0431\u043d\u0430\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u0434\u043b\u044f \u0432\u044b\u0432\u043e\u0434\u0430  \/\/ \u043e\u0431\u0445\u043e\u0434\u0430 \u0432 \u0434\u0435\u0440\u0435\u0432\u0430 \u0448\u0438\u0440\u0438\u043d\u0443.  \/\/ \u0424\u0443\u043d\u043a\u0446\u0438\u044f \u0442\u0430\u043a\u0436\u0435 \u0432\u044b\u0432\u043e\u0434\u0438\u0442 \u0432\u044b\u0441\u043e\u0442\u0443 \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0443\u0437\u043b\u0430 void preOrder(struct node *root) {     if (root != NULL)     {         printf(\"%d \", root-&gt;key);         preOrder(root-&gt;left);         preOrder(root-&gt;right);     } }    \/* \u0423\u043f\u0440\u0430\u0432\u043b\u044f\u044e\u0449\u0438\u0439 \u043a\u043e\u0434 \u0434\u043b\u044f \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u0438 \u043f\u0440\u0438\u0432\u0435\u0434\u0435\u043d\u043d\u043e\u0439 \u0432\u044b\u0448\u0435 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 *\/ int main() {     struct node *root = newNode(100);     root-&gt;left = newNode(50);     root-&gt;right = newNode(200);     root-&gt;left-&gt;left = newNode(40);     root-&gt;left-&gt;left-&gt;left = newNode(30);     root-&gt;left-&gt;left-&gt;left-&gt;left = newNode(20);     root = insert(root, 25);     printf(\"Preorder traversal of the modified Splay tree is \\n\");     preOrder(root);     return 0; } <\/code><\/pre>\n<h3>\u0412\u044b\u0432\u043e\u0434:<\/h3>\n<pre><code>Preorder traversal of the modified Splay tree is  25 20 50 30 40 100 200<\/code><\/pre>\n<\/p>\n<hr>\n<blockquote>\n<p><a href=\"https:\/\/otus.pw\/Zwdi\/\">\u0423\u0437\u043d\u0430\u0442\u044c \u043f\u043e\u0434\u0440\u043e\u0431\u043d\u0435\u0435 \u043e \u043a\u0443\u0440\u0441\u0435 <\/a>\u00ab\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u0438 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0434\u0430\u043d\u043d\u044b\u0445\u00bb.<\/p>\n<p><a href=\"https:\/\/otus.pw\/JTu7\/\">\u0417\u0430\u0440\u0435\u0433\u0438\u0441\u0442\u0440\u0438\u0440\u043e\u0432\u0430\u0442\u044c\u0441\u044f \u043d\u0430 \u043e\u0442\u043a\u0440\u044b\u0442\u044b\u0439 \u0443\u0440\u043e\u043a<\/a> \u00ab\u0417\u0430\u043f\u043e\u0432\u0435\u0434\u043d\u0438\u043a\u0438 \u0434\u0432\u043e\u0438\u0447\u043d\u044b\u0445 \u0434\u0435\u0440\u0435\u0432\u044c\u0435\u0432 \u043f\u043e\u0438\u0441\u043a\u0430\u00bb<a href=\"https:\/\/otus.pw\/JTu7\/\">.<\/a><\/p>\n<\/blockquote>\n<\/div>\n<p> \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0441\u0442\u0430\u0442\u044c\u0438 <a href=\"https:\/\/habr.com\/ru\/company\/otus\/blog\/538098\/\"> https:\/\/habr.com\/ru\/company\/otus\/blog\/538098\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"\n<div class=\"post__text post__text_v2\" id=\"post-content-body\">\n<blockquote>\n<p>\u041f\u0440\u0438\u0432\u0435\u0442, \u0445\u0430\u0431\u0440\u043e\u0432\u0447\u0430\u043d\u0435. \u0412 \u043f\u0440\u0435\u0434\u0434\u0432\u0435\u0440\u0438\u0438 \u0441\u0442\u0430\u0440\u0442\u0430 \u043a\u0443\u0440\u0441\u0430 <a href=\"https:\/\/otus.pw\/Zwdi\/\">\u00ab\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u0438 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0434\u0430\u043d\u043d\u044b\u0445\u00bb<\/a> \u043f\u0440\u0438\u0433\u043b\u0430\u0448\u0430\u0435\u043c \u0431\u0443\u0434\u0443\u0449\u0438\u0445 \u0441\u0442\u0443\u0434\u0435\u043d\u0442\u043e\u0432 \u0438 \u0432\u0441\u0435\u0445 \u0436\u0435\u043b\u0430\u044e\u0449\u0438\u0445 \u043d\u0430 \u043e\u0442\u043a\u0440\u044b\u0442\u044b\u0439 \u0443\u0440\u043e\u043a \u043f\u043e \u0442\u0435\u043c\u0435 <a href=\"https:\/\/otus.pw\/JTu7\/\">\u00ab\u0417\u0430\u043f\u043e\u0432\u0435\u0434\u043d\u0438\u043a\u0438 \u0434\u0432\u043e\u0438\u0447\u043d\u044b\u0445 \u0434\u0435\u0440\u0435\u0432\u044c\u0435\u0432 \u043f\u043e\u0438\u0441\u043a\u0430\u00bb.<\/a><\/p>\n<p>\u0422\u0430\u043a\u0436\u0435 \u0434\u0435\u043b\u0438\u043c\u0441\u044f \u0442\u0440\u0430\u0434\u0438\u0446\u0438\u043e\u043d\u043d\u044b\u043c \u043f\u043e\u043b\u0435\u0437\u043d\u044b\u043c \u043f\u0435\u0440\u0435\u0432\u043e\u0434\u043e\u043c.<\/p>\n<\/blockquote>\n<figure class=\"full-width\"><figcaption><\/figcaption><\/figure>\n<\/p>\n<hr>\n<p><strong><em>\u041f\u0435\u0440\u0435\u0434 \u043f\u0440\u043e\u0447\u0442\u0435\u043d\u0438\u0435\u043c \u044d\u0442\u043e\u0439 \u0441\u0442\u0430\u0442\u044c\u0438 \u043d\u0430\u0441\u0442\u043e\u044f\u0442\u0435\u043b\u044c\u043d\u043e \u0440\u0435\u043a\u043e\u043c\u0435\u043d\u0434\u0443\u0435\u0442\u0441\u044f \u043e\u0437\u043d\u0430\u043a\u043e\u043c\u0438\u0442\u044c\u0441\u044f \u0441 \u043f\u0435\u0440\u0432\u043e\u0439 \u0447\u0430\u0441\u0442\u044c\u044e: <\/em><\/strong><a href=\"https:\/\/habr.com\/ru\/company\/otus\/blog\/535316\/\"><strong><em><u>Splay-\u0434\u0435\u0440\u0435\u0432\u043e. \u041f\u043e\u0438\u0441\u043a<\/u><\/em><\/strong><\/a><\/p>\n<p>\u041a\u0430\u043a \u0443\u043f\u043e\u043c\u0438\u043d\u0430\u043b\u043e\u0441\u044c \u0432 <a href=\"https:\/\/habr.com\/ru\/company\/otus\/blog\/535316\/\"><u>\u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0435\u0439 \u0441\u0442\u0430\u0442\u044c\u0435<\/u><\/a>, Splay-\u0434\u0435\u0440\u0435\u0432\u043e \u2014 \u044d\u0442\u043e \u0441\u0430\u043c\u043e\u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u0443\u044e\u0449\u0430\u044f\u0441\u044f \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u0434\u0430\u043d\u043d\u044b\u0445, \u0432 \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0438\u0439 \u043a\u043b\u044e\u0447, \u043a \u043a\u043e\u0442\u043e\u0440\u043e\u043c\u0443 \u043e\u0441\u0443\u0449\u0435\u0441\u0442\u0432\u043b\u044f\u043b\u0441\u044f \u0434\u043e\u0441\u0442\u0443\u043f, \u0432\u0441\u0435\u0433\u0434\u0430 \u043f\u043e\u043c\u0435\u0449\u0430\u0435\u0442\u0441\u044f \u0432 \u043a\u043e\u0440\u0435\u043d\u044c. \u041e\u043f\u0435\u0440\u0430\u0446\u0438\u044f \u0432\u0441\u0442\u0430\u0432\u043a\u0438 \u0430\u043d\u0430\u043b\u043e\u0433\u0438\u0447\u043d\u0430 \u0432\u0441\u0442\u0430\u0432\u043a\u0435 \u0432 \u0431\u0438\u043d\u0430\u0440\u043d\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e \u043f\u043e\u0438\u0441\u043a\u0430 \u0441 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u0438\u043c\u0438 \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u043c\u0438 \u0448\u0430\u0433\u0430\u043c\u0438, \u0446\u0435\u043b\u044c \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0443\u0431\u0435\u0434\u0438\u0442\u044c\u0441\u044f, \u0447\u0442\u043e \u0432\u043d\u043e\u0432\u044c \u0432\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u043d\u044b\u0439 \u043a\u043b\u044e\u0447 \u0441\u0442\u0430\u043d\u043e\u0432\u0438\u0442\u0441\u044f \u043d\u043e\u0432\u044b\u043c \u043a\u043e\u0440\u043d\u0435\u043c.<\/p>\n<p>\u041d\u0438\u0436\u0435 \u043f\u0440\u0438\u0432\u0435\u0434\u0435\u043d\u044b \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u0435 \u0441\u043b\u0443\u0447\u0430\u0438 \u043f\u0440\u0438 \u0432\u0441\u0442\u0430\u0432\u043a\u0435 \u043a\u043b\u044e\u0447\u0430 k \u0432 Splay-\u0434\u0435\u0440\u0435\u0432\u043e.<\/p>\n<p><strong>1)<\/strong> \u041a\u043e\u0440\u0435\u043d\u044c \u0440\u0430\u0432\u0435\u043d NULL: \u043c\u044b \u043f\u0440\u043e\u0441\u0442\u043e \u0441\u043e\u0437\u0434\u0430\u0435\u043c \u043d\u043e\u0432\u044b\u0439 \u0443\u0437\u0435\u043b \u0438 \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u043c \u0435\u0433\u043e \u043a\u0430\u043a \u043a\u043e\u0440\u043d\u0435\u0432\u043e\u0439.<\/p>\n<p><strong>2) <\/strong>\u0412\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u043c \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044e <a href=\"https:\/\/habr.com\/ru\/company\/otus\/blog\/535316\/\"><u>Splay<\/u><\/a> \u043d\u0430\u0434 \u0437\u0430\u0434\u0430\u043d\u043d\u044b\u0439 \u043a\u043b\u044e\u0447\u043e\u043c k. \u0415\u0441\u043b\u0438 k \u0443\u0436\u0435 \u043f\u0440\u0438\u0441\u0443\u0442\u0441\u0442\u0432\u0443\u0435\u0442, \u043e\u043d \u0441\u0442\u0430\u043d\u043e\u0432\u0438\u0442\u0441\u044f \u043d\u043e\u0432\u044b\u043c \u043a\u043e\u0440\u043d\u0435\u043c. \u0415\u0441\u043b\u0438 \u043e\u043d \u043e\u0442\u0441\u0443\u0442\u0441\u0442\u0432\u0443\u0435\u0442, \u0442\u043e \u043d\u043e\u0432\u044b\u043c \u043a\u043e\u0440\u043d\u0435\u0432\u044b\u043c \u0443\u0437\u043b\u043e\u043c \u0441\u0442\u0430\u043d\u043e\u0432\u0438\u0442\u0441\u044f \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0438\u0439 \u0443\u0437\u0435\u043b-\u043b\u0438\u0441\u0442, \u043a \u043a\u043e\u0442\u043e\u0440\u043e\u043c\u0443 \u0431\u044b\u043b \u043e\u0441\u0443\u0449\u0435\u0441\u0442\u0432\u043b\u0435\u043d \u0434\u043e\u0441\u0442\u0443\u043f.<\/p>\n<p><strong>3)<\/strong> \u0415\u0441\u043b\u0438 \u043d\u043e\u0432\u044b\u0439 \u043a\u043e\u0440\u043d\u0435\u0432\u043e\u0439 \u043a\u043b\u044e\u0447 \u0442\u0430\u043a\u043e\u0439 \u0436\u0435, \u043a\u0430\u043a k, \u043d\u0438\u0447\u0435\u0433\u043e \u043d\u0435 \u0434\u0435\u043b\u0430\u0435\u043c, \u043f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 k \u0443\u0436\u0435 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442.<\/p>\n<p><strong>4) <\/strong>\u0412 \u043f\u0440\u043e\u0442\u0438\u0432\u043d\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u0432\u044b\u0434\u0435\u043b\u044f\u0435\u043c \u043f\u0430\u043c\u044f\u0442\u044c \u0434\u043b\u044f \u043d\u043e\u0432\u043e\u0433\u043e \u0443\u0437\u043b\u0430 \u0438 \u0441\u0440\u0430\u0432\u043d\u0438\u0432\u0430\u0435\u043c \u043a\u043e\u0440\u043d\u0435\u0432\u043e\u0439 \u043a\u043b\u044e\u0447 \u0441 k.<\/p>\n<p>      <strong>4.a)<\/strong> \u0415\u0441\u043b\u0438 k \u043c\u0435\u043d\u044c\u0448\u0435 \u043a\u043e\u0440\u043d\u0435\u0432\u043e\u0433\u043e \u043a\u043b\u044e\u0447\u0430, \u0434\u0435\u043b\u0430\u0435\u043c \u043a\u043e\u0440\u0435\u043d\u044c \u043f\u0440\u0430\u0432\u044b\u043c \u0434\u043e\u0447\u0435\u0440\u043d\u0438\u043c \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u043c \u043d\u043e\u0432\u043e\u0433\u043e \u0443\u0437\u043b\u0430, \u043a\u043e\u043f\u0438\u0440\u0443\u0435\u043c \u043b\u0435\u0432\u044b\u0439 \u0434\u043e\u0447\u0435\u0440\u043d\u0438\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u043a\u043e\u0440\u043d\u044f \u0432 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u043b\u0435\u0432\u043e\u0433\u043e \u0434\u043e\u0447\u0435\u0440\u043d\u0435\u0433\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u043d\u043e\u0432\u043e\u0433\u043e \u0443\u0437\u043b\u0430 \u0438 \u0434\u0435\u043b\u0430\u0435\u043c \u043b\u0435\u0432\u044b\u0439 \u0434\u043e\u0447\u0435\u0440\u043d\u0438\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u043a\u043e\u0440\u043d\u044f \u0440\u0430\u0432\u043d\u044b\u043c NULL.<\/p>\n<p>      <strong>4.b)<\/strong> \u0415\u0441\u043b\u0438 k \u0431\u043e\u043b\u044c\u0448\u0435 \u043a\u043e\u0440\u043d\u0435\u0432\u043e\u0433\u043e \u043a\u043b\u044e\u0447\u0430, \u0434\u0435\u043b\u0430\u0435\u043c \u043a\u043e\u0440\u0435\u043d\u044c \u043b\u0435\u0432\u044b\u043c \u0434\u043e\u0447\u0435\u0440\u043d\u0438\u043c \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u043c \u043d\u043e\u0432\u043e\u0433\u043e \u0443\u0437\u043b\u0430, \u043a\u043e\u043f\u0438\u0440\u0443\u0435\u043c \u043f\u0440\u0430\u0432\u044b\u0439 \u0434\u043e\u0447\u0435\u0440\u043d\u0438\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u043a\u043e\u0440\u043d\u044f \u0432 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u043f\u0440\u0430\u0432\u043e\u0433\u043e \u0434\u043e\u0447\u0435\u0440\u043d\u0435\u0433\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u043d\u043e\u0432\u043e\u0433\u043e \u0443\u0437\u043b\u0430 \u0438 \u0434\u0435\u043b\u0430\u0435\u043c \u043f\u0440\u0430\u0432\u044b\u0439 \u0434\u043e\u0447\u0435\u0440\u043d\u0438\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u043a\u043e\u0440\u043d\u044f \u0440\u0430\u0432\u043d\u044b\u043c NULL.<\/p>\n<p><strong>5)<\/strong> \u0412\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u043c \u043d\u043e\u0432\u044b\u0439 \u0443\u0437\u0435\u043b \u0432 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u043d\u043e\u0432\u043e\u0433\u043e \u043a\u043e\u0440\u043d\u044f \u0434\u0435\u0440\u0435\u0432\u0430.<\/p>\n<p><strong>\u041f\u0440\u0438\u043c\u0435\u0440:<\/strong><\/p>\n<pre><code>           100                  [20]                             25                \/  \\                   \\                             \/  \\         50   200                  50                          20   50         \/          insert(25)     \/  \\        insert(25)           \/  \\         40          ======&gt;      30   100      ========&gt;           30  100          \/          1. Splay(25)    \\     \\      2. insert 25         \\    \\     30                          40    200                         40   200       \/                                                            [20] <\/code><\/pre>\n<h3>\u0421++<\/h3>\n<pre><code class=\"cpp\">#include &lt;bits\/stdc++.h&gt; using namespace std;    \/\/ \u0423\u0437\u0435\u043b \u0410\u0412\u041b-\u0434\u0435\u0440\u0435\u0432\u0430 class node  {      public:     int key;      node *left, *right;  };     \/* \u0412\u0441\u043f\u043e\u043c\u043e\u0433\u0430\u0442\u0435\u043b\u044c\u043d\u0430\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u044f, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0432\u044b\u0434\u0435\u043b\u044f\u0435\u0442  \u043d\u043e\u0432\u044b\u0439 \u0443\u0437\u0435\u043b \u0441 \u0437\u0430\u0434\u0430\u043d\u043d\u044b\u043c key \u0438 left \u0438 right, \u0443\u043a\u0430\u0437\u044b\u0432\u0430\u044e\u0449\u0438\u043c\u0438 \u0432 NULL. *\/ node* newNode(int key)  {      node* Node = new node();     Node-&gt;key = key;      Node-&gt;left = Node-&gt;right = NULL;      return (Node);  }     \/\/ \u0421\u043b\u0443\u0436\u0435\u0431\u043d\u0430\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u0434\u043b\u044f \u0440\u0430\u0437\u0432\u043e\u0440\u043e\u0442\u0430 \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u0430 \u0441 \u043a\u043e\u0440\u043d\u0435\u043c y \u0432\u043f\u0440\u0430\u0432\u043e. \/\/ \u0421\u043c\u043e\u0442\u0440\u0438\u0442\u0435 \u0434\u0438\u0430\u0433\u0440\u0430\u043c\u043c\u0443, \u043f\u0440\u0438\u0432\u0435\u0434\u0435\u043d\u043d\u0443\u044e \u0432\u044b\u0448\u0435. node *rightRotate(node *x)  {      node *y = x-&gt;left;      x-&gt;left = y-&gt;right;      y-&gt;right = x;      return y;  }     \/\/ \u0421\u043b\u0443\u0436\u0435\u0431\u043d\u0430\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u0434\u043b\u044f \u0440\u0430\u0437\u0432\u043e\u0440\u043e\u0442\u0430 \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u0430 \u0441 \u043a\u043e\u0440\u043d\u0435\u043c x \u0432\u043b\u0435\u0432\u043e  \/\/ \u0421\u043c\u043e\u0442\u0440\u0438\u0442\u0435 \u0434\u0438\u0430\u0433\u0440\u0430\u043c\u043c\u0443, \u043f\u0440\u0438\u0432\u0435\u0434\u0435\u043d\u043d\u0443\u044e \u0432\u044b\u0448\u0435.  node *leftRotate(node *x)  {      node *y = x-&gt;right;      x-&gt;right = y-&gt;left;      y-&gt;left = x;      return y;  }     \/\/ \u042d\u0442\u0430 \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u043f\u043e\u0434\u043d\u0438\u043c\u0435\u0442 \u043a\u043b\u044e\u0447 \/\/ \u0432 \u043a\u043e\u0440\u0435\u043d\u044c, \u0435\u0441\u043b\u0438 \u043e\u043d \u043f\u0440\u0438\u0441\u0443\u0442\u0441\u0442\u0432\u0443\u0435\u0442 \u0432 \u0434\u0435\u0440\u0435\u0432\u0435.  \/\/ \u0415\u0441\u043b\u0438 \u0442\u0430\u043a\u043e\u0439 \u043a\u043b\u044e\u0447 \u043e\u0442\u0441\u0443\u0442\u0441\u0442\u0432\u0443\u0435\u0442 \u0432 \u0434\u0435\u0440\u0435\u0432\u0435, \u043e\u043d\u0430 \/\/ \u043f\u043e\u0434\u043d\u0438\u043c\u0435\u0442 \u0432 \u043a\u043e\u0440\u0435\u043d\u044c \u0441\u0430\u043c\u044b\u0439 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0438\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442, \/\/ \u043a \u043a\u043e\u0442\u043e\u0440\u043e\u043c\u0443 \u0431\u044b\u043b \u043e\u0441\u0443\u0449\u0435\u0441\u0442\u0432\u043b\u0435\u043d \u0434\u043e\u0441\u0442\u0443\u043f. \/\/ \u042d\u0442\u0430 \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u0438\u0437\u043c\u0435\u043d\u044f\u0435\u0442 \u0434\u0435\u0440\u0435\u0432\u043e \/\/ \u0438 \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442 \u043d\u043e\u0432\u044b\u0439 \u043a\u043e\u0440\u0435\u043d\u044c (root). node *splay(node *root, int key)  {      \/\/ \u0411\u0430\u0437\u043e\u0432\u044b\u0435 \u0441\u043b\u0443\u0447\u0430\u0438: root \u0440\u0430\u0432\u0435\u043d NULL \u0438\u043b\u0438     \/\/ \u043a\u043b\u044e\u0447 \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u0441\u044f \u0432 \u043a\u043e\u0440\u043d\u0435     if (root == NULL || root-&gt;key == key)          return root;         \/\/ \u041a\u043b\u044e\u0447 \u043b\u0435\u0436\u0438\u0442 \u0432 \u043b\u0435\u0432\u043e\u043c \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u0435     if (root-&gt;key &gt; key)      {          \/\/ \u041a\u043b\u044e\u0447\u0430 \u043d\u0435\u0442 \u0432 \u0434\u0435\u0440\u0435\u0432\u0435, \u043c\u044b \u0437\u0430\u043a\u043e\u043d\u0447\u0438\u043b\u0438         if (root-&gt;left == NULL) return root;             \/\/ Zig-Zig (\u041b\u0435\u0432\u044b\u0439-\u043b\u0435\u0432\u044b\u0439)         if (root-&gt;left-&gt;key &gt; key)          {              \/\/ \u0421\u043d\u0430\u0447\u0430\u043b\u0430 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u043e \u043f\u043e\u0434\u043d\u0438\u043c\u0435\u043c              \/\/ \u043a\u043b\u044e\u0447 \u0432 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u043a\u043e\u0440\u043d\u044f left-left             root-&gt;left-&gt;left = splay(root-&gt;left-&gt;left, key);                 \/\/ \u041f\u0435\u0440\u0432\u044b\u0439 \u0440\u0430\u0437\u0432\u043e\u0440\u043e\u0442 \u0434\u043b\u044f root,               \/\/ \u0432\u0442\u043e\u0440\u043e\u0439 \u0440\u0430\u0437\u0432\u043e\u0440\u043e\u0442 \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442\u0441\u044f \u043f\u043e\u0441\u043b\u0435 else              root = rightRotate(root);          }          else if (root-&gt;left-&gt;key &lt; key) \/\/ Zig-Zag (Left Right)          {              \/\/ \u0421\u043d\u0430\u0447\u0430\u043b\u0430 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u043e \u043f\u043e\u0434\u043d\u0438\u043c\u0430\u0435\u043c              \/\/ \u043a\u043b\u044e\u0447 \u0432 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u043a\u043e\u0440\u0435\u043d\u044f left-right             root-&gt;left-&gt;right = splay(root-&gt;left-&gt;right, key);                 \/\/ \u0412\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u043c \u043f\u0435\u0440\u0432\u044b\u0439 \u0440\u0430\u0437\u0432\u043e\u0440\u043e\u0442 \u0434\u043b\u044f root-&gt;left             if (root-&gt;left-&gt;right != NULL)                  root-&gt;left = leftRotate(root-&gt;left);          }             \/\/ \u0412\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u043c \u0432\u0442\u043e\u0440\u043e\u0439 \u0440\u0430\u0437\u0432\u043e\u0440\u043e\u0442 \u0434\u043b\u044f \u043a\u043e\u0440\u043d\u044f         return (root-&gt;left == NULL)? root: rightRotate(root);      }      else \/\/ \u041a\u043b\u044e\u0447 \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u0441\u044f \u0432 \u043f\u0440\u0430\u0432\u043e\u043c \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u0435     {          \/\/ \u041a\u043b\u044e\u0447\u0430 \u043d\u0435\u0442 \u0432 \u0434\u0435\u0440\u0435\u0432\u0435, \u043c\u044b \u0437\u0430\u043a\u043e\u043d\u0447\u0438\u043b\u0438         if (root-&gt;right == NULL) return root;             \/\/ Zag-Zig (\u041f\u0440\u0430\u0432\u044b\u0439-\u043b\u0435\u0432\u044b\u0439)         if (root-&gt;right-&gt;key &gt; key)          {              \/\/ \u041f\u043e\u0434\u043d\u044f\u0442\u044c \u043a\u043b\u044e\u0447 \u0432 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u043a\u043e\u0440\u0435\u043d\u044f right-left             root-&gt;right-&gt;left = splay(root-&gt;right-&gt;left, key);                 \/\/ \u0412\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u043c \u043f\u0435\u0440\u0432\u044b\u0439 \u043f\u043e\u0432\u043e\u0440\u043e\u0442 \u0434\u043b\u044f root-&gt;right             if (root-&gt;right-&gt;left != NULL)                  root-&gt;right = rightRotate(root-&gt;right);          }          else if (root-&gt;right-&gt;key &lt; key)\/\/ Zag-Zag (\u041f\u0440\u0430\u0432\u044b\u0439-\u043f\u0440\u0430\u0432\u044b\u0439)          {              \/\/ \u041f\u043e\u0434\u043d\u0438\u043c\u0430\u0435\u043c \u043a\u043b\u044e\u0447 \u0432 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u043a\u043e\u0440\u043d\u044f               \/\/ right-right \u0438 \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u043c \u043f\u0435\u0440\u0432\u044b\u0439 \u0440\u0430\u0437\u0432\u043e\u0440\u043e\u0442             root-&gt;right-&gt;right = splay(root-&gt;right-&gt;right, key);              root = leftRotate(root);          }             \/\/ \u0412\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u043c \u0432\u0442\u043e\u0440\u043e\u0439 \u0440\u0430\u0437\u0432\u043e\u0440\u043e\u0442 \u0434\u043b\u044f root         return (root-&gt;right == NULL)? root: leftRotate(root);      }  }     \/\/ \u0424\u0443\u043d\u043a\u0446\u0438\u044f \u0434\u043b\u044f \u0432\u0441\u0442\u0430\u0432\u043a\u0438 \u043d\u043e\u0432\u043e\u0433\u043e \u043a\u043b\u044e\u0447\u0430 k \u0432 splay-\u0434\u0435\u0440\u0435\u0432\u043e \u0441 \u0437\u0430\u0434\u0430\u043d\u043d\u044b\u043c \u043a\u043e\u0440\u043d\u0435\u043c node *insert(node *root, int k)  {      \/\/ \u041f\u0440\u043e\u0441\u0442\u043e\u0439 \u0441\u043b\u0443\u0447\u0430\u0439: \u0435\u0441\u043b\u0438 \u0434\u0435\u0440\u0435\u0432\u043e \u043f\u0443\u0441\u0442\u043e     if (root == NULL) return newNode(k);         \/\/ \u0414\u0435\u043b\u0430\u0435\u043c \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0439 \u0443\u0437\u0435\u043b-\u043b\u0438\u0441\u0442 \u043a\u043e\u0440\u043d\u0435\u043c      root = splay(root, k);         \/\/ \u0415\u0441\u043b\u0438 \u043a\u043b\u044e\u0447 \u0443\u0436\u0435 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442, \u0442\u043e \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u043c \u0435\u0433\u043e     if (root-&gt;key == k) return root;         \/\/ \u0412 \u043f\u0440\u043e\u0442\u0438\u0432\u043d\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u0432\u044b\u0434\u0435\u043b\u044f\u0435\u043c \u043f\u0430\u043c\u044f\u0442\u044c \u043f\u043e\u0434 \u043d\u043e\u0432\u044b\u0439 \u0443\u0437\u0435\u043b     node *newnode = newNode(k);         \/\/ \u0415\u0441\u043b\u0438 \u043a\u043e\u0440\u043d\u0435\u0432\u043e\u0439 \u043a\u043b\u044e\u0447 \u0431\u043e\u043b\u044c\u0448\u0435, \u0434\u0435\u043b\u0430\u0435\u043c \u043a\u043e\u0440\u0435\u043d\u044c \u043f\u0440\u0430\u0432\u044b\u043c \u0434\u043e\u0447\u0435\u0440\u043d\u0438\u043c \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u043c \u043d\u043e\u0432\u043e\u0433\u043e \u0443\u0437\u043b\u0430, \u043a\u043e\u043f\u0438\u0440\u0443\u0435\u043c \u043b\u0435\u0432\u044b\u0439 \u0434\u043e\u0447\u0435\u0440\u043d\u0438\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u043a\u043e\u0440\u043d\u044f \u0432 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u043b\u0435\u0432\u043e\u0433\u043e \u0434\u043e\u0447\u0435\u0440\u043d\u0435\u0433\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u043d\u043e\u0432\u043e\u0433\u043e \u0443\u0437\u043b\u0430     if (root-&gt;key &gt; k)      {          newnode-&gt;right = root;          newnode-&gt;left = root-&gt;left;          root-&gt;left = NULL;      }         \/\/ \u0415\u0441\u043b\u0438 \u043a\u043e\u0440\u043d\u0435\u0432\u043e\u0439 \u043a\u043b\u044e\u0447 \u043c\u0435\u043d\u044c\u0448\u0435, \u0434\u0435\u043b\u0430\u0435\u043c \u043a\u043e\u0440\u0435\u043d\u044c \u043b\u0435\u0432\u044b\u043c \u0434\u043e\u0447\u0435\u0440\u043d\u0438\u043c \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u043c \u043d\u043e\u0432\u043e\u0433\u043e \u0443\u0437\u043b\u0430, \u043a\u043e\u043f\u0438\u0440\u0443\u0435\u043c \u043f\u0440\u0430\u0432\u044b\u0439 \u0434\u043e\u0447\u0435\u0440\u043d\u0438\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u043a\u043e\u0440\u043d\u044f \u0432 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u043f\u0440\u0430\u0432\u043e\u0433\u043e \u0434\u043e\u0447\u0435\u0440\u043d\u0435\u0433\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u043d\u043e\u0432\u043e\u0433\u043e \u0443\u0437\u043b\u0430     else     {          newnode-&gt;left = root;          newnode-&gt;right = root-&gt;right;          root-&gt;right = NULL;      }         return newnode; \/\/ \u043d\u043e\u0432\u044b\u0439 \u0443\u0437\u0435\u043b \u0441\u0442\u0430\u043d\u043e\u0432\u0438\u0442\u0441\u044f \u043d\u043e\u0432\u044b\u043c \u043a\u043e\u0440\u043d\u0435\u043c }     \/\/ \u0421\u043b\u0443\u0436\u0435\u0431\u043d\u0430\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u0434\u043b\u044f \u0432\u044b\u0432\u043e\u0434\u0430  \/\/ \u043e\u0431\u0445\u043e\u0434\u0430 \u0432 \u0434\u0435\u0440\u0435\u0432\u0430 \u0448\u0438\u0440\u0438\u043d\u0443.  \/\/ \u0424\u0443\u043d\u043a\u0446\u0438\u044f \u0442\u0430\u043a\u0436\u0435 \u0432\u044b\u0432\u043e\u0434\u0438\u0442 \u0432\u044b\u0441\u043e\u0442\u0443 \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0443\u0437\u043b\u0430 void preOrder(node *root)  {      if (root != NULL)      {          cout&lt;&lt;root-&gt;key&lt;&lt;\" \";          preOrder(root-&gt;left);          preOrder(root-&gt;right);      }  }     \/* \u0423\u043f\u0440\u0430\u0432\u043b\u044f\u044e\u0449\u0438\u0439 \u043a\u043e\u0434 *\/ int main()  {      node *root = newNode(100);      root-&gt;left = newNode(50);      root-&gt;right = newNode(200);      root-&gt;left-&gt;left = newNode(40);      root-&gt;left-&gt;left-&gt;left = newNode(30);      root-&gt;left-&gt;left-&gt;left-&gt;left = newNode(20);      root = insert(root, 25);      cout&lt;&lt;\"Preorder traversal of the modified Splay tree is \\n\";      preOrder(root);      return 0;  }     \/\/ \u042d\u0442\u043e\u0442 \u043a\u043e\u0434 \u043b\u044e\u0431\u0435\u0437\u043d\u043e \u043f\u0440\u0435\u0434\u043e\u0441\u0442\u0430\u0432\u043b\u0435\u043d rathbhupendra <\/code><\/pre>\n<h3>C<\/h3>\n<pre><code class=\"cpp\">\/\/ \u041a\u043e\u0434 \u043f\u043e\u0437\u0430\u0438\u043c\u0441\u0442\u0432\u043e\u0432\u0430\u043d c http:\/\/algs4.cs.princeton.edu\/33balanced\/SplayBST.java.html #include&lt;stdio.h&gt; #include&lt;stdlib.h&gt;    \/\/ \u0423\u0437\u0435\u043b \u0410\u0412\u041b-\u0434\u0435\u0440\u0435\u0432\u0430 struct node {     int key;     struct node *left, *right; };    \/* \u0412\u0441\u043f\u043e\u043c\u043e\u0433\u0430\u0442\u0435\u043b\u044c\u043d\u0430\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u044f, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0441\u043e\u0437\u0434\u0430\u0435\u0442  \u043d\u043e\u0432\u044b\u0439 \u0443\u0437\u0435\u043b \u0441 \u0437\u0430\u0434\u0430\u043d\u043d\u044b\u043c key \u0438 left \u0438 right, \u0443\u043a\u0430\u0437\u044b\u0432\u0430\u044e\u0449\u0438\u043c\u0438 \u0432 NULL. *\/ struct node* newNode(int key) {     struct node* node = (struct node*)malloc(sizeof(struct node));     node-&gt;key   = key;     node-&gt;left  = node-&gt;right  = NULL;     return (node); }    \/\/ \u0421\u043b\u0443\u0436\u0435\u0431\u043d\u0430\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u0434\u043b\u044f \u0440\u0430\u0437\u0432\u043e\u0440\u043e\u0442\u0430 \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u0430 \u0441 \u043a\u043e\u0440\u043d\u0435\u043c y \u0432\u043f\u0440\u0430\u0432\u043e. \/\/ \u0421\u043c\u043e\u0442\u0440\u0438\u0442\u0435 \u0434\u0438\u0430\u0433\u0440\u0430\u043c\u043c\u0443, \u043f\u0440\u0438\u0432\u0435\u0434\u0435\u043d\u043d\u0443\u044e \u0432\u044b\u0448\u0435. struct node *rightRotate(struct node *x) {     struct node *y = x-&gt;left;     x-&gt;left = y-&gt;right;     y-&gt;right = x;     return y; }    \/\/ \u0421\u043b\u0443\u0436\u0435\u0431\u043d\u0430\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u0434\u043b\u044f \u0440\u0430\u0437\u0432\u043e\u0440\u043e\u0442\u0430 \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u0430 \u0441 \u043a\u043e\u0440\u043d\u0435\u043c x \u0432\u043b\u0435\u0432\u043e  \/\/ \u0421\u043c\u043e\u0442\u0440\u0438\u0442\u0435 \u0434\u0438\u0430\u0433\u0440\u0430\u043c\u043c\u0443, \u043f\u0440\u0438\u0432\u0435\u0434\u0435\u043d\u043d\u0443\u044e \u0432\u044b\u0448\u0435.  struct node *leftRotate(struct node *x) {     struct node *y = x-&gt;right;     x-&gt;right = y-&gt;left;     y-&gt;left = x;     return y; }    \/\/ \u042d\u0442\u0430 \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u043f\u043e\u0434\u043d\u0438\u043c\u0435\u0442 \u043a\u043b\u044e\u0447 \/\/ \u0432 \u043a\u043e\u0440\u0435\u043d\u044c, \u0435\u0441\u043b\u0438 \u043e\u043d \u043f\u0440\u0438\u0441\u0443\u0442\u0441\u0442\u0432\u0443\u0435\u0442 \u0432 \u0434\u0435\u0440\u0435\u0432\u0435.  \/\/ \u0415\u0441\u043b\u0438 \u0442\u0430\u043a\u043e\u0439 \u043a\u043b\u044e\u0447 \u043e\u0442\u0441\u0443\u0442\u0441\u0442\u0432\u0443\u0435\u0442 \u0432 \u0434\u0435\u0440\u0435\u0432\u0435, \u043e\u043d\u0430 \/\/ \u043f\u043e\u0434\u043d\u0438\u043c\u0435\u0442 \u0432 \u043a\u043e\u0440\u0435\u043d\u044c \u0441\u0430\u043c\u044b\u0439 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0438\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442, \/\/ \u043a \u043a\u043e\u0442\u043e\u0440\u043e\u043c\u0443 \u0431\u044b\u043b \u043e\u0441\u0443\u0449\u0435\u0441\u0442\u0432\u043b\u0435\u043d \u0434\u043e\u0441\u0442\u0443\u043f. \/\/ \u042d\u0442\u0430 \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u0438\u0437\u043c\u0435\u043d\u044f\u0435\u0442 \u0434\u0435\u0440\u0435\u0432\u043e \/\/ \u0438 \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442 \u043d\u043e\u0432\u044b\u0439 \u043a\u043e\u0440\u0435\u043d\u044c. struct node *splay(struct node *root, int key) {     \/\/ \u0411\u0430\u0437\u043e\u0432\u044b\u0435 \u0441\u043b\u0443\u0447\u0430\u0438: \u043a\u043e\u0440\u0435\u043d\u044c \u0440\u0430\u0432\u0435\u043d NULL \u0438\u043b\u0438     \/\/ \u043a\u043b\u044e\u0447 \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u0441\u044f \u0432 \u043a\u043e\u0440\u043d\u0435     if (root == NULL || root-&gt;key == key)         return root;        \/\/ \u041a\u043b\u044e\u0447 \u043b\u0435\u0436\u0438\u0442 \u0432 \u043b\u0435\u0432\u043e\u043c \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u0435     if (root-&gt;key &gt; key)     {         \/\/ \u041a\u043b\u044e\u0447\u0430 \u043d\u0435\u0442 \u0432 \u0434\u0435\u0440\u0435\u0432\u0435, \u043c\u044b \u0437\u0430\u043a\u043e\u043d\u0447\u0438\u043b\u0438         if (root-&gt;left == NULL) return root;            \/\/ Zig-Zig (\u041b\u0435\u0432\u044b\u0439-\u043b\u0435\u0432\u044b\u0439)         if (root-&gt;left-&gt;key &gt; key)         {             \/\/ \u0421\u043d\u0430\u0447\u0430\u043b\u0430 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u043e \u043f\u043e\u0434\u043d\u0438\u043c\u0435\u043c             \/\/ \u043a\u043b\u044e\u0447 \u043a\u0430\u043a \u043a\u043e\u0440\u0435\u043d\u044c left-left             root-&gt;left-&gt;left = splay(root-&gt;left-&gt;left, key);                \/\/ \u041f\u0435\u0440\u0432\u044b\u0439 \u0440\u0430\u0437\u0432\u043e\u0440\u043e\u0442 \u0434\u043b\u044f \u043a\u043e\u0440\u043d\u044f,              \/\/ \u0432\u0442\u043e\u0440\u043e\u0439 \u0440\u0430\u0437\u0432\u043e\u0440\u043e\u0442 \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442\u0441\u044f \u043f\u043e\u0441\u043b\u0435 else             root = rightRotate(root);         }         else if (root-&gt;left-&gt;key &lt; key) \/\/ Zig-Zag (\u041b\u0435\u0432\u044b\u0439-\u043f\u0440\u0430\u0432\u044b\u0439)         {             \/\/ \u0421\u043d\u0430\u0447\u0430\u043b\u0430 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u043e \u043f\u043e\u0434\u043d\u0438\u043c\u0430\u0435\u043c             \/\/ \u043a\u043b\u044e\u0447 \u043a\u0430\u043a \u043a\u043e\u0440\u0435\u043d\u044c left-right             root-&gt;left-&gt;right = splay(root-&gt;left-&gt;right, key);                \/\/ \u0412\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u043c \u043f\u0435\u0440\u0432\u044b\u0439 \u0440\u0430\u0437\u0432\u043e\u0440\u043e\u0442 \u0434\u043b\u044f root-&gt;left             if (root-&gt;left-&gt;right != NULL)                 root-&gt;left = leftRotate(root-&gt;left);         }            \/\/ \u0412\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u043c \u0432\u0442\u043e\u0440\u043e\u0439 \u0440\u0430\u0437\u0432\u043e\u0440\u043e\u0442 \u0434\u043b\u044f \u043a\u043e\u0440\u043d\u044f         return (root-&gt;left == NULL)? root: rightRotate(root);     }     else \/\/ \u041a\u043b\u044e\u0447<\/code><\/pre>\n<\/hr>\n<\/blockquote>\n<\/div>\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-316604","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/316604","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=316604"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/316604\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=316604"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=316604"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=316604"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}