{"id":315679,"date":"2020-12-28T15:01:03","date_gmt":"2020-12-28T15:01:03","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=315679"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=315679","title":{"rendered":"Splay-\u0434\u0435\u0440\u0435\u0432\u043e. \u041f\u043e\u0438\u0441\u043a"},"content":{"rendered":"\n
\n
\n

\u041f\u0440\u0438\u0432\u0435\u0442, \u0425\u0430\u0431\u0440! \u0411\u0443\u0434\u0443\u0449\u0438\u0445 \u0441\u0442\u0443\u0434\u0435\u043d\u0442\u043e\u0432 \u043a\u0443\u0440\u0441\u0430 <\/strong>«\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»<\/strong><\/a> \u043f\u0440\u0438\u0433\u043b\u0430\u0448\u0430\u0435\u043c \u043d\u0430 <\/strong>\u043e\u0442\u043a\u0440\u044b\u0442\u044b\u0439 \u0432\u0435\u0431\u0438\u043d\u0430\u0440 \u043f\u043e \u0442\u0435\u043c\u0435 «\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.»<\/strong><\/a><\/p>\n

\u0410 \u0441\u0435\u0439\u0447\u0430\u0441 \u0434\u0435\u043b\u0438\u043c\u0441\u044f \u0441 \u0432\u0430\u043c\u0438 \u0442\u0440\u0430\u0434\u0438\u0446\u0438\u043e\u043d\u043d\u044b\u043c \u043f\u0435\u0440\u0435\u0432\u043e\u0434\u043e\u043c \u043f\u043e\u043b\u0435\u0437\u043d\u043e\u0433\u043e \u043c\u0430\u0442\u0435\u0440\u0438\u0430\u043b\u0430.<\/p>\n<\/blockquote>\n

<\/figcaption><\/figure>\n
\n

\u041d\u0430\u0438\u0445\u0443\u0434\u0448\u0430\u044f \u0432\u0440\u0435\u043c\u0435\u043d\u043d\u0430\u044f \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0442\u0430\u043a\u0438\u0445 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439, \u043a\u0430\u043a \u043f\u043e\u0438\u0441\u043a, \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u0435 \u0438 \u0432\u0441\u0442\u0430\u0432\u043a\u0430, \u0434\u043b\u044f \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430 \u043f\u043e\u0438\u0441\u043a\u0430 (Binary Search Tree) \u0441\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442 O(n). \u041d\u0430\u0438\u0445\u0443\u0434\u0448\u0438\u0439 \u0441\u043b\u0443\u0447\u0430\u0439 \u0441\u043b\u0443\u0447\u0430\u0439 \u0432\u043e\u0437\u043d\u0438\u043a\u0430\u0435\u0442, \u043a\u043e\u0433\u0434\u0430 \u0434\u0435\u0440\u0435\u0432\u043e \u043d\u0435\u0441\u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u043e\u0432\u0430\u043d\u043e. \u041c\u044b \u043c\u043e\u0436\u0435\u043c \u0443\u043b\u0443\u0447\u0448\u0438\u0442\u044c \u043d\u0430\u0438\u0445\u0443\u0434\u0448\u0438\u0439 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u0432\u0440\u0435\u043c\u0435\u043d\u043d\u043e\u0439 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u0438 \u0434\u043e O(log n) \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u043a\u0440\u0430\u0441\u043d\u043e-\u0447\u0435\u0440\u043d\u044b\u0445 \u0438 \u0410\u0412\u041b-\u0434\u0435\u0440\u0435\u0432\u044c\u0435\u0432<\/a>.<\/p>\n

\u041c\u043e\u0436\u0435\u043c \u043b\u0438 \u043c\u044b \u0434\u043e\u0431\u0438\u0442\u044c\u0441\u044f \u043d\u0430 \u043f\u0440\u0430\u043a\u0442\u0438\u043a\u0435 \u043b\u0443\u0447\u0448\u0435\u0433\u043e \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0430, \u0447\u0435\u043c \u0442\u043e\u0442, \u0447\u0442\u043e \u043d\u0430\u043c \u0434\u0430\u044e\u0442 \u043a\u0440\u0430\u0441\u043d\u043e-\u0447\u0435\u0440\u043d\u044b\u0435 \u0438\u043b\u0438 \u0410\u0412\u041b-\u0434\u0435\u0440\u0435\u0432\u044c\u044f?<\/strong><\/p>\n

\u041f\u043e\u0434\u043e\u0431\u043d\u043e \u043a\u0440\u0430\u0441\u043d\u043e-\u0447\u0435\u0440\u043d\u044b\u043c \u0438 \u0410\u0412\u041b-\u0434\u0435\u0440\u0435\u0432\u044c\u044f\u043c<\/a>, Splay-\u0434\u0435\u0440\u0435\u0432\u043e (\u0438\u043b\u0438 \u043a\u043e\u0441\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e<\/em>) \u0442\u0430\u043a\u0436\u0435 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0441\u0430\u043c\u043e\u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u0443\u044e\u0449\u0438\u043c\u0441\u044f \u0431\u0438\u043d\u0430\u0440\u043d\u044b\u043c \u0434\u0435\u0440\u0435\u0432\u043e\u043c \u043f\u043e\u0438\u0441\u043a\u0430<\/a>. \u041e\u0441\u043d\u043e\u0432\u043d\u0430\u044f \u0438\u0434\u0435\u044f splay-\u0434\u0435\u0440\u0435\u0432\u0430 \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e\u0431\u044b \u043f\u043e\u043c\u0435\u0449\u0430\u0442\u044c \u044d\u043b\u0435\u043c\u0435\u043d\u0442, \u043a \u043a\u043e\u0442\u043e\u0440\u043e\u043c\u0443 \u043d\u0435\u0434\u0430\u0432\u043d\u043e \u043e\u0441\u0443\u0449\u0435\u0441\u0442\u0432\u043b\u044f\u043b\u0441\u044f \u0434\u043e\u0441\u0442\u0443\u043f, \u0432 \u043a\u043e\u0440\u0435\u043d\u044c \u0434\u0435\u0440\u0435\u0432\u0430, \u0447\u0442\u043e \u0434\u0435\u043b\u0430\u0435\u0442 \u044d\u0442\u043e\u0442 \u044d\u043b\u0435\u043c\u0435\u043d\u0442, \u0434\u043e\u0441\u0442\u0443\u043f\u043d\u044b\u043c \u0437\u0430 \u0432\u0440\u0435\u043c\u044f \u043f\u043e\u0440\u044f\u0434\u043a\u0430 O(1) \u043f\u0440\u0438 \u043f\u043e\u0432\u0442\u043e\u0440\u043d\u043e\u043c \u0434\u043e\u0441\u0442\u0443\u043f\u0435. \u0412\u0441\u044f \u0441\u0443\u0442\u044c \u0437\u0430\u043a\u043b\u044e\u0447\u0430\u0435\u0442\u0441\u044f \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e\u0431\u044b \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u043a\u043e\u043d\u0446\u0435\u043f\u0446\u0438\u044e \u043b\u043e\u043a\u0430\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u0441\u0441\u044b\u043b\u043e\u043a (\u0432 \u0441\u0440\u0435\u0434\u043d\u0435\u0441\u0442\u0430\u0442\u0438\u0441\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u043c \u043f\u0440\u0438\u043b\u043e\u0436\u0435\u043d\u0438\u0438 80% \u043e\u0431\u0440\u0430\u0449\u0435\u043d\u0438\u0439 \u043f\u0440\u0438\u0445\u043e\u0434\u044f\u0442\u0441\u044f \u043d\u0430 20% \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432). \u041f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u044c\u0442\u0435 \u0441\u0435\u0431\u0435 \u0441\u0438\u0442\u0443\u0430\u0446\u0438\u044e, \u043a\u043e\u0433\u0434\u0430 \u0443 \u043d\u0430\u0441 \u0435\u0441\u0442\u044c \u043c\u0438\u043b\u043b\u0438\u043e\u043d\u044b \u0438\u043b\u0438 \u0434\u0430\u0436\u0435 \u043c\u0438\u043b\u043b\u0438\u0430\u0440\u0434\u044b \u043a\u043b\u044e\u0447\u0435\u0439, \u0438 \u043b\u0438\u0448\u044c \u043a \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u043c \u0438\u0437 \u043d\u0438\u0445 \u043e\u0431\u0440\u0430\u0449\u0430\u044e\u0442\u0441\u044f \u0440\u0435\u0433\u0443\u043b\u044f\u0440\u043d\u043e, \u0447\u0442\u043e \u0432\u0435\u0441\u044c\u043c\u0430 \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e \u0434\u043b\u044f \u043c\u043d\u043e\u0433\u0438\u0445 \u0442\u0438\u043f\u0438\u0447\u043d\u044b\u0445 \u043f\u0440\u0438\u043b\u043e\u0436\u0435\u043d\u0438\u044f\u0445.<\/p>\n

\u0412\u0441\u0435 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u0441\u043e splay-\u0434\u0435\u0440\u0435\u0432\u043e\u043c \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u044e\u0442\u0441\u044f \u0432 \u0441\u0440\u0435\u0434\u043d\u0435\u043c \u0437\u0430 \u0432\u0440\u0435\u043c\u044f \u043f\u043e\u0440\u044f\u0434\u043a\u0430 O(log n), \u0433\u0434\u0435 n — \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0432 \u0434\u0435\u0440\u0435\u0432\u0435. \u041b\u044e\u0431\u0430\u044f \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u0430\u044f \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044f \u0432 \u0445\u0443\u0434\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u043c\u043e\u0436\u0435\u0442 \u0437\u0430\u043d\u044f\u0442\u044c \u0432\u0440\u0435\u043c\u044f \u043f\u043e\u0440\u044f\u0434\u043a\u0430 \u0422\u044d\u0442\u0430(n).<\/p>\n

\u041e\u043f\u0435\u0440\u0430\u0446\u0438\u044f \u043f\u043e\u0438\u0441\u043a\u0430 <\/h3>\n

\u041e\u043f\u0435\u0440\u0430\u0446\u0438\u044f \u043f\u043e\u0438\u0441\u043a\u0430 \u0432 splay-\u0434\u0435\u0440\u0435\u0432\u0435 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442 \u0441\u043e\u0431\u043e\u0439 \u0441\u0442\u0430\u043d\u0434\u0430\u0440\u0442\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u043e\u0438\u0441\u043a\u0430 \u0432 \u0431\u0438\u043d\u0430\u0440\u043d\u043e\u043c \u0434\u0435\u0440\u0435\u0432\u0435, \u043f\u043e\u0441\u043b\u0435 \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u043e \u0432\u044b\u0432\u043e\u0440\u0430\u0447\u0438\u0432\u0430\u0435\u0442\u0441\u044f (\u0438\u0441\u043a\u043e\u043c\u044b\u0439 \u0443\u0437\u0435\u043b \u043f\u0435\u0440\u0435\u043c\u0435\u0449\u0430\u0435\u0442\u0441\u044f \u0432 \u043a\u043e\u0440\u0435\u043d\u044c \u2014 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044f splay). \u0415\u0441\u043b\u0438 \u043f\u043e\u0438\u0441\u043a \u0437\u0430\u0432\u0435\u0440\u0448\u0438\u043b\u0441\u044f \u0443\u0441\u043f\u0435\u0445\u043e\u043c, \u0442\u043e \u043d\u0430\u0439\u0434\u0435\u043d\u043d\u044b\u0439 \u0443\u0437\u0435\u043b \u043f\u043e\u0434\u043d\u0438\u043c\u0430\u0435\u0442\u0441\u044f \u043d\u0430\u0432\u0435\u0440\u0445 \u0438 \u0441\u0442\u0430\u043d\u043e\u0432\u0438\u0442\u0441\u044f \u043d\u043e\u0432\u044b\u043c \u043a\u043e\u0440\u043d\u0435\u043c. \u0412 \u043f\u0440\u043e\u0442\u0438\u0432\u043d\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u043a\u043e\u0440\u043d\u0435\u043c \u0441\u0442\u0430\u043d\u043e\u0432\u0438\u0442\u0441\u044f \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0438\u0439 \u0443\u0437\u0435\u043b, \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 \u0434\u043e \u0434\u043e\u0441\u0442\u0438\u0436\u0435\u043d\u0438\u044f NULL.<\/p>\n

\u0412 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0435 \u043e\u0441\u0443\u0449\u0435\u0441\u0442\u0432\u043b\u0435\u043d\u0438\u044f \u0434\u043e\u0441\u0442\u0443\u043f\u0430 \u043a \u0443\u0437\u043b\u0443 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0435 \u0441\u043b\u0443\u0447\u0430\u0438:<\/p>\n

1.<\/strong> \u0423\u0437\u0435\u043b \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043a\u043e\u0440\u043d\u0435\u0432\u044b\u043c.<\/strong> \u041c\u044b \u043f\u0440\u043e\u0441\u0442\u043e \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u043c \u043a\u043e\u0440\u0435\u043d\u044c, \u0431\u043e\u043b\u044c\u0448\u0435 \u043d\u0438\u0447\u0435\u0433\u043e \u043d\u0435 \u0434\u0435\u043b\u0430\u0435\u043c, \u0442\u0430\u043a \u043a\u0430\u043a \u0443\u0437\u0435\u043b, \u043a \u043a\u043e\u0442\u043e\u0440\u043e\u043c\u0443 \u043e\u0441\u0443\u0449\u0435\u0441\u0442\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0434\u043e\u0441\u0442\u0443\u043f, \u0443\u0436\u0435 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043a\u043e\u0440\u043d\u0435\u0432\u044b\u043c.<\/p>\n

2. Zig: \u0443\u0437\u0435\u043b \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0434\u043e\u0447\u0435\u0440\u043d\u0438\u043c \u043f\u043e \u043e\u0442\u043d\u043e\u0448\u0435\u043d\u0438\u044e \u043a \u043a\u043e\u0440\u043d\u044e<\/strong> <\/em>(\u0443 \u0443\u0437\u043b\u0430 \u043d\u0435\u0442 \u043f\u0440\u0430\u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044f). \u0423\u0437\u0435\u043b \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043b\u0438\u0431\u043e \u043b\u0435\u0432\u044b\u043c \u043f\u043e\u0442\u043e\u043c\u043a\u043e\u043c \u043a\u043e\u0440\u043d\u044f (\u043c\u044b \u0434\u0435\u043b\u0430\u0435\u043c \u043f\u0440\u0430\u0432\u044b\u0439 \u0440\u0430\u0437\u0432\u043e\u0440\u043e\u0442), \u043b\u0438\u0431\u043e \u043f\u0440\u0430\u0432\u044b\u043c \u043f\u043e\u0442\u043e\u043c\u043a\u043e\u043c \u0441\u0432\u043e\u0435\u0433\u043e \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044f (\u043c\u044b \u0434\u0435\u043b\u0430\u0435\u043c \u043b\u0435\u0432\u044b\u0439 \u0440\u0430\u0437\u0432\u043e\u0440\u043e\u0442).<\/p>\n

T1, T2 \u0438 T3 \u2014 \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u044c\u044f \u0434\u0435\u0440\u0435\u0432\u0430 \u0441 \u043a\u043e\u0440\u043d\u0435\u043c y (\u0441\u043b\u0435\u0432\u0430) \u0438\u043b\u0438 x (\u0441\u043f\u0440\u0430\u0432\u0430)<\/p>\n

<\/figcaption><\/figure>\n

3. \u0423 \u0443\u0437\u043b\u0430 \u0435\u0441\u0442\u044c \u0438 \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044c, \u0438 \u043f\u0440\u0430\u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044c<\/em><\/strong>. \u0412\u043e\u0437\u043c\u043e\u0436\u043d\u044b \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0435 \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u044b:<\/p>\n

\u0430) Zig-Zig \u0438 Zag-Zag.<\/strong> \u0423\u0437\u0435\u043b \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043b\u0435\u0432\u044b\u043c \u043f\u043e\u0442\u043e\u043c\u043a\u043e\u043c \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u0441\u043a\u043e\u0433\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430, \u0438 \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044c \u0442\u0430\u043a\u0436\u0435 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043b\u0435\u0432\u044b\u043c \u043f\u043e\u0442\u043e\u043c\u043a\u043e\u043c \u043f\u0440\u0430\u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044f (\u0434\u0432\u0430 \u0440\u0430\u0437\u0432\u043e\u0440\u043e\u0442\u0430 \u0432\u043f\u0440\u0430\u0432\u043e) \u0418\u041b\u0418 \u0443\u0437\u0435\u043b \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043f\u0440\u0430\u0432\u044b\u043c \u043f\u043e\u0442\u043e\u043c\u043a\u043e\u043c \u0441\u0432\u043e\u0435\u0433\u043e \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u0441\u043a\u043e\u0433\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430, \u0438 \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044c \u0442\u0430\u043a\u0436\u0435 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043f\u0440\u0430\u0432\u044b\u043c \u043f\u043e\u0442\u043e\u043c\u043a\u043e\u043c \u0441\u0432\u043e\u0435\u0433\u043e \u043f\u0440\u0430\u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044c (\u0434\u0432\u0430 \u0440\u0430\u0437\u0432\u043e\u0440\u043e\u0442\u0430 \u0432\u043b\u0435\u0432\u043e).<\/p>\n

<\/figcaption><\/figure>\n

\u0431) Zig-Zag \u0438 Zag-Zig.<\/strong> \u0423\u0437\u0435\u043b \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043b\u0435\u0432\u044b\u043c \u043f\u043e\u0442\u043e\u043c\u043a\u043e\u043c \u043f\u043e \u043e\u0442\u043d\u043e\u0448\u0435\u043d\u0438\u044e \u043a \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u0441\u043a\u043e\u043c\u0443 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0443, \u0430 \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044c \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043f\u0440\u0430\u0432\u044b\u043c \u043f\u043e\u0442\u043e\u043c\u043a\u043e\u043c \u043f\u0440\u0430\u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044f (\u0440\u0430\u0437\u0432\u043e\u0440\u043e\u0442 \u0432\u043b\u0435\u0432\u043e \u0441 \u043f\u043e\u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u043c \u0440\u0430\u0437\u0432\u043e\u0440\u043e\u0442\u043e\u043c \u0432\u043f\u0440\u0430\u0432\u043e) \u0418\u041b\u0418 \u0443\u0437\u0435\u043b \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043f\u0440\u0430\u0432\u044b\u043c \u043f\u043e\u0442\u043e\u043c\u043a\u043e\u043c \u0441\u0432\u043e\u0435\u0433\u043e \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u0441\u043a\u043e\u0433\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430, \u0430 \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044c \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043b\u0435\u0432\u044b\u043c \u043f\u043e\u0442\u043e\u043c\u043a\u043e\u043c \u043f\u0440\u0430\u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044f (\u0440\u0430\u0437\u0432\u043e\u0440\u043e\u0442 \u0432\u043f\u0440\u0430\u0432\u043e \u0441 \u043f\u043e\u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u043c \u0440\u0430\u0437\u0432\u043e\u0440\u043e\u0442\u043e\u043c \u0432\u043b\u0435\u0432\u043e).<\/p>\n

<\/figcaption><\/figure>\n

\u041f\u0440\u0438\u043c\u0435\u0440:<\/strong><\/p>\n

<\/figcaption><\/figure>\n

\u0412\u0430\u0436\u043d\u043e \u043e\u0442\u043c\u0435\u0442\u0438\u0442\u044c, \u0447\u0442\u043e \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044f \u043f\u043e\u0438\u0441\u043a\u0430 \u0438\u043b\u0438 \u0440\u0430\u0437\u0432\u043e\u0440\u043e\u0442\u0430 (splay) \u043d\u0435 \u0442\u043e\u043b\u044c\u043a\u043e \u043f\u0435\u0440\u0435\u043d\u043e\u0441\u0438\u0442 \u043d\u0430\u0439\u0434\u0435\u043d\u043d\u044b\u0439 \u043a\u043b\u044e\u0447 \u0432 \u043a\u043e\u0440\u0435\u043d\u044c, \u043d\u043e \u0442\u0430\u043a\u0436\u0435 \u0443\u0440\u0430\u0432\u043d\u043e\u0432\u0435\u0448\u0438\u0432\u0430\u0435\u0442 \u0434\u0435\u0440\u0435\u0432\u043e. \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440 \u0432 \u0441\u043b\u0443\u0447\u0430\u0435 \u0432\u044b\u0448\u0435, \u0432\u044b\u0441\u043e\u0442\u0430 \u0434\u0435\u0440\u0435\u0432\u0430 \u0443\u043c\u0435\u043d\u044c\u0448\u0430\u0435\u0442\u0441\u044f \u043d\u0430 1.<\/p>\n

\u0420\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438:<\/h4>\n

C++<\/h3>\n
#include <bits\/stdc++.h>  using namespace std;   \/\/ An AVL tree node  class node  {  \tpublic:  \tint key;  \tnode *left, *right;  };   \/* Helper function that allocates  a new node with the given key and  \tNULL left and right pointers. *\/ node* newNode(int key)  {  \tnode* Node = new node();  \tNode->key = key;  \tNode->left = Node->right = NULL;  \treturn (Node);  }   \/\/ A utility function to right  \/\/ rotate subtree rooted with y  \/\/ See the diagram given above.  node *rightRotate(node *x)  {  \tnode *y = x->left;  \tx->left = y->right;  \ty->right = x;  \treturn y;  }   \/\/ A utility function to left  \/\/ rotate subtree rooted with x  \/\/ See the diagram given above.  node *leftRotate(node *x)  {  \tnode *y = x->right;  \tx->right = y->left;  \ty->left = x;  \treturn y;  }   \/\/ This function brings the key at  \/\/ root if key is present in tree.  \/\/ If key is not present, then it  \/\/ brings the last accessed item at  \/\/ root. This function modifies the  \/\/ tree and returns the new root  node *splay(node *root, int key)  {  \t\/\/ Base cases: root is NULL or  \t\/\/ key is present at root  \tif (root == NULL || root->key == key)  \t\treturn root;   \t\/\/ Key lies in left subtree  \tif (root->key > key)  \t{  \t\t\/\/ Key is not in tree, we are done  \t\tif (root->left == NULL) return root;   \t\t\/\/ Zig-Zig (Left Left)  \t\tif (root->left->key > key)  \t\t{  \t\t\t\/\/ First recursively bring the  \t\t\t\/\/ key as root of left-left  \t\t\troot->left->left = splay(root->left->left, key);   \t\t\t\/\/ Do first rotation for root,  \t\t\t\/\/ second rotation is done after else  \t\t\troot = rightRotate(root);  \t\t}  \t\telse if (root->left->key < key) \/\/ Zig-Zag (Left Right)  \t\t{  \t\t\t\/\/ First recursively bring  \t\t\t\/\/ the key as root of left-right  \t\t\troot->left->right = splay(root->left->right, key);   \t\t\t\/\/ Do first rotation for root->left  \t\t\tif (root->left->right != NULL)  \t\t\t\troot->left = leftRotate(root->left);  \t\t}   \t\t\/\/ Do second rotation for root  \t\treturn (root->left == NULL)? root: rightRotate(root);  \t}  \telse \/\/ Key lies in right subtree  \t{  \t\t\/\/ Key is not in tree, we are done  \t\tif (root->right == NULL) return root;   \t\t\/\/ Zag-Zig (Right Left)  \t\tif (root->right->key > key)  \t\t{  \t\t\t\/\/ Bring the key as root of right-left  \t\t\troot->right->left = splay(root->right->left, key);   \t\t\t\/\/ Do first rotation for root->right  \t\t\tif (root->right->left != NULL)  \t\t\t\troot->right = rightRotate(root->right);  \t\t}  \t\telse if (root->right->key < key)\/\/ Zag-Zag (Right Right)  \t\t{  \t\t\t\/\/ Bring the key as root of  \t\t\t\/\/ right-right and do first rotation  \t\t\troot->right->right = splay(root->right->right, key);  \t\t\troot = leftRotate(root);  \t\t}   \t\t\/\/ Do second rotation for root  \t\treturn (root->right == NULL)? root: leftRotate(root);  \t}  }   \/\/ The search function for Splay tree.  \/\/ Note that this function returns the  \/\/ new root of Splay Tree. If key is  \/\/ present in tree then, it is moved to root.  node *search(node *root, int key)  {  \treturn splay(root, key);  }   \/\/ A utility function to print  \/\/ preorder traversal of the tree.  \/\/ The function also prints height of every node  void preOrder(node *root)  {  \tif (root != NULL)  \t{  \t\tcout<<root->key<<\" \";  \t\tpreOrder(root->left);  \t\tpreOrder(root->right);  \t}  }   \/* Driver code*\/ int main()  {  \tnode *root = newNode(100);  \troot->left = newNode(50);  \troot->right = newNode(200);  \troot->left->left = newNode(40);  \troot->left->left->left = newNode(30);  \troot->left->left->left->left = newNode(20);   \troot = search(root, 20);  \tcout << \"Preorder traversal of the modified Splay tree is \\n\";  \tpreOrder(root);  \treturn 0;  }   \/\/ This code is contributed by rathbhupendra <\/code><\/pre>\n
C<\/h3>\n
\/\/ The code is adopted from http:\/\/goo.gl\/SDH9hH  #include<stdio.h>  #include<stdlib.h>   \/\/ An AVL tree node  struct node  {  \tint key;  \tstruct node *left, *right;  };   \/* Helper function that allocates a new node with the given key and  \tNULL left and right pointers. *\/ struct node* newNode(int key)  {  \tstruct node* node = (struct node*)malloc(sizeof(struct node));  \tnode->key = key;  \tnode->left = node->right = NULL;  \treturn (node);  }   \/\/ A utility function to right rotate subtree rooted with y  \/\/ See the diagram given above.  struct node *rightRotate(struct node *x)  {  \tstruct node *y = x->left;  \tx->left = y->right;  \ty->right = x;  \treturn y;  }   \/\/ A utility function to left rotate subtree rooted with x  \/\/ See the diagram given above.  struct node *leftRotate(struct node *x)  {  \tstruct node *y = x->right;  \tx->right = y->left;  \ty->left = x;  \treturn y;  }   \/\/ This function brings the key at root if key is present in tree.  \/\/ If key is not present, then it brings the last accessed item at  \/\/ root. This function modifies the tree and returns the new root  struct node *splay(struct node *root, int key)  {  \t\/\/ Base cases: root is NULL or key is present at root  \tif (root == NULL || root->key == key)  \t\treturn root;   \t\/\/ Key lies in left subtree  \tif (root->key > key)  \t{  \t\t\/\/ Key is not in tree, we are done  \t\tif (root->left == NULL) return root;   \t\t\/\/ Zig-Zig (Left Left)  \t\tif (root->left->key > key)  \t\t{  \t\t\t\/\/ First recursively bring the key as root of left-left  \t\t\troot->left->left = splay(root->left->left, key);   \t\t\t\/\/ Do first rotation for root, second rotation is done after else  \t\t\troot = rightRotate(root);  \t\t}  \t\telse if (root->left->key < key) \/\/ Zig-Zag (Left Right)  \t\t{  \t\t\t\/\/ First recursively bring the key as root of left-right  \t\t\troot->left->right = splay(root->left->right, key);   \t\t\t\/\/ Do first rotation for root->left  \t\t\tif (root->left->right != NULL)  \t\t\t\troot->left = leftRotate(root->left);  \t\t}   \t\t\/\/ Do second rotation for root  \t\treturn (root->left == NULL)? root: rightRotate(root);  \t}  \telse \/\/ Key lies in right subtree  \t{  \t\t\/\/ Key is not in tree, we are done  \t\tif (root->right == NULL) return root;   \t\t\/\/ Zag-Zig (Right Left)  \t\tif (root->right->key > key)  \t\t{  \t\t\t\/\/ Bring the key as root of right-left  \t\t\troot->right->left = splay(root->right->left, key);   \t\t\t\/\/ Do first rotation for root->right  \t\t\tif (root->right->left != NULL)  \t\t\t\troot->right = rightRotate(root->right);  \t\t}  \t\telse if (root->right->key < key)\/\/ Zag-Zag (Right Right)  \t\t{  \t\t\t\/\/ Bring the key as root of right-right and do first rotation  \t\t\troot->right->right = splay(root->right->right, key);  \t\t\troot = leftRotate(root);  \t\t}   \t\t\/\/ Do second rotation for root  \t\treturn (root->right == NULL)? root: leftRotate(root);  \t}  }   \/\/ The search function for Splay tree. Note that this function  \/\/ returns the new root of Splay Tree. If key is present in tree  \/\/ then, it is moved to root.  struct node *search(struct node *root, int key)  {  \treturn splay(root, key);  }   \/\/ A utility function to print preorder traversal of the tree.  \/\/ The function also prints height of every node  void preOrder(struct node *root)  {  \tif (root != NULL)  \t{  \t\tprintf(\"%d \", root->key);  \t\tpreOrder(root->left);  \t\tpreOrder(root->right);  \t}  }   \/* Driver program to test above function*\/ int main()  {  \tstruct node *root = newNode(100);  \troot->left = newNode(50);  \troot->right = newNode(200);  \troot->left->left = newNode(40);  \troot->left->left->left = newNode(30);  \troot->left->left->left->left = newNode(20);   \troot = search(root, 20);  \tprintf(\"Preorder traversal of the modified Splay tree is \\n\");  \tpreOrder(root);  \treturn 0;  }  <\/code><\/pre>\n
Java<\/h3>\n
\/\/ Java implementation for above approach  class GFG  {   \/\/ An AVL tree node  static class node  {   \tint key;  \tnode left, right;  };   \/* Helper function that allocates  a new node with the given key and  \tnull left and right pointers. *\/ static node newNode(int key)  {  \tnode Node = new node();  \tNode.key = key;  \tNode.left = Node.right = null;  \treturn (Node);  }   \/\/ A utility function to right  \/\/ rotate subtree rooted with y  \/\/ See the diagram given above.  static node rightRotate(node x)  {  \tnode y = x.left;  \tx.left = y.right;  \ty.right = x;  \treturn y;  }   \/\/ A utility function to left  \/\/ rotate subtree rooted with x  \/\/ See the diagram given above.  static node leftRotate(node x)  {  \tnode y = x.right;  \tx.right = y.left;  \ty.left = x;  \treturn y;  }   \/\/ This function brings the key at  \/\/ root if key is present in tree.  \/\/ If key is not present, then it  \/\/ brings the last accessed item at  \/\/ root. This function modifies the  \/\/ tree and returns the new root  static node splay(node root, int key)  {  \t\/\/ Base cases: root is null or  \t\/\/ key is present at root  \tif (root == null || root.key == key)  \t\treturn root;   \t\/\/ Key lies in left subtree  \tif (root.key > key)  \t{  \t\t\/\/ Key is not in tree, we are done  \t\tif (root.left == null) return root;   \t\t\/\/ Zig-Zig (Left Left)  \t\tif (root.left.key > key)  \t\t{  \t\t\t\/\/ First recursively bring the  \t\t\t\/\/ key as root of left-left  \t\t\troot.left.left = splay(root.left.left, key);   \t\t\t\/\/ Do first rotation for root,  \t\t\t\/\/ second rotation is done after else  \t\t\troot = rightRotate(root);  \t\t}  \t\telse if (root.left.key < key) \/\/ Zig-Zag (Left Right)  \t\t{  \t\t\t\/\/ First recursively bring  \t\t\t\/\/ the key as root of left-right  \t\t\troot.left.right = splay(root.left.right, key);   \t\t\t\/\/ Do first rotation for root.left  \t\t\tif (root.left.right != null)  \t\t\t\troot.left = leftRotate(root.left);  \t\t}   \t\t\/\/ Do second rotation for root  \t\treturn (root.left == null) ?  \t\t\t\t\t\t\troot : rightRotate(root);  \t}  \telse \/\/ Key lies in right subtree  \t{  \t\t\/\/ Key is not in tree, we are done  \t\tif (root.right == null) return root;   \t\t\/\/ Zag-Zig (Right Left)  \t\tif (root.right.key > key)  \t\t{  \t\t\t\/\/ Bring the key as root of right-left  \t\t\troot.right.left = splay(root.right.left, key);   \t\t\t\/\/ Do first rotation for root.right  \t\t\tif (root.right.left != null)  \t\t\t\troot.right = rightRotate(root.right);  \t\t}  \t\telse if (root.right.key < key)\/\/ Zag-Zag (Right Right)  \t\t{  \t\t\t\/\/ Bring the key as root of  \t\t\t\/\/ right-right and do first rotation  \t\t\troot.right.right = splay(root.right.right, key);  \t\t\troot = leftRotate(root);  \t\t}   \t\t\/\/ Do second rotation for root  \t\treturn (root.right == null) ?  \t\t\t\t\t\t\troot : leftRotate(root);  \t}  }   \/\/ The search function for Splay tree.  \/\/ Note that this function returns the  \/\/ new root of Splay Tree. If key is  \/\/ present in tree then, it is moved to root.  static node search(node root, int key)  {  \treturn splay(root, key);  }   \/\/ A utility function to print  \/\/ preorder traversal of the tree.  \/\/ The function also prints height of every node  static void preOrder(node root)  {  \tif (root != null)  \t{  \t\tSystem.out.print(root.key + \" \");  \t\tpreOrder(root.left);  \t\tpreOrder(root.right);  \t}  }   \/\/ Driver code  public static void main(String[] args)  {  \tnode root = newNode(100);  \troot.left = newNode(50);  \troot.right = newNode(200);  \troot.left.left = newNode(40);  \troot.left.left.left = newNode(30);  \troot.left.left.left.left = newNode(20);   \troot = search(root, 20);  \tSystem.out.print(\"Preorder traversal of the\" +  \t\t\t\t\t\" modified Splay tree is \\n\");  \tpreOrder(root);  }  }   \/\/ This code is contributed by 29AjayKumar  <\/code><\/pre>\n
C#<\/h3>\n
\/\/ C# implementation for above approach  using System;   class GFG  {   \/\/ An AVL tree node  public class node  {   \tpublic int key;  \tpublic node left, right;  };   \/* Helper function that allocates  a new node with the given key and  null left and right pointers. *\/ static node newNode(int key)  {  \tnode Node = new node();  \tNode.key = key;  \tNode.left = Node.right = null;  \treturn (Node);  }   \/\/ A utility function to right  \/\/ rotate subtree rooted with y  \/\/ See the diagram given above.  static node rightRotate(node x)  {  \tnode y = x.left;  \tx.left = y.right;  \ty.right = x;  \treturn y;  }   \/\/ A utility function to left  \/\/ rotate subtree rooted with x  \/\/ See the diagram given above.  static node leftRotate(node x)  {  \tnode y = x.right;  \tx.right = y.left;  \ty.left = x;  \treturn y;  }   \/\/ This function brings the key at  \/\/ root if key is present in tree.  \/\/ If key is not present, then it  \/\/ brings the last accessed item at  \/\/ root. This function modifies the  \/\/ tree and returns the new root  static node splay(node root, int key)  {  \t\/\/ Base cases: root is null or  \t\/\/ key is present at root  \tif (root == null || root.key == key)  \t\treturn root;   \t\/\/ Key lies in left subtree  \tif (root.key > key)  \t{  \t\t\/\/ Key is not in tree, we are done  \t\tif (root.left == null) return root;   \t\t\/\/ Zig-Zig (Left Left)  \t\tif (root.left.key > key)  \t\t{  \t\t\t\/\/ First recursively bring the  \t\t\t\/\/ key as root of left-left  \t\t\troot.left.left = splay(root.left.left, key);   \t\t\t\/\/ Do first rotation for root,  \t\t\t\/\/ second rotation is done after else  \t\t\troot = rightRotate(root);  \t\t}  \t\telse if (root.left.key < key) \/\/ Zig-Zag (Left Right)  \t\t{  \t\t\t\/\/ First recursively bring  \t\t\t\/\/ the key as root of left-right  \t\t\troot.left.right = splay(root.left.right, key);   \t\t\t\/\/ Do first rotation for root.left  \t\t\tif (root.left.right != null)  \t\t\t\troot.left = leftRotate(root.left);  \t\t}   \t\t\/\/ Do second rotation for root  \t\treturn (root.left == null) ?  \t\t\t\t\t\t\troot : rightRotate(root);  \t}  \telse \/\/ Key lies in right subtree  \t{  \t\t\/\/ Key is not in tree, we are done  \t\tif (root.right == null) return root;   \t\t\/\/ Zag-Zig (Right Left)  \t\tif (root.right.key > key)  \t\t{  \t\t\t\/\/ Bring the key as root of right-left  \t\t\troot.right.left = splay(root.right.left, key);   \t\t\t\/\/ Do first rotation for root.right  \t\t\tif (root.right.left != null)  \t\t\t\troot.right = rightRotate(root.right);  \t\t}  \t\telse if (root.right.key < key)\/\/ Zag-Zag (Right Right)  \t\t{  \t\t\t\/\/ Bring the key as root of  \t\t\t\/\/ right-right and do first rotation  \t\t\troot.right.right = splay(root.right.right, key);  \t\t\troot = leftRotate(root);  \t\t}   \t\t\/\/ Do second rotation for root  \t\treturn (root.right == null) ?  \t\t\t\t\t\t\troot : leftRotate(root);  \t}  }   \/\/ The search function for Splay tree.  \/\/ Note that this function returns the  \/\/ new root of Splay Tree. If key is  \/\/ present in tree then, it is moved to root.  static node search(node root, int key)  {  \treturn splay(root, key);  }   \/\/ A utility function to print  \/\/ preorder traversal of the tree.  \/\/ The function also prints height of every node  static void preOrder(node root)  {  \tif (root != null)  \t{  \t\tConsole.Write(root.key + \" \");  \t\tpreOrder(root.left);  \t\tpreOrder(root.right);  \t}  }   \/\/ Driver code  public static void Main(String[] args)  {  \tnode root = newNode(100);  \troot.left = newNode(50);  \troot.right = newNode(200);  \troot.left.left = newNode(40);  \troot.left.left.left = newNode(30);  \troot.left.left.left.left = newNode(20);   \troot = search(root, 20);  \tConsole.Write(\"Preorder traversal of the\" +  \t\t\t\t\" modified Splay tree is \\n\");  \tpreOrder(root);  }  }   \/\/ This code is contributed by 29AjayKumar <\/code><\/pre>\n
\u0412\u044b\u0445\u043e\u0434\u043d\u044b\u0435 \u0434\u0430\u043d\u043d\u044b\u0435:<\/strong><\/p>\n
Preorder traversal of the modified Splay tree is 20 50 30 40 100 200<\/code><\/p>\n
\u0420\u0435\u0437\u044e\u043c\u0435<\/h3>\n
1)<\/strong> Splay-\u0434\u0435\u0440\u0435\u0432\u044c\u044f \u043e\u0431\u043b\u0430\u0434\u0430\u044e\u0442 \u043e\u0442\u043b\u0438\u0447\u043d\u044b\u043c \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u043e\u043c \u043b\u043e\u043a\u0430\u043b\u044c\u043d\u043e\u0441\u0442\u0438. \u0427\u0430\u0441\u0442\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c\u044b\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u043b\u0435\u0433\u043a\u043e \u043d\u0430\u0439\u0442\u0438. \u0420\u0435\u0434\u043a\u0438\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u043d\u0435 \u043c\u0435\u0448\u0430\u044e\u0442\u0441\u044f \u043f\u0440\u0438 \u043f\u043e\u0438\u0441\u043a\u0435.<\/p>\n
2) <\/strong>\u0412\u0441\u0435 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u0441\u043e splay-\u0434\u0435\u0440\u0435\u0432\u043e\u043c \u0432 \u0441\u0440\u0435\u0434\u043d\u0435\u043c \u0437\u0430\u043d\u0438\u043c\u0430\u044e\u0442 \u0432\u0440\u0435\u043c\u044f \u043f\u043e\u0440\u044f\u0434\u043a\u0430 O(log n). \u041c\u043e\u0436\u043d\u043e \u0441\u0442\u0440\u043e\u0433\u043e \u0434\u043e\u043a\u0430\u0437\u0430\u0442\u044c, \u0447\u0442\u043e Splay-\u0434\u0435\u0440\u0435\u0432\u044c\u044f \u0440\u0430\u0431\u043e\u0442\u0430\u044e\u0442 \u0432 \u0441\u0440\u0435\u0434\u043d\u0435\u043c \u0437\u0430 \u0432\u0440\u0435\u043c\u044f \u043f\u043e\u0440\u044f\u0434\u043a\u0430 O(log n) \u043d\u0430 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044e \u043f\u0440\u0438 \u043b\u044e\u0431\u043e\u0439 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 (\u043f\u0440\u0438 \u0443\u0441\u043b\u043e\u0432\u0438\u0438, \u0447\u0442\u043e \u043c\u044b \u043d\u0430\u0447\u0438\u043d\u0430\u0435\u043c \u0441 \u043f\u0443\u0441\u0442\u043e\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430)<\/p>\n
3)<\/strong> Splay-\u0434\u0435\u0440\u0435\u0432\u044c\u044f \u043f\u0440\u043e\u0449\u0435 \u043f\u043e \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044e \u0441 \u043a\u0440\u0430\u0441\u043d\u043e-\u0447\u0435\u0440\u043d\u044b\u043c\u0438 \u0438 \u0410\u0412\u041b-\u0434\u0435\u0440\u0435\u0432\u044c\u044f\u043c\u0438<\/a>, \u0442\u0430\u043a \u043a\u0430\u043a \u0443\u0437\u043b\u044b splay-\u0434\u0435\u0440\u0435\u0432\u0430 \u043d\u0435 \u0442\u0440\u0435\u0431\u0443\u044e\u0442 \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u0445 \u043f\u043e\u043b\u0435\u0439.<\/p>\n
4)<\/strong> \u0412 \u043e\u0442\u043b\u0438\u0447\u0438\u0435 \u043e\u0442 \u0410\u0412\u041b-\u0434\u0435\u0440\u0435\u0432\u0430<\/a>, splay-\u0434\u0435\u0440\u0435\u0432\u043e \u043c\u043e\u0436\u0435\u0442 \u0438\u0437\u043c\u0435\u043d\u044f\u0442\u044c\u0441\u044f \u0434\u0430\u0436\u0435 \u043f\u0440\u0438 \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u0438 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u0447\u0442\u0435\u043d\u0438\u044f, \u0442\u0430\u043a\u0438\u0445 \u043a\u0430\u043a \u043f\u043e\u0438\u0441\u043a.<\/p>\n
\u041f\u0440\u0438\u043c\u0435\u043d\u0435\u043d\u0438\u0435 Splay-\u0434\u0435\u0440\u0435\u0432\u044c\u0435\u0432<\/h4>\n
Splay-\u0434\u0435\u0440\u0435\u0432\u044c\u044f \u0441\u0442\u0430\u043b\u0438 \u043d\u0430\u0438\u0431\u043e\u043b\u0435\u0435 \u0448\u0438\u0440\u043e\u043a\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c\u043e\u0439 \u0431\u0430\u0437\u043e\u0432\u043e\u0439 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u043e\u0439 \u0434\u0430\u043d\u043d\u044b\u0445, \u0438\u0437\u043e\u0431\u0440\u0435\u0442\u0435\u043d\u043d\u043e\u0439 \u0437\u0430 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0438\u0435 30 \u043b\u0435\u0442, \u043f\u043e\u0442\u043e\u043c\u0443 \u0447\u0442\u043e \u043e\u043d\u0438 \u044f\u0432\u043b\u044f\u044e\u0442\u0441\u044f \u0441\u0430\u043c\u044b\u043c \u0431\u044b\u0441\u0442\u0440\u044b\u043c \u0442\u0438\u043f\u043e\u043c \u0441\u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430 \u043f\u043e\u0438\u0441\u043a\u0430 \u0434\u043b\u044f \u043e\u0433\u0440\u043e\u043c\u043d\u043e\u0433\u043e \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430 \u043f\u0440\u0438\u043b\u043e\u0436\u0435\u043d\u0438\u0439.<\/p>\n
Splay-\u0434\u0435\u0440\u0435\u0432\u044c\u044f \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044e\u0442\u0441\u044f \u0432 Windows NT (\u0432 \u0432\u0438\u0440\u0442\u0443\u0430\u043b\u044c\u043d\u043e\u0439 \u043f\u0430\u043c\u044f\u0442\u0438, \u0441\u0435\u0442\u0438 \u0438 \u043a\u043e\u0434\u0435 \u0444\u0430\u0439\u043b\u043e\u0432\u043e\u0439 \u0441\u0438\u0441\u0442\u0435\u043c\u044b), \u043a\u043e\u043c\u043f\u0438\u043b\u044f\u0442\u043e\u0440\u0435 gcc \u0438 \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0435 GNU C++, \u0440\u0435\u0434\u0430\u043a\u0442\u043e\u0440\u0435 \u0441\u0442\u0440\u043e\u043a sed, \u0441\u0435\u0442\u0435\u0432\u044b\u0445 \u043c\u0430\u0440\u0448\u0440\u0443\u0442\u0438\u0437\u0430\u0442\u043e\u0440\u0430\u0445 Fore Systems, \u043d\u0430\u0438\u0431\u043e\u043b\u0435\u0435 \u043f\u043e\u043f\u0443\u043b\u044f\u0440\u043d\u043e\u0439 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 Unix malloc, \u0437\u0430\u0433\u0440\u0443\u0436\u0430\u0435\u043c\u044b\u0445 \u043c\u043e\u0434\u0443\u043b\u044f\u0445 \u044f\u0434\u0440\u0430 Linux \u0438 \u0432\u043e \u043c\u043d\u043e\u0433\u0438\u0445 \u0434\u0440\u0443\u0433\u0438\u0445 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0430\u0445 (\u0418\u0441\u0442\u043e\u0447\u043d\u0438\u043a: http:\/\/www.cs.berkeley.edu\/~jrs\/61b\/lec\/36<\/a>)<\/p>\n
\u0421\u043c\u043e\u0442\u0440\u0438\u0442\u0435 \u0442\u0430\u043a\u0436\u0435 Splay Tree | Set 2 (Insert)<\/a>.<\/p>\n
\u0421\u0441\u044b\u043b\u043a\u0438:<\/strong><\/p>\n
http:\/\/www.cs.berkeley.edu\/~jrs\/61b\/lec\/36<\/a><\/p>\n
http:\/\/www.cs.cornell.edu\/courses\/cs3110\/2009fa\/recitations\/rec-splay.html<\/a><\/p>\n
http:\/\/courses.cs.washington.edu\/courses\/cse326\/01au\/lectures\/SplayTrees.ppt<\/a><\/p>\n
\n
\n
\u0423\u0437\u043d\u0430\u0442\u044c \u043f\u043e\u0434\u0440\u043e\u0431\u043d\u0435\u0435 \u043e \u043a\u0443\u0440\u0441\u0435<\/strong><\/a> «\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».<\/p>\n
<\/strong>\u0417\u0430\u043f\u0438\u0441\u0430\u0442\u044c\u0441\u044f \u043d\u0430 \u043e\u0442\u043a\u0440\u044b\u0442\u044b\u0439 \u0432\u0435\u0431\u0438\u043d\u0430\u0440<\/strong><\/a> \u043f\u043e \u0442\u0435\u043c\u0435 «\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.»<\/strong><\/p>\n<\/blockquote>\n
 \u0420\u0435\u043a\u043b\u0430\u043c\u0430 \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u043f\u043e\u043b\u0435\u0437\u043d\u0430<\/h3>\n
\u041f\u0440\u044f\u043c\u043e \u0441\u0435\u0439\u0447\u0430\u0441 \u0432 OTUS \u0434\u0435\u0439\u0441\u0442\u0432\u0443\u044e\u0442 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0435 \u043d\u043e\u0432\u043e\u0433\u043e\u0434\u043d\u0438\u0435 \u0441\u043a\u0438\u0434\u043a\u0438 \u043d\u0430 \u0432\u0441\u0435 \u043a\u0443\u0440\u0441\u044b. \u041e\u0437\u043d\u0430\u043a\u043e\u043c\u0438\u0442\u044c\u0441\u044f \u0441 \u043f\u043e\u043b\u043d\u044b\u043c \u0441\u043f\u0438\u0441\u043a\u043e\u043c \u043a\u0443\u0440\u0441\u043e\u0432 \u0432\u044b \u043c\u043e\u0436\u0435\u0442\u0435 \u043f\u043e \u0441\u0441\u044b\u043b\u043a\u0435 \u043d\u0438\u0436\u0435. \u0422\u0430\u043a\u0436\u0435 \u0443 \u0432\u0441\u0435\u0445 \u0436\u0435\u043b\u0430\u044e\u0449\u0438\u0445 \u0435\u0441\u0442\u044c \u0443\u043d\u0438\u043a\u0430\u043b\u044c\u043d\u0430\u044f \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u043e\u0442\u043f\u0440\u0430\u0432\u0438\u0442\u044c \u0430\u0434\u0440\u0435\u0441\u0430\u0442\u0443 \u043f\u043e\u0434\u0430\u0440\u043e\u0447\u043d\u044b\u0439 \u0441\u0435\u0440\u0442\u0438\u0444\u0438\u043a\u0430\u0442 \u043d\u0430 \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u0435 \u0432 OTUS<\/a>.<\/p>\n
\u041a\u0441\u0442\u0430\u0442\u0438, \u043e «\u043a\u0440\u0430\u0441\u0438\u0432\u043e\u0439 \u0443\u043f\u0430\u043a\u043e\u0432\u043a\u0435» \u043e\u043d\u043b\u0430\u0439\u043d-\u0441\u0435\u0440\u0442\u0438\u0444\u0438\u043a\u0430\u0442\u043e\u0432 \u043c\u044b <\/em>\u0440\u0430\u0441\u0441\u043a\u0430\u0437\u044b\u0432\u0430\u0435\u043c \u0432 \u044d\u0442\u043e\u0439 \u0441\u0442\u0430\u0442\u044c\u0435<\/em><\/a>.<\/em><\/p>\n
<\/figcaption><\/figure>\n
\u0417\u0410\u0411\u0420\u0410\u0422\u042c \u0421\u041a\u0418\u0414\u041a\u0423<\/strong><\/a><\/p>\n<\/div>\n
 \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0441\u0442\u0430\u0442\u044c\u0438  https:\/\/habr.com\/ru\/company\/otus\/blog\/535316\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"\n
\n
\n
\u041f\u0440\u0438\u0432\u0435\u0442, \u0425\u0430\u0431\u0440! \u0411\u0443\u0434\u0443\u0449\u0438\u0445 \u0441\u0442\u0443\u0434\u0435\u043d\u0442\u043e\u0432 \u043a\u0443\u0440\u0441\u0430 <\/strong>«\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»<\/strong><\/a> \u043f\u0440\u0438\u0433\u043b\u0430\u0448\u0430\u0435\u043c \u043d\u0430 <\/strong>\u043e\u0442\u043a\u0440\u044b\u0442\u044b\u0439 \u0432\u0435\u0431\u0438\u043d\u0430\u0440 \u043f\u043e \u0442\u0435\u043c\u0435 «\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.»<\/strong><\/a><\/p>\n
\u0410 \u0441\u0435\u0439\u0447\u0430\u0441 \u0434\u0435\u043b\u0438\u043c\u0441\u044f \u0441 \u0432\u0430\u043c\u0438 \u0442\u0440\u0430\u0434\u0438\u0446\u0438\u043e\u043d\u043d\u044b\u043c \u043f\u0435\u0440\u0435\u0432\u043e\u0434\u043e\u043c \u043f\u043e\u043b\u0435\u0437\u043d\u043e\u0433\u043e \u043c\u0430\u0442\u0435\u0440\u0438\u0430\u043b\u0430.<\/p>\n<\/blockquote>\n
<\/figcaption><\/figure>\n
\n
\u041d\u0430\u0438\u0445\u0443\u0434\u0448\u0430\u044f \u0432\u0440\u0435\u043c\u0435\u043d\u043d\u0430\u044f \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0442\u0430\u043a\u0438\u0445 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439, \u043a\u0430\u043a \u043f\u043e\u0438\u0441\u043a, \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u0435 \u0438 \u0432\u0441\u0442\u0430\u0432\u043a\u0430, \u0434\u043b\u044f \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430 \u043f\u043e\u0438\u0441\u043a\u0430 (Binary Search Tree) \u0441\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442 O(n). \u041d\u0430\u0438\u0445\u0443\u0434\u0448\u0438\u0439 \u0441\u043b\u0443\u0447\u0430\u0439 \u0441\u043b\u0443\u0447\u0430\u0439 \u0432\u043e\u0437\u043d\u0438\u043a\u0430\u0435\u0442, \u043a\u043e\u0433\u0434\u0430 \u0434\u0435\u0440\u0435\u0432\u043e \u043d\u0435\u0441\u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u043e\u0432\u0430\u043d\u043e. \u041c\u044b \u043c\u043e\u0436\u0435\u043c \u0443\u043b\u0443\u0447\u0448\u0438\u0442\u044c \u043d\u0430\u0438\u0445\u0443\u0434\u0448\u0438\u0439 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u0432\u0440\u0435\u043c\u0435\u043d\u043d\u043e\u0439 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u0438 \u0434\u043e O(log n) \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u043a\u0440\u0430\u0441\u043d\u043e-\u0447\u0435\u0440\u043d\u044b\u0445 \u0438 \u0410\u0412\u041b-\u0434\u0435\u0440\u0435\u0432\u044c\u0435\u0432<\/a>.<\/p>\n
\u041c\u043e\u0436\u0435\u043c \u043b\u0438 \u043c\u044b \u0434\u043e\u0431\u0438\u0442\u044c\u0441\u044f \u043d\u0430 \u043f\u0440\u0430\u043a\u0442\u0438\u043a\u0435 \u043b\u0443\u0447\u0448\u0435\u0433\u043e \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0430, \u0447\u0435\u043c \u0442\u043e\u0442, \u0447\u0442\u043e \u043d\u0430\u043c \u0434\u0430\u044e\u0442 \u043a\u0440\u0430\u0441\u043d\u043e-\u0447\u0435\u0440\u043d\u044b\u0435 \u0438\u043b\u0438 \u0410\u0412\u041b-\u0434\u0435\u0440\u0435\u0432\u044c\u044f?<\/strong><\/p>\n
\u041f\u043e\u0434\u043e\u0431\u043d\u043e \u043a\u0440\u0430\u0441\u043d\u043e-\u0447\u0435\u0440\u043d\u044b\u043c \u0438 \u0410\u0412\u041b-\u0434\u0435\u0440\u0435\u0432\u044c\u044f\u043c<\/a>, Splay-\u0434\u0435\u0440\u0435\u0432\u043e (\u0438\u043b\u0438 \u043a\u043e\u0441\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e<\/em>) \u0442\u0430\u043a\u0436\u0435 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0441\u0430\u043c\u043e\u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u0443\u044e\u0449\u0438\u043c\u0441\u044f \u0431\u0438\u043d\u0430\u0440\u043d\u044b\u043c \u0434\u0435\u0440\u0435\u0432\u043e\u043c \u043f\u043e\u0438\u0441\u043a\u0430<\/a>. \u041e\u0441\u043d\u043e\u0432\u043d\u0430\u044f \u0438\u0434\u0435\u044f splay-\u0434\u0435\u0440\u0435\u0432\u0430 \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e\u0431\u044b \u043f\u043e\u043c\u0435\u0449\u0430\u0442\u044c \u044d\u043b\u0435\u043c\u0435\u043d\u0442, \u043a \u043a\u043e\u0442\u043e\u0440\u043e\u043c\u0443 \u043d\u0435\u0434\u0430\u0432\u043d\u043e \u043e\u0441\u0443\u0449\u0435\u0441\u0442\u0432\u043b\u044f\u043b\u0441\u044f \u0434\u043e\u0441\u0442\u0443\u043f, \u0432 \u043a\u043e\u0440\u0435\u043d\u044c \u0434\u0435\u0440\u0435\u0432\u0430, \u0447\u0442\u043e \u0434\u0435\u043b\u0430\u0435\u0442 \u044d\u0442\u043e\u0442 \u044d\u043b\u0435\u043c\u0435\u043d\u0442, \u0434\u043e\u0441\u0442\u0443\u043f\u043d\u044b\u043c \u0437\u0430 \u0432\u0440\u0435\u043c\u044f \u043f\u043e\u0440\u044f\u0434\u043a\u0430 O(1) \u043f\u0440\u0438 \u043f\u043e\u0432\u0442\u043e\u0440\u043d\u043e\u043c \u0434\u043e\u0441\u0442\u0443\u043f\u0435. \u0412\u0441\u044f \u0441\u0443\u0442\u044c \u0437\u0430\u043a\u043b\u044e\u0447\u0430\u0435\u0442\u0441\u044f \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e\u0431\u044b \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u043a\u043e\u043d\u0446\u0435\u043f\u0446\u0438\u044e \u043b\u043e\u043a\u0430\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u0441\u0441\u044b\u043b\u043e\u043a (\u0432 \u0441\u0440\u0435\u0434\u043d\u0435\u0441\u0442\u0430\u0442\u0438\u0441\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u043c \u043f\u0440\u0438\u043b\u043e\u0436\u0435\u043d\u0438\u0438 80% \u043e\u0431\u0440\u0430\u0449\u0435\u043d\u0438\u0439 \u043f\u0440\u0438\u0445\u043e\u0434\u044f\u0442\u0441\u044f \u043d\u0430 20% \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432). \u041f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u044c\u0442\u0435 \u0441\u0435\u0431\u0435 \u0441\u0438\u0442\u0443\u0430\u0446\u0438\u044e, \u043a\u043e\u0433\u0434\u0430 \u0443 \u043d\u0430\u0441 \u0435\u0441\u0442\u044c \u043c\u0438\u043b\u043b\u0438\u043e\u043d\u044b \u0438\u043b\u0438 \u0434\u0430\u0436\u0435 \u043c\u0438\u043b\u043b\u0438\u0430\u0440\u0434\u044b \u043a\u043b\u044e\u0447\u0435\u0439, \u0438 \u043b\u0438\u0448\u044c \u043a \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u043c \u0438\u0437 \u043d\u0438\u0445 \u043e\u0431\u0440\u0430\u0449\u0430\u044e\u0442\u0441\u044f \u0440\u0435\u0433\u0443\u043b\u044f\u0440\u043d\u043e, \u0447\u0442\u043e \u0432\u0435\u0441\u044c\u043c\u0430 \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e \u0434\u043b\u044f \u043c\u043d\u043e\u0433\u0438\u0445 \u0442\u0438\u043f\u0438\u0447\u043d\u044b\u0445 \u043f\u0440\u0438\u043b\u043e\u0436\u0435\u043d\u0438\u044f\u0445.<\/p>\n
\u0412\u0441\u0435 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u0441\u043e splay-\u0434\u0435\u0440\u0435\u0432\u043e\u043c \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u044e\u0442\u0441\u044f \u0432 \u0441\u0440\u0435\u0434\u043d\u0435\u043c \u0437\u0430 \u0432\u0440\u0435\u043c\u044f \u043f\u043e\u0440\u044f\u0434\u043a\u0430 O(log n), \u0433\u0434\u0435 n — \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0432 \u0434\u0435\u0440\u0435\u0432\u0435. \u041b\u044e\u0431\u0430\u044f \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u0430\u044f \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044f \u0432 \u0445\u0443\u0434\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u043c\u043e\u0436\u0435\u0442 \u0437\u0430\u043d\u044f\u0442\u044c \u0432\u0440\u0435\u043c\u044f \u043f\u043e\u0440\u044f\u0434\u043a\u0430 \u0422\u044d\u0442\u0430(n).<\/p>\n
\u041e\u043f\u0435\u0440\u0430\u0446\u0438\u044f \u043f\u043e\u0438\u0441\u043a\u0430 <\/h3>\n
\u041e\u043f\u0435\u0440\u0430\u0446\u0438\u044f \u043f\u043e\u0438\u0441\u043a\u0430 \u0432 splay-\u0434\u0435\u0440\u0435\u0432\u0435 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442 \u0441\u043e\u0431\u043e\u0439 \u0441\u0442\u0430\u043d\u0434\u0430\u0440\u0442\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u043e\u0438\u0441\u043a\u0430 \u0432 \u0431\u0438\u043d\u0430\u0440\u043d\u043e\u043c \u0434\u0435\u0440\u0435\u0432\u0435, \u043f\u043e\u0441\u043b\u0435 \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u043e \u0432\u044b\u0432\u043e\u0440\u0430\u0447\u0438\u0432\u0430\u0435\u0442\u0441\u044f (\u0438\u0441\u043a\u043e\u043c\u044b\u0439 \u0443\u0437\u0435\u043b \u043f\u0435\u0440\u0435\u043c\u0435\u0449\u0430\u0435\u0442\u0441\u044f \u0432 \u043a\u043e\u0440\u0435\u043d\u044c \u2014 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044f splay). \u0415\u0441\u043b\u0438 \u043f\u043e\u0438\u0441\u043a \u0437\u0430\u0432\u0435\u0440\u0448\u0438\u043b\u0441\u044f \u0443\u0441\u043f\u0435\u0445\u043e\u043c, \u0442\u043e \u043d\u0430\u0439\u0434\u0435\u043d\u043d\u044b\u0439 \u0443\u0437\u0435\u043b \u043f\u043e\u0434\u043d\u0438\u043c\u0430\u0435\u0442\u0441\u044f \u043d\u0430\u0432\u0435\u0440\u0445 \u0438 \u0441\u0442\u0430\u043d\u043e\u0432\u0438\u0442\u0441\u044f \u043d\u043e\u0432\u044b\u043c \u043a\u043e\u0440\u043d\u0435\u043c. \u0412 \u043f\u0440\u043e\u0442\u0438\u0432\u043d\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u043a\u043e\u0440\u043d\u0435\u043c \u0441\u0442\u0430\u043d\u043e\u0432\u0438\u0442\u0441\u044f \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0438\u0439 \u0443\u0437\u0435\u043b, \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 \u0434\u043e \u0434\u043e\u0441\u0442\u0438\u0436\u0435\u043d\u0438\u044f NULL.<\/p>\n
\u0412 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0435 \u043e\u0441\u0443\u0449\u0435\u0441\u0442\u0432\u043b\u0435\u043d\u0438\u044f \u0434\u043e\u0441\u0442\u0443\u043f\u0430 \u043a \u0443\u0437\u043b\u0443 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0435 \u0441\u043b\u0443\u0447\u0430\u0438:<\/p>\n
1.<\/strong> \u0423\u0437\u0435\u043b \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043a\u043e\u0440\u043d\u0435\u0432\u044b\u043c.<\/strong> \u041c\u044b \u043f\u0440\u043e\u0441\u0442\u043e \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u043c \u043a\u043e\u0440\u0435\u043d\u044c, \u0431\u043e\u043b\u044c\u0448\u0435 \u043d\u0438\u0447\u0435\u0433\u043e \u043d\u0435 \u0434\u0435\u043b\u0430\u0435\u043c, \u0442\u0430\u043a \u043a\u0430\u043a \u0443\u0437\u0435\u043b, \u043a \u043a\u043e\u0442\u043e\u0440\u043e\u043c\u0443 \u043e\u0441\u0443\u0449\u0435\u0441\u0442\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0434\u043e\u0441\u0442\u0443\u043f, \u0443\u0436\u0435 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043a\u043e\u0440\u043d\u0435\u0432\u044b\u043c.<\/p>\n
2. Zig: \u0443\u0437\u0435\u043b \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0434\u043e\u0447\u0435\u0440\u043d\u0438\u043c \u043f\u043e \u043e\u0442\u043d\u043e\u0448\u0435\u043d\u0438\u044e \u043a \u043a\u043e\u0440\u043d\u044e<\/strong> <\/em>(\u0443 \u0443\u0437\u043b\u0430 \u043d\u0435\u0442 \u043f\u0440\u0430\u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044f). \u0423\u0437\u0435\u043b \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043b\u0438\u0431\u043e \u043b\u0435\u0432\u044b\u043c \u043f\u043e\u0442\u043e\u043c\u043a\u043e\u043c \u043a\u043e\u0440\u043d\u044f (\u043c\u044b \u0434\u0435\u043b\u0430\u0435\u043c \u043f\u0440\u0430\u0432\u044b\u0439 \u0440\u0430\u0437\u0432\u043e\u0440\u043e\u0442), \u043b\u0438\u0431\u043e \u043f\u0440\u0430\u0432\u044b\u043c \u043f\u043e\u0442\u043e\u043c\u043a\u043e\u043c \u0441\u0432\u043e\u0435\u0433\u043e \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044f (\u043c\u044b \u0434\u0435\u043b\u0430\u0435\u043c \u043b\u0435\u0432\u044b\u0439 \u0440\u0430\u0437\u0432\u043e\u0440\u043e\u0442).<\/p>\n
T1, T2 \u0438 T3 \u2014 \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u044c\u044f \u0434\u0435\u0440\u0435\u0432\u0430 \u0441 \u043a\u043e\u0440\u043d\u0435\u043c y (\u0441\u043b\u0435\u0432\u0430) \u0438\u043b\u0438 x (\u0441\u043f\u0440\u0430\u0432\u0430)<\/p>\n
<\/figcaption><\/figure>\n
3. \u0423 \u0443\u0437\u043b\u0430 \u0435\u0441\u0442\u044c \u0438 \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044c, \u0438 \u043f\u0440\u0430\u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044c<\/em><\/strong>. \u0412\u043e\u0437\u043c\u043e\u0436\u043d\u044b \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0435 \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u044b:<\/p>\n
\u0430) Zig-Zig \u0438 Zag-Zag.<\/strong> \u0423\u0437\u0435\u043b \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043b\u0435\u0432\u044b\u043c \u043f\u043e\u0442\u043e\u043c\u043a\u043e\u043c \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u0441\u043a\u043e\u0433\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430, \u0438 \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044c \u0442\u0430\u043a\u0436\u0435 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043b\u0435\u0432\u044b\u043c \u043f\u043e\u0442\u043e\u043c\u043a\u043e\u043c \u043f\u0440\u0430\u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044f (\u0434\u0432\u0430 \u0440\u0430\u0437\u0432\u043e\u0440\u043e\u0442\u0430 \u0432\u043f\u0440\u0430\u0432\u043e) \u0418\u041b\u0418 \u0443\u0437\u0435\u043b \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043f\u0440\u0430\u0432\u044b\u043c \u043f\u043e\u0442\u043e\u043c\u043a\u043e\u043c \u0441\u0432\u043e\u0435\u0433\u043e \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u0441\u043a\u043e\u0433\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430, \u0438 \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044c \u0442\u0430\u043a\u0436\u0435 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043f\u0440\u0430\u0432\u044b\u043c \u043f\u043e\u0442\u043e\u043c\u043a\u043e\u043c \u0441\u0432\u043e\u0435\u0433\u043e \u043f\u0440\u0430\u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044c (\u0434\u0432\u0430 \u0440\u0430\u0437\u0432\u043e\u0440\u043e\u0442\u0430 \u0432\u043b\u0435\u0432\u043e).<\/p>\n
<\/figcaption><\/figure>\n
\u0431) Zig-Zag \u0438 Zag-Zig.<\/strong> \u0423\u0437\u0435\u043b \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043b\u0435\u0432\u044b\u043c \u043f\u043e\u0442\u043e\u043c\u043a\u043e\u043c \u043f\u043e \u043e\u0442\u043d\u043e\u0448\u0435\u043d\u0438\u044e \u043a \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u0441\u043a\u043e\u043c\u0443 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0443, \u0430 \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044c \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043f\u0440\u0430\u0432\u044b\u043c \u043f\u043e\u0442\u043e\u043c\u043a\u043e\u043c \u043f\u0440\u0430\u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044f (\u0440\u0430\u0437\u0432\u043e\u0440\u043e\u0442 \u0432\u043b\u0435\u0432\u043e \u0441 \u043f\u043e\u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u043c \u0440\u0430\u0437\u0432\u043e\u0440\u043e\u0442\u043e\u043c \u0432\u043f\u0440\u0430\u0432\u043e) \u0418\u041b\u0418 \u0443\u0437\u0435\u043b \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043f\u0440\u0430\u0432\u044b\u043c \u043f\u043e\u0442\u043e\u043c\u043a\u043e\u043c \u0441\u0432\u043e\u0435\u0433\u043e \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u0441\u043a\u043e\u0433\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430, \u0430 \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044c \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043b\u0435\u0432\u044b\u043c \u043f\u043e\u0442\u043e\u043c\u043a\u043e\u043c \u043f\u0440\u0430\u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044f (\u0440\u0430\u0437\u0432\u043e\u0440\u043e\u0442 \u0432\u043f\u0440\u0430\u0432\u043e \u0441 \u043f\u043e\u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u043c \u0440\u0430\u0437\u0432\u043e\u0440\u043e\u0442\u043e\u043c \u0432\u043b\u0435\u0432\u043e).<\/p>\n
<\/figcaption><\/figure>\n
\u041f\u0440\u0438\u043c\u0435\u0440:<\/strong><\/p>\n
<\/figcaption><\/figure>\n
\u0412\u0430\u0436\u043d\u043e \u043e\u0442\u043c\u0435\u0442\u0438\u0442\u044c, \u0447\u0442\u043e \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044f \u043f\u043e\u0438\u0441\u043a\u0430 \u0438\u043b\u0438 \u0440\u0430\u0437\u0432\u043e\u0440\u043e\u0442\u0430 (splay) \u043d\u0435 \u0442\u043e\u043b\u044c\u043a\u043e \u043f\u0435\u0440\u0435\u043d\u043e\u0441\u0438\u0442 \u043d\u0430\u0439\u0434\u0435\u043d\u043d\u044b\u0439 \u043a\u043b\u044e\u0447 \u0432 \u043a\u043e\u0440\u0435\u043d\u044c, \u043d\u043e \u0442\u0430\u043a\u0436\u0435 \u0443\u0440\u0430\u0432\u043d\u043e\u0432\u0435\u0448\u0438\u0432\u0430\u0435\u0442 \u0434\u0435\u0440\u0435\u0432\u043e. \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440 \u0432 \u0441\u043b\u0443\u0447\u0430\u0435 \u0432\u044b\u0448\u0435, \u0432\u044b\u0441\u043e\u0442\u0430 \u0434\u0435\u0440\u0435\u0432\u0430 \u0443\u043c\u0435\u043d\u044c\u0448\u0430\u0435\u0442\u0441\u044f \u043d\u0430 1.<\/p>\n
 \u0420\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438:<\/h4>\n
C++<\/h3>\n
#include <bits\/stdc++.h>  using namespace std;   \/\/ An AVL tree node  class node  {  \tpublic:  \tint key;  \tnode *left, *right;  };   \/* Helper function that allocates  a new node with the given key and  \tNULL left and right pointers. *\/ node* newNode(int key)  {  \tnode* Node = new node();  \tNode->key = key;  \tNode->left = Node->right = NULL;  \treturn (Node);  }   \/\/ A utility function to right  \/\/ rotate subtree rooted with y  \/\/ See the diagram given above.  node *rightRotate(node *x)  {  \tnode *y = x->left;  \tx->left = y->right;  \ty->right = x;  \treturn y;  }   \/\/ A utility function to left  \/\/ rotate subtree rooted with x  \/\/ See the diagram given above.  node *leftRotate(node *x)  {  \tnode *y = x->right;  \tx->right = y->left;  \ty->left = x;  \treturn y;  }   \/\/ This function brings the key at  \/\/ root if key is present in tree.  \/\/ If key is not present, then it  \/\/ brings the last accessed item at  \/\/ root. This function modifies the  \/\/ tree and returns the new root  node *splay(node *root, int key)  {  \t\/\/ Base cases: root is NULL or  \t\/\/ key is present at root  \tif (root == NULL || root->key == key)  \t\treturn root;   \t\/\/ Key lies in left subtree  \tif (root->key > key)  \t{  \t\t\/\/ Key is not in tree, we are done  \t\tif (root->left == NULL) return root;   \t\t\/\/ Zig-Zig (Left Left)  \t\tif (root->left->key > key)  \t\t{  \t\t\t\/\/ First recursively bring the  \t\t\t\/\/ key as root of left-left  \t\t\troot->left->left = splay(root->left->left, key);   \t\t\t\/\/ Do first rotation for root,  \t\t\t\/\/ second rotation is done after else  \t\t\troot = rightRotate(root);  \t\t}  \t\telse if (root->left->key < key) \/\/ Zig-Zag (Left Right)  \t\t{  \t\t\t\/\/ First recursively bring  \t\t\t\/\/ the key as root of left-right  \t\t\troot->left->right = splay(root->left->right, key);   \t\t\t\/\/ Do first rotation for root->left  \t\t\tif (root->left->right != NULL)  \t\t\t\troot->left = leftRotate(root->left);  \t\t}   \t\t\/\/ Do second rotation for root  \t\treturn (root->left == NULL)? root: rightRotate(root);  \t}  \telse \/\/ Key lies in right subtree  \t{  \t\t\/\/ Key is not in tree, we are done  \t\tif (root->right == NULL) return root;   \t\t\/\/ Zag-Zig (Right Left)  \t\tif (root->right->key > key)  \t\t{  \t\t\t\/\/ Bring the key as root of right-left  \t\t\troot->right->left = splay(root->right->left, key);   \t\t\t\/\/ Do first rotation for root->right  \t\t\tif (root->right->left != NULL)  \t\t\t\troot->right = rightRotate(root->right);  \t\t}  \t\telse if (root->right->key < key)\/\/ Zag-Zag (Right Right)  \t\t{  \t\t\t\/\/ Bring the key as root of  \t\t\t\/\/ right-right and do first rotation  \t\t\troot->right->right = splay(root->right->right, key);  \t\t\troot = leftRotate(root);  \t\t}   \t\t\/\/ Do second rotation for root  \t\treturn (root->right == NULL)? root: leftRotate(root);  \t}  }   \/\/ The search function for Splay tree.  \/\/ Note that this function returns the  \/\/ new root of Splay Tree. If key is  \/\/ present in tree then, it is moved to root.  node *search(node *root, int key)  {  \treturn splay(root, key);  }   \/\/ A utility function to print  \/\/ preorder traversal of the tree.  \/\/ The function also prints height of every node  void preOrder(node *root)  {  \tif (root != NULL)  \t{  \t\tcout<<root->key<<\" \";  \t\tpreOrder(root->left);  \t\tpreOrder(root->right);  \t}  }   \/* Driver code*\/ int main()  {  \tnode *root = newNode(100);  \troot->left = newNode(50);  \troot->right = newNode(200);  \troot->left->left = newNode(40);  \troot->left->left->left = newNode(30);  \troot->left->left->left->left = newNode(20);   \troot = search(root, 20);  \tcout << \"Preorder traversal of the modified Splay tree is \\n\";  \tpreOrder(root);  \treturn 0;  }   \/\/ This code is contributed by rathbhupendra <\/code><\/pre>\n
C<\/h3>\n
\/\/ The code is adopted from http:\/\/goo.gl\/SDH9hH  #include<stdio.h>  #include<stdlib.h>   \/\/ An AVL tree node  struct node  {  \tint key;  \tstruct node *left, *right;  };   \/* Helper function that allocates a new node with the given key and  \tNULL left and right pointers. *\/ struct node* newNode(int key)  {  \tstruct node* node = (struct node*)malloc(sizeof(struct node));  \tnode->key = key;  \tnode->left = node->right = NULL;  \treturn (node);  }   \/\/ A utility function to right rotate subtree rooted with y  \/\/ See the diagram given above.  struct node *rightRotate(struct node *x)  {  \tstruct node *y = x->left;  \tx->left = y->right;  \ty->right = x;  \treturn y;  }   \/\/ A utility function to left rotate subtree rooted with x  \/\/ See the diagram given above.  struct node *leftRotate(struct node *x)  {  \tstruct node *y = x->right;  \tx->right = y->left;  \ty->left = x;  \treturn y;  }   \/\/ This function brings the key at root if key is present in tree.  \/\/ If key is not present, then it brings the last accessed item at  \/\/ root. This function modifies the tree and returns the new root  struct node *splay(struct node *root, int key)  {  \t\/\/ Base cases: root is NULL or key is present at root  \tif (root == NULL || root->key == key)  \t\treturn root;   \t\/\/ Key lies in left subtree  \tif (root->key > key)  \t{  \t\t\/\/ Key is not in tree, we are done  \t\tif (root->left == NULL) return root;   \t\t\/\/ Zig-Zig (Left Left)  \t\tif (root->left->key > key)  \t\t{  \t\t\t\/\/ First recursively bring the key as root of left-left  \t\t\troot->left->left = splay(root->left->left, key);   \t\t\t\/\/ Do first rotation for root, second rotation is done after else  \t\t\troot = rightRotate(root);  \t\t}  \t\telse if (root->left->key < key) \/\/ Zig-Zag (Left Right)  \t\t{  \t\t\t\/\/ First recursively bring the key as root of left-right  \t\t\troot->left->right = splay(root->left->right, key);   \t\t\t\/\/ Do first rotation for root->left  \t\t\tif (root->left->right != NULL)  \t\t\t\troot->left = leftRotate(root->left);  \t\t}   \t\t\/\/ Do second rotation for root  \t\treturn (root->left == NULL)? root: rightRotate(root);  \t}  \telse \/\/ Key lies in right subtree  \t{  \t\t\/\/ Key is not in tree, we are done  \t\tif (root->right == NULL) return root;   \t\t\/\/ Zag-Zig (Right Left)  \t\tif (root->right->key > key)  \t\t{  \t\t\t\/\/ Bring the key as root of right-left  \t\t\troot->right->left = splay(root->right->left, key);   \t\t\t\/\/ Do first rotation for root->right  \t\t\tif (root->right->left != NULL)  \t\t\t\troot->right = rightRotate(root->right);  \t\t}  \t\telse if (root->right->key < key)\/\/ Zag-Zag (Right Right)  \t\t{  \t\t\t\/\/ Bring the key as root of right-right and do first rotation  \t\t\troot->right->right = splay(root->right->right, key);  \t\t\troot = leftRotate(root);  \t\t}   \t\t\/\/ Do second rotation for root  \t\treturn (root->right == NULL)? root: leftRotate(root);  \t}  }   \/\/ The search function for Splay tree. Note that this function  \/\/ returns the new root of Splay Tree. If key is present in tree  \/\/ then, it is moved to root.  struct node *search(struct node *root, int key)  {  \treturn splay(root, key);  }<\/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-315679","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/315679","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=315679"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/315679\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=315679"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=315679"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=315679"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}