{"id":464011,"date":"2025-06-20T21:01:08","date_gmt":"2025-06-20T21:01:08","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=464011"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=464011","title":{"rendered":"<span>\u041a\u0440\u0430\u0441\u043d\u043e-\u0447\u0451\u0440\u043d\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e: \u043f\u043e\u043b\u043d\u0430\u044f \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u043d\u0430 C#<\/span>"},"content":{"rendered":"<div><!--[--><!--]--><\/div>\n<div id=\"post-content-body\">\n<div>\n<div class=\"article-formatted-body article-formatted-body article-formatted-body_version-2\">\n<div xmlns=\"http:\/\/www.w3.org\/1999\/xhtml\">\n<figure class=\"full-width\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/11d\/955\/39c\/11d95539cf744396d1800083efa54f39.png\" width=\"780\" height=\"441\" sizes=\"auto, (max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/r\/w780\/getpro\/habr\/upload_files\/11d\/955\/39c\/11d95539cf744396d1800083efa54f39.png 780w,&#10;       https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/11d\/955\/39c\/11d95539cf744396d1800083efa54f39.png 781w\" loading=\"lazy\" decode=\"async\"\/><\/figure>\n<p>\u0427\u0442\u043e \u043c\u043e\u0436\u0435\u0442 \u0437\u0430\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u043e\u0431\u0440\u0430\u0442\u0438\u0442\u044c \u0432\u043d\u0438\u043c\u0430\u043d\u0438\u0435 \u043d\u0430 <a href=\"https:\/\/en.wikipedia.org\/wiki\/Red%E2%80%93black_tree\" rel=\"noopener noreferrer nofollow\">\u043a\u0440\u0430\u0441\u043d\u043e-\u0447\u0451\u0440\u043d\u044b\u0435 \u0434\u0435\u0440\u0435\u0432\u044c\u044f<\/a>, \u0438 \u043a\u0430\u043a \u0438\u0445 \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u0442\u044c? \u0421\u0442\u0430\u0442\u044c\u044f \u043e\u0442\u0432\u0435\u0442\u0438\u0442 \u043d\u0430 \u043e\u0431\u0430 \u044d\u0442\u0438 \u0432\u043e\u043f\u0440\u043e\u0441\u0430. \u0411\u043e\u043d\u0443\u0441\u043e\u043c \u0431\u0443\u0434\u0435\u0442 \u043f\u043e\u043a\u0430\u0437\u0430\u043d\u043e, \u043a\u0430\u043a \u043d\u0430 \u043e\u0441\u043d\u043e\u0432\u0435 \u043a\u0440\u0430\u0441\u043d\u043e-\u0447\u0451\u0440\u043d\u043e\u0433\u043e \u0441\u043a\u043e\u043d\u0441\u0442\u0440\u0443\u0438\u0440\u043e\u0432\u0430\u0442\u044c <a href=\"https:\/\/en.wikipedia.org\/wiki\/Interval_tree\" rel=\"noopener noreferrer nofollow\">\u0434\u0435\u0440\u0435\u0432\u043e \u0438\u043d\u0442\u0435\u0440\u0432\u0430\u043b\u043e\u0432<\/a>.<\/p>\n<hr\/>\n<p>\u0412\u0430\u0436\u043d\u043e\u0435 \u0437\u0430\u043c\u0435\u0447\u0430\u043d\u0438\u0435: \u0441\u0442\u0430\u0442\u044c\u044f \u0444\u043e\u043a\u0443\u0441\u0438\u0440\u0443\u0435\u0442\u0441\u044f \u043d\u0430 \u043a\u043e\u0434\u0435. \u201c\u041e\u201d \u0431\u043e\u043b\u044c\u0448\u043e\u0435, \u0434\u0432\u043e\u0438\u0447\u043d\u044b\u0435 \u0434\u0435\u0440\u0435\u0432\u044c\u044f, \u0441\u0432\u044f\u0437\u043d\u044b\u0435 \u0441\u043f\u0438\u0441\u043a\u0438 \u2014 \u0432\u0441\u0451 \u044d\u0442\u043e \u043e\u0441\u0442\u0430\u043d\u0435\u0442\u0441\u044f \u0437\u0430 \u043a\u0430\u0434\u0440\u043e\u043c. \u0421\u0442\u0430\u0442\u044c\u0438 \u0446\u0435\u043d\u043d\u044b \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b\u044c\u043d\u043e\u0441\u0442\u044c\u044e \u043c\u0430\u0442\u0435\u0440\u0438\u0430\u043b\u0430, \u0430 \u043f\u0435\u0440\u0435\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u044b\u0435 \u0432\u0435\u0449\u0438 (\u0432\u043a\u043b\u044e\u0447\u0430\u044f \u043c\u0435\u0445\u0430\u043d\u0438\u043a\u0443 \u043a\u0440\u0430\u0441\u043d\u043e-\u0447\u0451\u0440\u043d\u044b\u0445 \u0434\u0435\u0440\u0435\u0432\u044c\u0435\u0432) \u043e\u0431\u0441\u0443\u0436\u0434\u0430\u043b\u0438\u0441\u044c \u0443\u0436\u0435 \u043c\u043d\u043e\u0433\u043e \u0440\u0430\u0437, \u0432 \u0442\u043e\u043c \u0447\u0438\u0441\u043b\u0435 \u0438 \u0437\u0434\u0435\u0441\u044c, \u043d\u0430 \u0425\u0430\u0431\u0440\u0435.<\/p>\n<p>\u0415\u0441\u043b\u0438 \u0436\u0430\u0436\u0434\u0430 \u0433\u043e\u0442\u043e\u0432\u044b\u0445 \u0440\u0435\u0448\u0435\u043d\u0438\u0439 \u0443 \u0432\u0430\u0441 \u0442\u0430\u043a \u0436\u0435 \u0441\u0438\u043b\u044c\u043d\u0430, \u043a\u0430\u043a \u0431\u044b\u043b\u0430 \u0443 \u043c\u0435\u043d\u044f \u043f\u043e\u043b\u0433\u043e\u0434\u0430 \u043d\u0430\u0437\u0430\u0434, \u043a\u043e\u0433\u0434\u0430 \u044f \u043d\u0430\u0447\u0438\u043d\u0430\u043b \u0440\u0430\u0437\u0431\u0438\u0440\u0430\u0442\u044c\u0441\u044f \u0441 \u0442\u0435\u043c\u043e\u0439, \u0442\u043e \u043c\u043e\u0436\u0435\u0442\u0435 \u0441\u0440\u0430\u0437\u0443 \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u0438\u0442\u044c \u043a \u0440\u0430\u0437\u0434\u0435\u043b\u0443 <a href=\"#construction\" rel=\"noopener noreferrer nofollow\">\u041f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u0435<\/a>. \u0418\u043b\u0438 \u0432\u043e\u043e\u0431\u0449\u0435 \u0432 <a href=\"#conclusion\" rel=\"noopener noreferrer nofollow\">\u043a\u043e\u043d\u0435\u0446 \u0441\u0442\u0430\u0442\u044c\u0438<\/a> \u043a \u0441\u0441\u044b\u043b\u043a\u0430\u043c \u043d\u0430 \u0444\u0430\u0439\u043b\u044b.<\/p>\n<h2>\u041e\u0433\u043b\u0430\u0432\u043b\u0435\u043d\u0438\u0435<\/h2>\n<ul>\n<li>\n<p><a href=\"#why\" rel=\"noopener noreferrer nofollow\">\u0417\u0430\u0447\u0435\u043c?<\/a><\/p>\n<\/li>\n<li>\n<p><a href=\"#construction\" rel=\"noopener noreferrer nofollow\">\u041f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u0435<\/a><\/p>\n<\/li>\n<li>\n<p><a href=\"#intervaltree\" rel=\"noopener noreferrer nofollow\">\u0414\u0435\u0440\u0435\u0432\u043e \u0438\u043d\u0442\u0435\u0440\u0432\u0430\u043b\u043e\u0432<\/a><\/p>\n<\/li>\n<li>\n<p><a href=\"#conclusion\" rel=\"noopener noreferrer nofollow\">\u0417\u0430\u043a\u043b\u044e\u0447\u0435\u043d\u0438\u0435<\/a><\/p>\n<\/li>\n<\/ul>\n<p><a class=\"anchor\" name=\"why\" id=\"why\"><\/a><\/p>\n<h2>\u0417\u0430\u0447\u0435\u043c?<\/h2>\n<p>\u041f\u0435\u0440\u0435\u0434 \u0442\u0435\u043c, \u043a\u0430\u043a \u043e\u043a\u0443\u043d\u0443\u0442\u044c\u0441\u044f \u0432 \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u043e\u043d\u043d\u0443\u044e \u0431\u043e\u0442\u0430\u043d\u0438\u043a\u0443, \u043e\u0442\u0432\u0435\u0447\u0443 \u043d\u0430 \u0432\u043e\u043f\u0440\u043e\u0441, \u0437\u0430\u0434\u0430\u043d\u043d\u044b\u0439 \u0432 \u043d\u0430\u0447\u0430\u043b\u0435 \u0441\u0442\u0430\u0442\u044c\u0438. \u0412\u043e\u0437\u043d\u0438\u043a\u043b\u0430 \u0437\u0430\u0434\u0430\u0447\u0430:<\/p>\n<ul>\n<li>\n<p>\u043d\u0443\u0436\u043d\u0430 \u0443\u043f\u043e\u0440\u044f\u0434\u043e\u0447\u0435\u043d\u043d\u0430\u044f (\u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u0430\u044f \u043f\u043e \u043d\u0435\u043a\u043e\u0435\u043c\u0443 \u0430\u0442\u0440\u0438\u0431\u0443\u0442\u0443) \u043a\u043e\u043b\u043b\u0435\u043a\u0446\u0438\u044f \u043e\u0431\u044a\u0435\u043a\u0442\u043e\u0432;<\/p>\n<\/li>\n<li>\n<p>\u043f\u043e\u0440\u044f\u0434\u043e\u043a \u043d\u0435 \u0434\u043e\u043b\u0436\u0435\u043d \u043d\u0430\u0440\u0443\u0448\u0430\u0442\u044c\u0441\u044f \u043f\u0440\u0438 \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u0438 \u0438 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u0438 \u0434\u0430\u043d\u043d\u044b\u0445;<\/p>\n<\/li>\n<li>\n<p>\u0443\u043a\u0430\u0437\u0430\u043d\u043d\u044b\u0435 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438, \u0430 \u0442\u0430\u043a\u0436\u0435 \u043f\u043e\u0438\u0441\u043a \u043e\u0431\u044a\u0435\u043a\u0442\u0430 \u0432 \u043a\u043e\u043b\u043b\u0435\u043a\u0446\u0438\u0438 \u0441\u043b\u0435\u0434\u0443\u0435\u0442 \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0442\u044c \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e \u0431\u044b\u0441\u0442\u0440\u043e.<\/p>\n<\/li>\n<\/ul>\n<p>\u041a\u0430\u043a \u0438 \u0443 \u043f\u0440\u043e\u0448\u043b\u044b\u0445 \u043c\u043e\u0438\u0445 \u0441\u0442\u0430\u0442\u0435\u0439, \u0443 \u044d\u0442\u043e\u0439 \u043d\u043e\u0433\u0438 \u0440\u0430\u0441\u0442\u0443\u0442 \u0438\u0437 \u0440\u0430\u0431\u043e\u0442\u044b \u043d\u0430\u0434 \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u043e\u0439 <a href=\"https:\/\/github.com\/melanchall\/drywetmidi\" rel=\"noopener noreferrer nofollow\">DryWetMIDI<\/a>. \u041d\u0435\u0434\u0430\u0432\u043d\u0438\u0439 <a href=\"https:\/\/github.com\/melanchall\/drywetmidi\/releases\/tag\/v8.0.0\" rel=\"noopener noreferrer nofollow\">\u0440\u0435\u043b\u0438\u0437<\/a> \u043f\u043e\u0437\u0432\u043e\u043b\u0438\u043b \u0432\u043d\u043e\u0441\u0438\u0442\u044c \u0438\u0437\u043c\u0435\u043d\u0435\u043d\u0438\u044f \u0432 \u0432\u043e\u0441\u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u043c\u044b\u0435 \u043e\u0431\u044a\u0435\u043a\u0442\u044b (MIDI-\u0441\u043e\u0431\u044b\u0442\u0438\u044f, \u043d\u043e\u0442\u044b \u0438 \u0442.\u043f.) \u043d\u0430 \u043b\u0435\u0442\u0443. \u0415\u0441\u043b\u0438 \u043a\u0440\u0430\u0442\u043a\u043e, \u0442\u0435\u043f\u0435\u0440\u044c \u043c\u043e\u0436\u043d\u043e \u0443\u0434\u0430\u043b\u044f\u0442\u044c, \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0442\u044c \u0438 \u043c\u0435\u043d\u044f\u0442\u044c \u0434\u0430\u043d\u043d\u044b\u0435 \u0431\u0435\u0437 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e\u0441\u0442\u0438 \u043f\u0435\u0440\u0435\u0441\u043e\u0437\u0434\u0430\u0432\u0430\u0442\u044c \u044d\u043a\u0437\u0435\u043c\u043f\u043b\u044f\u0440 \u043a\u043b\u0430\u0441\u0441\u0430 <a href=\"https:\/\/melanchall.github.io\/drywetmidi\/api\/Melanchall.DryWetMidi.Multimedia.Playback.html\" rel=\"noopener noreferrer nofollow\">Playback<\/a>. \u0423\u0447\u0438\u0442\u044b\u0432\u0430\u044f, \u0447\u0442\u043e \u043e\u0431\u044a\u0435\u043a\u0442\u044b \u0432\u043d\u0443\u0442\u0440\u0438 \u0434\u043e\u043b\u0436\u043d\u044b \u0438\u0434\u0442\u0438 \u0432 \u0445\u0440\u043e\u043d\u043e\u043b\u043e\u0433\u0438\u0447\u0435\u0441\u043a\u043e\u043c \u043f\u043e\u0440\u044f\u0434\u043a\u0435, \u043f\u0440\u0438\u0445\u043e\u0434\u0438\u043c \u043a \u043f\u043e\u043a\u0430\u0437\u0430\u043d\u043d\u043e\u0439 \u0432\u044b\u0448\u0435 \u0437\u0430\u0434\u0430\u0447\u0435.<\/p>\n<p>\u0411\u0435\u0441\u0446\u0435\u043d\u043d\u044b\u0439 \u043e\u043f\u044b\u0442 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0438\u0445 \u043f\u043e\u043a\u043e\u043b\u0435\u043d\u0438\u0439 \u043f\u043e\u0434\u0441\u043a\u0430\u0437\u044b\u0432\u0430\u0435\u0442 \u2014 \u043d\u0443\u0436\u043d\u043e \u0441\u0430\u043c\u043e\u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u0443\u044e\u0449\u0435\u0435\u0441\u044f \u0431\u0438\u043d\u0430\u0440\u043d\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e \u043f\u043e\u0438\u0441\u043a\u0430 (<a href=\"https:\/\/en.wikipedia.org\/wiki\/Self-balancing_binary_search_tree\" rel=\"noopener noreferrer nofollow\">self-balancing binary search tree<\/a>). \u0418\u043b\u0438 \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u0435, \u043a\u043e\u043c\u0443 \u043a\u0430\u043a \u0431\u043e\u043b\u044c\u0448\u0435 \u043d\u0440\u0430\u0432\u0438\u0442\u0441\u044f. \u0421\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u044f, \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044f \u0438 \u043f\u043e\u0438\u0441\u043a\u0430 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u0432 \u0442\u0430\u043a\u043e\u0439 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0435 <code>O(logN)<\/code>, \u043a\u0430\u043a \u0432 \u0441\u0440\u0435\u0434\u043d\u0435\u043c, \u0442\u0430\u043a \u0438 \u0432 \u0445\u0443\u0434\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u044f\u0445. \u0427\u0435\u0433\u043e \u043d\u0435 \u0441\u043a\u0430\u0436\u0435\u0448\u044c \u043f\u0440\u043e \u043e\u0431\u044b\u0447\u043d\u043e\u0435 BST (<a href=\"https:\/\/en.wikipedia.org\/wiki\/Binary_search_tree\" rel=\"noopener noreferrer nofollow\">binary search tree<\/a>), \u043f\u043e\u0441\u043b\u0435 \u0441\u0435\u0440\u0438\u0438 \u043c\u043e\u0434\u0438\u0444\u0438\u043a\u0430\u0446\u0438\u0439 \u0432 \u043a\u043e\u0442\u043e\u0440\u043e\u043c \u043b\u0435\u0433\u043a\u043e \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0442\u0430\u043a\u0443\u044e \u0433\u0438\u0440\u043b\u044f\u043d\u0434\u0443:<\/p>\n<figure class=\"full-width\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/ad2\/9d1\/d98\/ad29d1d9863fe29acbaefa64ce7a1efb.png\" width=\"780\" height=\"302\" sizes=\"auto, (max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/r\/w780\/getpro\/habr\/upload_files\/ad2\/9d1\/d98\/ad29d1d9863fe29acbaefa64ce7a1efb.png 780w,&#10;       https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/ad2\/9d1\/d98\/ad29d1d9863fe29acbaefa64ce7a1efb.png 781w\" loading=\"lazy\" decode=\"async\"\/><\/figure>\n<p>\u0421\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u0431\u0443\u0434\u0435\u0442, \u043e\u0447\u0435\u0432\u0438\u0434\u043d\u043e, \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0439 (\u0442.\u0435. <code>O(N)<\/code>). \u041f\u043e\u0434\u0434\u0435\u0440\u0436\u0430\u043d\u0438\u0435 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0439 \u0432\u044b\u0441\u043e\u0442\u044b \u0434\u0435\u0440\u0435\u0432\u0430 (\u0447\u0442\u043e \u0438 \u0434\u0430\u0451\u0442 \u0437\u0430\u0432\u0435\u0442\u043d\u044b\u0439 \u043b\u043e\u0433\u0430\u0440\u0438\u0444\u043c) \u2014 \u0437\u0430\u0434\u0430\u0447\u0430 \u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u043e\u0432\u043a\u0438, \u0441\u0443\u0442\u044c \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u0432 \u043f\u0435\u0440\u0435\u0443\u043f\u043e\u0440\u044f\u0434\u043e\u0447\u0438\u0432\u0430\u043d\u0438\u0438 \u0443\u0437\u043b\u043e\u0432 \u0431\u0435\u0437 \u043d\u0430\u0440\u0443\u0448\u0435\u043d\u0438\u044f \u0441\u0432\u043e\u0439\u0441\u0442\u0432 BST.<\/p>\n<p>\u0418 \u0442\u0430\u043a, \u0441\u043e \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u043e\u0439 \u0434\u0430\u043d\u043d\u044b\u0445 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u043b\u0438\u0441\u044c. \u041d\u043e \u0441\u0430\u043c\u043e\u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u0443\u044e\u0449\u0438\u0435\u0441\u044f \u0431\u0438\u043d\u0430\u0440\u043d\u044b\u0435 \u0434\u0435\u0440\u0435\u0432\u044c\u044f \u043f\u043e\u0438\u0441\u043a\u0430 \u0431\u044b\u0432\u0430\u044e\u0442 \u0440\u0430\u0437\u043d\u044b\u043c\u0438. \u041d\u0430\u0438\u0431\u043e\u043b\u0435\u0435 \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u044b <a href=\"https:\/\/en.wikipedia.org\/wiki\/AVL_tree\" rel=\"noopener noreferrer nofollow\">AVL-\u0434\u0435\u0440\u0435\u0432\u043e<\/a> \u0438 \u0433\u0432\u043e\u0437\u0434\u044c \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u044b \u2014 <a href=\"https:\/\/en.wikipedia.org\/wiki\/Red%E2%80%93black_tree\" rel=\"noopener noreferrer nofollow\">\u043a\u0440\u0430\u0441\u043d\u043e-\u0447\u0451\u0440\u043d\u043e\u0435<\/a> (red-black tree, RBT). \u041d\u0430 \u044d\u0442\u043e\u043c \u043c\u0435\u0441\u0442\u0435 \u044f \u0434\u043e\u043b\u0436\u0435\u043d \u0431\u044b\u043b \u0441\u043a\u0430\u0437\u0430\u0442\u044c \u043e \u043f\u0440\u043e\u0432\u0435\u0434\u0451\u043d\u043d\u043e\u043c \u0438\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u043d\u0438\u0438 \u043f\u043b\u044e\u0441\u043e\u0432 \u0438 \u043c\u0438\u043d\u0443\u0441\u043e\u0432 \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0438\u0437 \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u043e\u0432, \u043d\u043e \u0447\u0442\u043e-\u0442\u043e \u043f\u043e\u0448\u043b\u043e \u043d\u0435 \u0442\u0430\u043a. \u041f\u0440\u043e \u043a\u0440\u0430\u0441\u043d\u043e-\u0447\u0451\u0440\u043d\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e \u0438 \u0435\u0433\u043e \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u0430 \u044f \u0443\u0436\u0435 \u0437\u043d\u0430\u043b, \u0430 \u043f\u043e\u0442\u043e\u043c\u0443 \u0432\u044b\u0431\u043e\u0440 \u043f\u0430\u043b \u043d\u0430 \u043d\u0435\u0433\u043e. \u041f\u0440\u043e\u0444\u0435\u0441\u0441\u0438\u043e\u043d\u0430\u043b\u044c\u043d\u043e, \u043d\u0435 \u0442\u0430\u043a \u043b\u0438?<\/p>\n<p>\u041d\u043e \u043f\u0438\u0441\u0430\u0442\u044c \u0441\u0442\u0430\u0442\u044c\u0438 \u044d\u0442\u043e \u043d\u0435 \u0442\u043e\u043b\u044c\u043a\u043e \u0434\u0435\u043b\u0438\u0442\u044c\u0441\u044f \u0437\u043d\u0430\u043d\u0438\u044f\u043c\u0438. \u0412\u043e \u0432\u0440\u0435\u043c\u044f \u0440\u0430\u0431\u043e\u0442\u044b \u043d\u0430\u0434 \u0442\u0435\u043a\u0441\u0442\u043e\u043c \u0432\u043e\u0437\u043d\u0438\u043a\u0430\u0435\u0442 \u0436\u0435\u043b\u0430\u043d\u0438\u0435 \u0433\u043b\u0443\u0431\u0436\u0435 \u0440\u0430\u0437\u043e\u0431\u0440\u0430\u0442\u044c\u0441\u044f \u0432 \u0442\u0435\u043c\u0435. \u0411\u044b\u043b\u043e \u0431\u044b \u0441\u043e\u0432\u0441\u0435\u043c \u0433\u043b\u0443\u043f\u043e \u0434\u0430\u0436\u0435 \u0441\u0435\u0439\u0447\u0430\u0441 \u043d\u0435 \u0437\u0430\u0434\u0430\u0442\u044c\u0441\u044f \u0432\u043e\u043f\u0440\u043e\u0441\u043e\u043c, \u043a\u0430\u043a\u0430\u044f \u0436\u0435 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u0434\u0430\u043d\u043d\u044b\u0445 \u043b\u0443\u0447\u0448\u0435. \u041a\u0440\u0430\u0442\u043a\u0438\u0439 \u043f\u0435\u0440\u0435\u0441\u043a\u0430\u0437 \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u0445 \u043c\u0430\u0442\u0435\u0440\u0438\u0430\u043b\u043e\u0432 \u0442\u0430\u043a\u043e\u0432: \u0432 \u0446\u0435\u043b\u043e\u043c, \u043e\u043d\u0438 \u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u044b. \u0412 \u043a\u043e\u043d\u0446\u0435 \u043a\u043e\u043d\u0446\u043e\u0432, \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0443 \u043e\u0431\u043e\u0438\u0445 <code>O(logN)<\/code> \u0434\u043b\u044f \u0432\u0441\u0435\u0445 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439. \u041d\u044e\u0430\u043d\u0441\u044b, \u043a\u043e\u043d\u0435\u0447\u043d\u043e, \u043f\u0440\u0438\u0441\u0443\u0442\u0441\u0442\u0432\u0443\u044e\u0442:<\/p>\n<ul>\n<li>\n<p>AVL \u0447\u0443\u0442\u044c \u0431\u044b\u0441\u0442\u0440\u0435\u0435 \u043f\u0440\u0438 \u043f\u043e\u0438\u0441\u043a\u0435 \u0434\u0430\u043d\u043d\u044b\u0445 \u0432\u0432\u0438\u0434\u0443 <a href=\"https:\/\/en.wikipedia.org\/wiki\/AVL_tree#Comparison_to_other_structures\" rel=\"noopener noreferrer nofollow\">\u043c\u0435\u043d\u044c\u0448\u0435\u0439 \u0432\u044b\u0441\u043e\u0442\u044b<\/a> \u0434\u0435\u0440\u0435\u0432\u0430;<\/p>\n<\/li>\n<li>\n<p>RBT \u0432\u044b\u0438\u0433\u0440\u044b\u0432\u0430\u0435\u0442 \u0432 \u0441\u043a\u043e\u0440\u043e\u0441\u0442\u0438 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044f \u0438\u0437-\u0437\u0430 \u043c\u0435\u043d\u044c\u0448\u0435\u0433\u043e \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0430 \u0432\u0440\u0430\u0449\u0435\u043d\u0438\u0439 \u043f\u0440\u0438 \u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u043e\u0432\u043a\u0435 (AVL-\u0434\u0435\u0440\u0435\u0432\u0443 \u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f <code>O(logN)<\/code> \u0442\u0430\u043a\u043e\u0432\u044b\u0445 \u0432 \u0445\u0443\u0434\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u043f\u043e \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044e \u0441 <code>O(1)<\/code> \u0443 \u043a\u0440\u0430\u0441\u043d\u043e-\u0447\u0451\u0440\u043d\u043e\u0433\u043e).<\/p>\n<\/li>\n<\/ul>\n<p>\u041c\u043d\u0435 \u043f\u043e\u0432\u0435\u0437\u043b\u043e, \u043f\u043e\u0442\u043e\u043c\u0443 \u0447\u0442\u043e \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u0438\u0437\u043c\u0435\u043d\u0435\u043d\u0438\u044f \u0434\u0435\u0440\u0435\u0432\u0430 \u0432 \u043c\u043e\u0451\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u0432\u0430\u0436\u043d\u0435\u0435. \u041f\u043e\u0438\u0441\u043a \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u0442 \u043d\u0435\u0447\u0430\u0441\u0442\u043e: \u043f\u0440\u0438 <a href=\"https:\/\/melanchall.github.io\/drywetmidi\/api\/Melanchall.DryWetMidi.Multimedia.Playback.html#Melanchall_DryWetMidi_Multimedia_Playback_MoveToTime_Melanchall_DryWetMidi_Interaction_ITimeSpan_\" rel=\"noopener noreferrer nofollow\">\u043f\u0440\u044b\u0436\u043a\u0430\u0445<\/a> \u043f\u043e \u0442\u0430\u0439\u043c\u043b\u0430\u0439\u043d\u0443 \u0432\u043e\u0441\u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u043c\u044b\u0445 \u0434\u0430\u043d\u043d\u044b\u0445. \u0412 \u044d\u0442\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435, \u043a\u043e\u043d\u0435\u0447\u043d\u043e, \u043f\u043e\u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f \u043d\u0430\u0439\u0442\u0438 \u0441\u043e\u0431\u044b\u0442\u0438\u0435, \u0441 \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u0434\u043e\u043b\u0436\u043d\u043e \u043d\u0430\u0447\u0430\u0442\u044c\u0441\u044f \u043f\u0440\u043e\u0438\u0433\u0440\u044b\u0432\u0430\u043d\u0438\u0435 \u0432 \u043d\u043e\u0432\u043e\u0439 \u043f\u043e\u0437\u0438\u0446\u0438\u0438.<\/p>\n<p>\u0421\u0442\u0430\u0442\u044c\u044f \u043f\u0440\u0438\u0437\u0432\u0430\u043d\u0430 \u0434\u0430\u0442\u044c \u0438\u0441\u0447\u0435\u0440\u043f\u044b\u0432\u0430\u044e\u0449\u0438\u0435 \u043b\u0438\u0441\u0442\u0438\u043d\u0433\u0438 \u043a\u043e\u0434\u0430 \u0441 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0435\u0439 \u043a\u0440\u0430\u0441\u043d\u043e-\u0447\u0451\u0440\u043d\u043e\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430, \u043a\u0430\u043a \u043e\u0441\u043d\u043e\u0432\u043d\u044b\u0445 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439, \u0442\u0430\u043a \u0438 \u043f\u043e\u043b\u0435\u0437\u043d\u044b\u0445 \u0432\u0441\u043f\u043e\u043c\u043e\u0433\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0445. \u0418 \u0441\u043e\u0432\u0441\u0435\u043c \u0441\u043a\u043e\u0440\u043e \u0432\u044b \u0443\u0432\u0438\u0434\u0438\u0442\u0435 \u044d\u0442\u0438 \u043f\u043e\u043b\u044f \u043c\u043e\u043d\u043e\u0448\u0438\u0440\u0438\u043d\u043d\u043e\u0433\u043e \u0442\u0435\u043a\u0441\u0442\u0430.<\/p>\n<p><strong>\u201c\u0410 \u043f\u043e\u0447\u0435\u043c\u0443 \u0431\u044b \u043d\u0435 \u0432\u0437\u044f\u0442\u044c \u0443\u0436\u0435 \u0433\u043e\u0442\u043e\u0432\u044b\u0439 \u043a\u043e\u0434 \u0438\u0437 \u0418\u043d\u0442\u0435\u0440\u043d\u0435\u0442\u0430?\u201d<\/strong> \u2014 \u043c\u043e\u0436\u0435\u0442 \u0432\u043e\u0437\u043d\u0438\u043a\u043d\u0443\u0442\u044c \u0432\u043e\u043f\u0440\u043e\u0441. \u041f\u0440\u0438\u0437\u043d\u0430\u044e\u0441\u044c, \u0443 \u043c\u0435\u043d\u044f, \u043a\u0430\u043a \u0442\u0438\u043f\u0438\u0447\u043d\u043e\u0433\u043e \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u0442\u0435\u043b\u044f \u043f\u0440\u043e\u0444\u0435\u0441\u0441\u0438\u0438, \u044d\u0442\u043e \u0431\u044b\u043b\u043e \u043f\u0435\u0440\u0432\u044b\u043c \u0436\u0435\u043b\u0430\u043d\u0438\u0435\u043c. \u041d\u043e \u0441\u043a\u0430\u0437\u0430\u0442\u044c \u043b\u0435\u0433\u0447\u0435, \u0447\u0435\u043c \u0441\u0434\u0435\u043b\u0430\u0442\u044c. \u0420\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u044b \u043f\u043e\u0438\u0441\u043a\u0430 \u043f\u043e \u0444\u0440\u0430\u0437\u0435 <em>\u201cred black tree c#\u201d<\/em>:<\/p>\n<ul>\n<li>\n<p><a href=\"https:\/\/gist.github.com\/JamesRandall\/33b6102e20bdf3ba6a027e6481f92242\" rel=\"noopener noreferrer nofollow\">Red-Black Tree Implementation in C#<\/a>. \u041d\u0435\u0442 \u043c\u0435\u0442\u043e\u0434\u0430 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044f \u0434\u0430\u043d\u043d\u044b\u0445. \u041a\u0440\u043e\u043c\u0435 \u0442\u043e\u0433\u043e, \u0432 \u043a\u043e\u0434\u0435 \u043d\u0430\u0439\u0434\u0435\u043d \u0431\u0430\u0433 (\u0441\u043c. \u043a\u043e\u043c\u043c\u0435\u043d\u0442\u0430\u0440\u0438\u0438).<\/p>\n<\/li>\n<li>\n<p><a href=\"https:\/\/www.c-sharpcorner.com\/article\/working-with-red-black-trees-in-c-sharp\/\" rel=\"noopener noreferrer nofollow\">Working With Red-Black Trees In C#<\/a>. \u0418 \u0441\u043d\u043e\u0432\u0430 \u043d\u0435\u0442 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044f.<\/p>\n<\/li>\n<li>\n<p><a href=\"https:\/\/www.jot.fm\/issues\/issue_2005_03\/column6\/\" rel=\"noopener noreferrer nofollow\">Generic Red-Black Tree and its C# Implementation<\/a>. \u0418\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d \u043d\u043e\u0432\u0430\u0442\u043e\u0440\u0441\u043a\u0438\u0439 \u043c\u0435\u0442\u043e\u0434 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u043a\u043e\u0434\u0430: \u043a\u0430\u0440\u0442\u0438\u043d\u043a\u0430\u043c\u0438.<\/p>\n<\/li>\n<li>\n<p><a href=\"https:\/\/dzone.com\/articles\/red-black-trees-in-c-a-guide-to-efficient-self-bal\" rel=\"noopener noreferrer nofollow\">Red-Black Trees in C#<\/a>. \u041a\u043b\u044e\u0447 \u0438 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u043e\u0434\u0438\u043d \u0438 \u0442\u043e\u0442 \u0436\u0435 \u043e\u0431\u044a\u0435\u043a\u0442. \u042d\u0442\u043e \u043d\u0435\u0432\u0435\u0440\u043d\u043e, \u0440\u0430\u0437\u0443\u043c\u0435\u0435\u0442\u0441\u044f.<\/p>\n<\/li>\n<li>\n<p><a href=\"https:\/\/www.codeproject.com\/Articles\/8287\/Red-Black-Trees-in-C-\" rel=\"noopener noreferrer nofollow\">Red-Black Trees in C#<\/a> (\u0442\u043e \u0436\u0435 \u043d\u0430\u0437\u0432\u0430\u043d\u0438\u0435, \u043d\u043e \u0434\u0440\u0443\u0433\u0430\u044f \u0441\u0442\u0430\u0442\u044c\u044f). \u041a\u043b\u044e\u0447 \u043f\u0440\u043e\u0441\u0442\u043e <code>IComparable<\/code>, \u0430 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u2014 <code>object<\/code>. \u0422\u043e \u0435\u0441\u0442\u044c, \u043d\u0435 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044e\u0442\u0441\u044f \u0434\u0436\u0435\u043d\u0435\u0440\u0438\u043a\u0438.<\/p>\n<\/li>\n<\/ul>\n<p><strong>\u201c\u041d\u043e \u043d\u0430\u0432\u0435\u0440\u043d\u044f\u043a\u0430 \u0436\u0435 \u0435\u0441\u0442\u044c \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0438 \u0441 \u0433\u043e\u0442\u043e\u0432\u044b\u043c\u0438 \u043a\u043b\u0430\u0441\u0441\u0430\u043c\u0438?\u201d<\/strong> \u2014 \u0441\u043d\u043e\u0432\u0430 \u0441\u043f\u0440\u043e\u0441\u0438\u0442\u0435 \u0432\u044b. \u041e\u0442\u0432\u0435\u0447\u0430\u044e:<\/p>\n<ol>\n<li>\n<p>\u0412\u043e\u0437\u043c\u043e\u0436\u043d\u043e, \u043c\u043e\u0438 \u043d\u0430\u0432\u044b\u043a\u0438 \u043f\u043e\u0438\u0441\u043a\u0430 \u043f\u043b\u043e\u0445\u0438, \u043d\u043e \u044f \u043d\u0435 \u043e\u0431\u043d\u0430\u0440\u0443\u0436\u0438\u043b \u0437\u0430\u0441\u043b\u0443\u0436\u0438\u0432\u0430\u044e\u0449\u0443\u044e \u0434\u043e\u0432\u0435\u0440\u0438\u044f \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0443 \u0432 NuGet, \u0433\u0434\u0435 \u043a\u0440\u0430\u0441\u043d\u043e-\u0447\u0451\u0440\u043d\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e \u0443\u0434\u043e\u0432\u043b\u0435\u0442\u0432\u043e\u0440\u044f\u043b\u043e \u0431\u044b \u043c\u043e\u0438\u043c \u0442\u0440\u0435\u0431\u043e\u0432\u0430\u043d\u0438\u044f\u043c (\u0441\u043c. \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0439 \u0440\u0430\u0437\u0434\u0435\u043b).<\/p>\n<\/li>\n<li>\n<p>\u0412 \u0441\u0432\u043e\u0451\u043c \u043f\u0440\u043e\u0435\u043a\u0442\u0435 \u044f \u043d\u0430\u043c\u0435\u0440\u0435\u043d\u043d\u043e \u0438\u0437\u0431\u0435\u0433\u0430\u044e \u0441\u0442\u043e\u0440\u043e\u043d\u043d\u0438\u0445 \u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u0435\u0439. \u0422\u044f\u043d\u0443\u0442\u044c \u0446\u0435\u043b\u0443\u044e \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0443 \u0440\u0430\u0434\u0438 \u043e\u0434\u043d\u043e\u0433\u043e \u043a\u043b\u0430\u0441\u0441\u0430 \u0438\u043b\u0438 \u043c\u0435\u0442\u043e\u0434\u0430 \u043d\u0435 \u0432\u0441\u0435\u0433\u0434\u0430 \u0440\u0430\u0437\u0443\u043c\u043d\u043e.<\/p>\n<\/li>\n<li>\n<p>\u041c\u043d\u0435 \u0442\u0440\u0435\u0431\u043e\u0432\u0430\u043b\u043e\u0441\u044c \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u0442\u044c \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u0435 \u043c\u0435\u0442\u043e\u0434\u044b, \u0442\u0440\u0435\u0431\u0443\u044e\u0449\u0438\u0435 \u0434\u043e\u0441\u0442\u0443\u043f\u0430 \u043a\u043e \u0432\u043d\u0443\u0442\u0440\u0435\u043d\u043d\u043e\u0441\u0442\u044f\u043c \u0434\u0435\u0440\u0435\u0432\u0430.<\/p>\n<\/li>\n<\/ol>\n<p><a class=\"anchor\" name=\"construction\" id=\"construction\"><\/a><\/p>\n<h2>\u041f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u0435<\/h2>\n<p>\u041a\u0430\u043a \u0432 \u043c\u043e\u0451\u043c \u043f\u043e\u043d\u0438\u043c\u0430\u043d\u0438\u0438 \u0434\u043e\u043b\u0436\u0435\u043d \u0432\u044b\u0433\u043b\u044f\u0434\u0435\u0442\u044c \u043a\u043b\u0430\u0441\u0441, \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u044f\u044e\u0449\u0438\u0439 \u043a\u0440\u0430\u0441\u043d\u043e-\u0447\u0451\u0440\u043d\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e:<\/p>\n<ol>\n<li>\n<p><strong>\u041a\u043b\u044e\u0447 \u0438 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 <\/strong>\u2014<strong> \u0440\u0430\u0437\u043d\u044b\u0435 \u0441\u0443\u0449\u043d\u043e\u0441\u0442\u0438<\/strong>. \u0415\u0441\u043b\u0438 \u0432 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f \u0447\u0442\u043e-\u0442\u043e \u0441\u043b\u043e\u0436\u043d\u0435\u0435 <code>int<\/code>, \u0442\u043e \u043f\u043e\u0447\u0442\u0438 \u043d\u0430\u0432\u0435\u0440\u043d\u044f\u043a\u0430 \u0441\u0430\u043c\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u043d\u0435 \u0431\u0443\u0434\u0435\u0442 \u043a\u043b\u044e\u0447\u043e\u043c.<\/p>\n<\/li>\n<li>\n<p><strong>\u041a\u043b\u0430\u0441\u0441 \u0434\u043e\u043b\u0436\u0435\u043d \u0431\u044b\u0442\u044c \u043e\u0431\u043e\u0431\u0449\u0451\u043d\u043d\u044b\u043c<\/strong> (\u0434\u0436\u0435\u043d\u0435\u0440\u0438\u043a\u043e\u043c). \u041d\u0435 \u043d\u0443\u0436\u043d\u043e \u0441\u0442\u0440\u043e\u0438\u0442\u044c \u0434\u043e\u0433\u0430\u0434\u043e\u043a \u043f\u043e \u043f\u043e\u0432\u043e\u0434\u0443 \u043a\u043b\u044e\u0447\u0430 \u0438 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f, \u0438\u043b\u0438 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0432\u0441\u0435\u044f\u0434\u043d\u044b\u0439 <code>object<\/code> (\u0432\u0440\u044f\u0434 \u043b\u0438 \u0432\u0430\u043c \u043d\u0443\u0436\u0435\u043d \u0431\u043e\u043a\u0441\u0438\u043d\u0433).<\/p>\n<\/li>\n<li>\n<p><strong>\u041a\u043b\u044e\u0447\u0438 \u043c\u043e\u0433\u0443\u0442 \u043f\u043e\u0432\u0442\u043e\u0440\u044f\u0442\u044c\u0441\u044f<\/strong>. \u041f\u0440\u0438\u043c\u0435\u0440: \u0433\u0440\u0443\u043f\u043f\u0430 \u043d\u043e\u0442 \u0432 MIDI-\u0444\u0430\u0439\u043b\u0435, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0441\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u044e\u0442 \u0430\u043a\u043a\u043e\u0440\u0434. \u0412\u044b\u0445\u043e\u0434\u0438\u0442, \u0447\u0442\u043e \u0441\u043e\u0431\u044b\u0442\u0438\u044f \u0441\u0442\u0430\u0440\u0442\u0430 \u0442\u0430\u043a\u0438\u0445 \u043d\u043e\u0442 (= \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f) \u0438\u043c\u0435\u044e\u0442 \u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u043e\u0435 \u0432\u0440\u0435\u043c\u044f (= \u043a\u043b\u044e\u0447).<\/p>\n<\/li>\n<\/ol>\n<p>\u041f\u043e\u0441\u043b\u0435\u0434\u043d\u0438\u0439 \u043f\u0443\u043d\u043a\u0442 \u043d\u0430\u0438\u0431\u043e\u043b\u0435\u0435 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u0435\u043d, \u0438\u0431\u043e \u0432\u043b\u0438\u044f\u0435\u0442 \u043d\u0430 \u0444\u0438\u043d\u0430\u043b\u044c\u043d\u0443\u044e \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0443 \u0434\u0435\u0440\u0435\u0432\u0430. \u0418\u0437\u043d\u0430\u0447\u0430\u043b\u044c\u043d\u043e \u044f \u0440\u0435\u0448\u0438\u043b \u043d\u0435 \u043c\u0443\u0434\u0440\u0438\u0442\u044c: \u043f\u0443\u0441\u0442\u044c \u0443\u0437\u043b\u044b \u0441 \u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u044b\u043c\u0438 \u043a\u043b\u044e\u0447\u0430\u043c\u0438 \u0432\u0441\u0435\u0433\u0434\u0430 \u0438\u0434\u0443\u0442 \u0432\u043f\u0440\u0430\u0432\u043e. \u041f\u0440\u043e\u0442\u0438\u0432\u043e\u0440\u0435\u0447\u0438\u0435 \u2014 \u0441\u043b\u043e\u0432\u043e, \u043f\u0440\u0438\u0445\u043e\u0434\u044f\u0449\u0435\u0435 \u043c\u043d\u0435 \u043d\u0430 \u0443\u043c \u0441\u0435\u0439\u0447\u0430\u0441. \u0412\u0435\u0434\u044c \u043f\u043e \u0442\u0430\u043a\u043e\u0439 \u043b\u043e\u0433\u0438\u043a\u0435 \u0434\u0435\u0440\u0435\u0432\u043e \u0438\u0437 \u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u044b\u0445 \u043e\u0431\u044a\u0435\u043a\u0442\u043e\u0432 \u0431\u0443\u0434\u0435\u0442 \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0442\u044c \u0442\u043e\u043b\u044c\u043a\u043e \u043f\u0440\u0430\u0432\u044b\u0435 \u0443\u0437\u043b\u044b, \u0447\u0442\u043e \u043c\u0435\u043d\u044f\u0435\u0442 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u0432 \u0441\u0442\u043e\u0440\u043e\u043d\u0443 \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0439. \u0415\u0441\u043b\u0438 \u0436\u0435 \u043f\u0440\u043e\u0432\u0435\u0441\u0442\u0438 \u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u043e\u0432\u043a\u0443, \u0442\u043e \u043d\u0430\u0440\u0443\u0448\u0438\u0442\u0441\u044f \u043f\u0440\u0438\u043d\u0446\u0438\u043f \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u044f.<\/p>\n<p>\u0421\u043f\u0440\u0430\u0432\u0435\u0434\u043b\u0438\u0432\u043e\u0441\u0442\u0438 \u0440\u0430\u0434\u0438, \u044d\u0442\u043e\u0442 \u043f\u043e\u0434\u0445\u043e\u0434 \u0436\u0438\u0437\u043d\u0435\u0441\u043f\u043e\u0441\u043e\u0431\u0435\u043d (\u044f \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u043b). \u041d\u043e \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043e\u043f\u0438\u0441\u044b\u0432\u0430\u0435\u043c\u044b\u0435 \u0434\u0430\u043b\u0435\u0435 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u0441\u0442\u0430\u043d\u043e\u0432\u044f\u0442\u0441\u044f \u0447\u0443\u0442\u044c \u0441\u043b\u043e\u0436\u043d\u0435\u0435. \u042f \u043e\u0441\u0442\u0430\u043d\u043e\u0432\u0438\u043b\u0441\u044f \u043d\u0430 \u0442\u043e\u043c, \u0447\u0442\u043e \u043a\u043b\u044e\u0447\u0438 \u0432 \u0443\u0437\u043b\u0430\u0445 \u0434\u0435\u0440\u0435\u0432\u0430 \u0432\u0441\u0451-\u0442\u0430\u043a\u0438 \u0434\u043e\u043b\u0436\u043d\u044b \u0431\u044b\u0442\u044c \u0443\u043d\u0438\u043a\u0430\u043b\u044c\u043d\u044b\u043c\u0438. \u041f\u0440\u0438 \u044d\u0442\u043e\u043c \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u0434\u0430\u043d\u043d\u044b\u0435 \u0441 \u043f\u043e\u0432\u0442\u043e\u0440\u044f\u044e\u0449\u0438\u043c\u0438\u0441\u044f \u0438\u0434\u0435\u043d\u0442\u0438\u0444\u0438\u043a\u0430\u0442\u043e\u0440\u0430\u043c\u0438 \u043d\u0443\u0436\u043d\u043e \u0443\u043c\u0435\u0442\u044c. \u0420\u0435\u0448\u0435\u043d\u0438\u0435: \u0432\u043d\u0443\u0442\u0440\u0438 \u0443\u0437\u043b\u0430 \u0440\u0430\u0437\u043c\u0435\u0449\u0430\u0442\u044c \u043d\u0435 \u043e\u0434\u043d\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435, \u0430 \u043a\u043e\u043b\u043b\u0435\u043a\u0446\u0438\u044e \u043e\u043d\u044b\u0445. \u041a\u0430\u043a \u0438\u043c\u0435\u043d\u043d\u043e \u044d\u0442\u043e \u0431\u0443\u0434\u0435\u0442 \u0443\u0441\u0442\u0440\u043e\u0435\u043d\u043e \u2014 \u0440\u0435\u0448\u0430\u0442\u044c \u0432\u0430\u043c. \u042f \u0432\u044b\u0431\u0440\u0430\u043b <code>LinkedList&lt;&gt;<\/code>.<\/p>\n<p>\u0427\u0442\u043e\u0431\u044b \u043d\u0435 \u0437\u0430\u043f\u0443\u0442\u0430\u0442\u044c\u0441\u044f \u0432 \u0434\u0430\u043b\u044c\u043d\u0435\u0439\u0448\u0435\u043c \u043f\u043e\u0432\u0435\u0441\u0442\u0432\u043e\u0432\u0430\u043d\u0438\u0438 \u0438 \u0438\u0437\u0431\u0435\u0436\u0430\u0442\u044c \u043c\u043d\u043e\u0433\u043e\u0441\u043b\u043e\u0432\u043d\u043e\u0441\u0442\u0438, \u043f\u0440\u0438\u043c\u0435\u043c \u0442\u0430\u043a\u0443\u044e \u0442\u0435\u0440\u043c\u0438\u043d\u043e\u043b\u043e\u0433\u0438\u044e:<\/p>\n<ul>\n<li>\n<p>\u0434\u0435\u0440\u0435\u0432\u043e \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0438\u0437 <strong>\u0443\u0437\u043b\u043e\u0432<\/strong> (tree node), \u0438\u043c\u0435\u044e\u0449\u0438\u0445 \u043a\u043b\u044e\u0447;<\/p>\n<\/li>\n<li>\n<p>\u0443\u0437\u0435\u043b \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u0441\u043f\u0438\u0441\u043e\u043a <strong>\u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432<\/strong> (node element), \u0432 \u043d\u0430\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u043a\u0430\u0436\u0434\u044b\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u044d\u0442\u043e <code>LinkedListNode&lt;&gt;<\/code>;<\/p>\n<\/li>\n<li>\n<p>\u0432 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0435 \u0445\u0440\u0430\u043d\u0438\u0442\u0441\u044f <strong>\u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435<\/strong> (value), \u0442.\u0435. \u043e\u0431\u044a\u0435\u043a\u0442 \u0434\u0430\u043d\u043d\u044b\u0445, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043c\u044b \u043f\u043e\u043c\u0435\u0449\u0430\u0435\u043c \u0432 \u0434\u0435\u0440\u0435\u0432\u043e.<\/p>\n<\/li>\n<\/ul>\n<figure class=\"full-width\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/6c9\/d7b\/086\/6c9d7b086b68f7b133edae54688a1fac.png\" width=\"780\" height=\"343\" sizes=\"auto, (max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/r\/w780\/getpro\/habr\/upload_files\/6c9\/d7b\/086\/6c9d7b086b68f7b133edae54688a1fac.png 780w,&#10;       https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/6c9\/d7b\/086\/6c9d7b086b68f7b133edae54688a1fac.png 781w\" loading=\"lazy\" decode=\"async\"\/><\/figure>\n<p>\u041f\u0435\u0440\u0435\u0434 \u0442\u0435\u043c, \u043a\u0430\u043a \u043d\u0430\u0447\u0430\u0442\u044c \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u0442\u044c, \u0434\u0438\u0441\u043a\u043b\u0435\u0439\u043c\u0435\u0440: \u043a\u043e\u0434 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c (\u0438 \u0431\u0443\u0434\u0435\u0442) \u0433\u0434\u0435-\u0442\u043e \u043d\u0435\u0438\u0434\u0435\u0430\u043b\u044c\u043d\u044b\u043c, \u0433\u0434\u0435-\u0442\u043e \u043d\u0435 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044e\u0449\u0438\u043c \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e\u0441\u0442\u0438 \u043d\u043e\u0432\u044b\u0445 \u0432\u0435\u0440\u0441\u0438\u0439 C#, \u0433\u0434\u0435-\u0442\u043e \u043d\u0435 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u0439 \u0432\u0430\u0448\u0438\u043c \u043f\u0440\u043e\u0444\u0435\u0441\u0441\u0438\u043e\u043d\u0430\u043b\u044c\u043d\u044b\u043c \u0432\u043a\u0443\u0441\u0430\u043c. \u041f\u0440\u0438\u043c\u0435\u0440 \u043d\u0435\u043e\u0434\u043d\u043e\u0437\u043d\u0430\u0447\u043d\u043e\u0433\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u2014 \u0441\u043f\u043e\u0441\u043e\u0431 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u0446\u0432\u0435\u0442\u0430 \u0443\u0437\u043b\u0430. \u041f\u0440\u0430\u0432\u0438\u043b\u0430 \u0445\u043e\u0440\u043e\u0448\u0435\u0433\u043e \u0442\u043e\u043d\u0430 \u043f\u043e\u0434\u0441\u043a\u0430\u0437\u044b\u0432\u0430\u044e\u0442, \u0447\u0442\u043e \u043d\u0443\u0436\u043d\u043e \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u044c <code>enum<\/code> \u0441 \u0434\u0432\u0443\u043c\u044f \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f\u043c\u0438 (<code>Red<\/code> \u0438 <code>Black<\/code>) \u0438 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0435\u0433\u043e \u0434\u043b\u044f \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u0430 <code>Color<\/code> \u0432 \u0443\u0437\u043b\u0435. \u0412 \u043f\u0435\u0440\u0432\u043e\u0439 \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u0438 \u044f \u0442\u0430\u043a \u0438 \u0441\u0434\u0435\u043b\u0430\u043b. \u041d\u043e \u043f\u043e\u0442\u043e\u043c \u043f\u043e\u0434\u0443\u043c\u0430\u043b \u2014 \u0446\u0432\u0435\u0442 \u0432\u0435\u0434\u044c \u043d\u0435 \u0431\u043e\u043b\u0435\u0435 \u0447\u0435\u043c \u043c\u0435\u0442\u0430\u0444\u043e\u0440\u0430 \u0434\u043b\u044f \u0430\u0442\u0440\u0438\u0431\u0443\u0442\u0430, \u043d\u0443\u0436\u043d\u043e\u0433\u043e \u043f\u0440\u043e\u0446\u0435\u0434\u0443\u0440\u0435 \u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u043e\u0432\u043a\u0438 \u0434\u0435\u0440\u0435\u0432\u0430. \u0418 \u0443\u0431\u0440\u0430\u043b <code>enum<\/code>, \u0430 \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u043e <code>Color<\/code> \u0437\u0430\u043c\u0435\u043d\u0438\u043b \u043d\u0430 \u0431\u0443\u043b\u0435\u0432\u043e <code>IsRed<\/code>. \u0411\u0440\u0438\u0442\u0432\u0430 \u041e\u043a\u043a\u0430\u043c\u0430 \u0432 \u0434\u0435\u0439\u0441\u0442\u0432\u0438\u0438.<\/p>\n<p>\u0427\u0442\u043e \u0436, \u0432\u043f\u0435\u0440\u0451\u0434! \u041f\u0435\u0440\u0432\u044b\u043c \u0434\u0435\u043b\u043e\u043c \u043e\u043f\u0438\u0448\u0435\u043c \u0443\u0437\u0435\u043b:<\/p>\n<pre><code class=\"cs\">public sealed class RedBlackTreeNode&lt;TKey, TValue&gt;     where TKey : IComparable&lt;TKey&gt; {     public static readonly RedBlackTreeNode&lt;TKey, TValue&gt; Void =         new RedBlackTreeNode&lt;TKey, TValue&gt;(default(TKey), null);      public RedBlackTreeNode(         TKey key,         RedBlackTreeNode&lt;TKey, TValue&gt; parent)     {         Key = key;         Parent = parent;     }      public TKey Key { get; set; }      public LinkedList&lt;TValue&gt; Values { get; } = new LinkedList&lt;TValue&gt;();      public RedBlackTreeNode&lt;TKey, TValue&gt; Left { get; set; }      public RedBlackTreeNode&lt;TKey, TValue&gt; Right { get; set; }      public RedBlackTreeNode&lt;TKey, TValue&gt; Parent { get; set; }      public bool IsRed { get; set; } }<\/code><\/pre>\n<p>\u041c\u043e\u0436\u043d\u043e \u0437\u0430\u043c\u0435\u0442\u0438\u0442\u044c \u0441\u0442\u0440\u0430\u043d\u043d\u0443\u044e \u043a\u043e\u043d\u0441\u0442\u0430\u043d\u0442\u0443 (\u0435\u0441\u043b\u0438 \u0432\u044b \u043f\u043e\u0437\u0432\u043e\u043b\u0438\u0442\u0435 \u043d\u0430\u0437\u0432\u0430\u0442\u044c \u0442\u0430\u043a <code>static readonly<\/code> \u043f\u043e\u043b\u0435) \u2014 <code>Void<\/code>. \u0427\u0442\u043e \u044d\u0442\u043e? \u0412 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u043f\u043e\u0441\u043e\u0431\u0438\u044f \u043f\u043e \u043a\u0440\u0430\u0441\u043d\u043e-\u0447\u0451\u0440\u043d\u043e\u043c\u0443 \u0434\u0435\u0440\u0435\u0432\u0443 \u044f \u0432\u044b\u0431\u0440\u0430\u043b \u043a\u043d\u0438\u0433\u0443 <a href=\"https:\/\/www.amazon.com\/dp\/0262033844\" rel=\"noopener noreferrer nofollow\">\u201cIntroduction to Algorithms\u201d<\/a> (\u0434\u043b\u044f \u0440\u0443\u0441\u0441\u043a\u043e\u044f\u0437\u044b\u0447\u043d\u043e\u0433\u043e \u0447\u0438\u0442\u0430\u0442\u0435\u043b\u044f \u0441\u0435\u0439 \u043a\u0438\u0440\u043f\u0438\u0447 \u043d\u0430 1000+ \u0441\u0442\u0440\u0430\u043d\u0438\u0446 \u0437\u043d\u0430\u043a\u043e\u043c \u043f\u043e\u0434 \u043d\u0430\u0437\u0432\u0430\u043d\u0438\u0435\u043c <em>\u201c\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b. \u041f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u0435 \u0438 \u0430\u043d\u0430\u043b\u0438\u0437\u201d<\/em>). \u0414\u043b\u044f \u0443\u0434\u043e\u0431\u0441\u0442\u0432\u0430 \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u043a\u0438 \u0433\u0440\u0430\u043d\u0438\u0447\u043d\u044b\u0445 \u0441\u043b\u0443\u0447\u0430\u0435\u0432 \u043b\u0438\u0441\u0442\u044c\u044f\u043c\u0438 \u0442\u0430\u043c \u0432\u0441\u0435\u0433\u0434\u0430 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043e\u0431\u044a\u0435\u043a\u0442 <code>nil<\/code>. \u042f \u0436\u0435 \u043f\u0440\u043e\u0441\u0442\u043e \u043d\u0430\u0437\u0432\u0430\u043b \u0435\u0433\u043e <code>Void<\/code>. \u0412 \u043c\u043e\u0451\u043c \u043a\u043e\u0434\u0435 \u0431\u0443\u0434\u0443\u0442 \u0438 \u0434\u0440\u0443\u0433\u0438\u0435 \u0440\u0430\u0441\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u044f \u0441 \u043a\u043d\u0438\u0433\u043e\u0439. \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0442\u0430\u043a\u0438\u0435 \u0432\u044b\u0440\u0430\u0437\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u0435 \u0438\u043c\u0435\u043d\u0430 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445, \u043a\u0430\u043a <code>w<\/code>, <code>x<\/code> \u0438 <code>y<\/code>, \u044f \u0440\u0435\u0448\u0438\u043b \u043d\u0435 \u0441\u043e\u0445\u0440\u0430\u043d\u044f\u0442\u044c.<\/p>\n<p>\u041a\u0430\u0441\u0430\u0442\u0435\u043b\u044c\u043d\u043e <code>IComparable&lt;TKey&gt;<\/code>: \u043a\u043b\u044e\u0447\u0438 \u043d\u0435 \u043c\u043e\u0433\u0443\u0442 \u0431\u044b\u0442\u044c \u0441\u043e\u0432\u0441\u0435\u043c \u0443\u0436 \u043b\u044e\u0431\u044b\u043c\u0438. \u041c\u044b, \u043e\u0447\u0435\u0432\u0438\u0434\u043d\u043e, \u0434\u043e\u043b\u0436\u043d\u044b \u0443\u043c\u0435\u0442\u044c \u0438\u0445 \u0441\u0440\u0430\u0432\u043d\u0438\u0432\u0430\u0442\u044c \u0434\u043b\u044f \u043d\u0430\u0432\u0438\u0433\u0430\u0446\u0438\u0438 \u043f\u043e \u0434\u0435\u0440\u0435\u0432\u0443. \u041d\u043e \u043d\u0430 \u044d\u0442\u043e\u043c \u0432\u0441\u0451, \u0431\u043e\u043b\u044c\u0448\u0435 \u043d\u0438\u043a\u0430\u043a\u0438\u0445 \u0442\u0440\u0435\u0431\u043e\u0432\u0430\u043d\u0438\u0439 \u043d\u0438 \u043a \u043a\u043b\u044e\u0447\u0443, \u043d\u0438 \u043a \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044e \u043d\u0435 \u0431\u0443\u0434\u0435\u0442 \u0438 \u043d\u0435 \u0434\u043e\u043b\u0436\u043d\u043e \u0431\u044b\u0442\u044c.<\/p>\n<p>\u0418 \u0442\u0430\u043a, \u0434\u0435\u0440\u0435\u0432\u043e \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0438\u0437 \u0443\u0437\u043b\u043e\u0432, \u0443\u0437\u043b\u044b \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0442 \u0441\u043f\u0438\u0441\u043a\u0438 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432, \u0430 \u043a\u0430\u0436\u0434\u044b\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0445\u0440\u0430\u043d\u0438\u0442 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435. \u041d\u043e \u0442\u043e\u0433\u0434\u0430 \u0432\u044b\u0445\u043e\u0434\u0438\u0442, \u0447\u0442\u043e \u0443\u0437\u043b\u043e\u043c \u043c\u044b \u043d\u0435 \u043c\u043e\u0436\u0435\u043c \u0443\u043a\u0430\u0437\u0430\u0442\u044c \u043d\u0430 \u043a\u043e\u043d\u043a\u0440\u0435\u0442\u043d\u043e\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435. \u0414\u043b\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0434\u0430\u043d\u043d\u043e\u0439 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u044b \u044f \u0432\u0432\u0451\u043b \u043f\u043e\u043d\u044f\u0442\u0438\u0435 <strong>\u043a\u043e\u043e\u0440\u0434\u0438\u043d\u0430\u0442\u044b<\/strong>:<\/p>\n<pre><code class=\"cs\">public sealed class RedBlackTreeCoordinate&lt;TKey, TValue&gt;     where TKey : IComparable&lt;TKey&gt; {     public RedBlackTreeCoordinate(         RedBlackTreeNode&lt;TKey, TValue&gt; treeNode,         LinkedListNode&lt;TValue&gt; nodeElement)     {         TreeNode = treeNode;         NodeElement = nodeElement;     }      public RedBlackTreeNode&lt;TKey, TValue&gt; TreeNode { get; }      public LinkedListNode&lt;TValue&gt; NodeElement { get; }      public TKey Key =&gt; TreeNode.Key;      public TValue Value =&gt; NodeElement.Value; }<\/code><\/pre>\n<p>\u041f\u043e\u0440\u0430 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u044c \u0441\u0430\u043c\u043e \u0434\u0435\u0440\u0435\u0432\u043e. \u0418\u0437 \u0432\u043d\u0443\u0442\u0440\u0435\u043d\u043d\u043e\u0441\u0442\u0435\u0439 \u043f\u043e\u043a\u0430 \u043e\u0431\u044a\u044f\u0432\u0438\u043c \u043a\u043e\u0440\u043d\u0435\u0432\u043e\u0439 \u0443\u0437\u0435\u043b, \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u043e, \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u044e\u0449\u0435\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439, \u0438 \u043f\u0430\u0440\u0443 \u0432\u0441\u043f\u043e\u043c\u043e\u0433\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0445 \u043c\u0435\u0442\u043e\u0434\u043e\u0432:<\/p>\n<pre><code class=\"cs\">public class RedBlackTree&lt;TKey, TValue&gt;     where TKey : IComparable&lt;TKey&gt; {     protected RedBlackTreeNode&lt;TKey, TValue&gt; _root =         RedBlackTreeNode&lt;TKey, TValue&gt;.Void;      public int Count { get; private set; }      protected bool IsVoid(         RedBlackTreeNode&lt;TKey, TValue&gt; node)     {         return node == null || node == RedBlackTreeNode&lt;TKey, TValue&gt;.Void;     }      private RedBlackTreeNode&lt;TKey, TValue&gt; NodeOrNull(         RedBlackTreeNode&lt;TKey, TValue&gt; node)     {         return IsVoid(node) ? null : node;     } }<\/code><\/pre>\n<p>\u0422\u0435\u043f\u0435\u0440\u044c \u043c\u043e\u0436\u043d\u043e \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u0442\u044c \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u0435 \u0434\u0430\u043d\u043d\u044b\u0445:<\/p>\n<pre><code class=\"cs\">public RedBlackTreeCoordinate&lt;TKey, TValue&gt; Add(TKey key, TValue value) {     var currentNode = _root;     var lastNode = RedBlackTreeNode&lt;TKey, TValue&gt;.Void;      while (!IsVoid(currentNode))     {         lastNode = currentNode;          var compareResult = key.CompareTo(currentNode.Key);         if (compareResult &lt; 0)             currentNode = currentNode.Left;         else if (compareResult &gt; 0)             currentNode = currentNode.Right;         else         {             Count++;             var coordinateOnExistingNode = new RedBlackTreeCoordinate&lt;TKey, TValue&gt;(                 currentNode, currentNode.Values.AddLast(value));             return coordinateOnExistingNode;         }     }      var newNode = new RedBlackTreeNode&lt;TKey, TValue&gt;(key, lastNode);     var result = new RedBlackTreeCoordinate&lt;TKey, TValue&gt;(         newNode,         newNode.Values.AddLast(value));      if (IsVoid(lastNode))         _root = newNode;     else if (key.CompareTo(lastNode.Key) &lt; 0)         lastNode.Left = newNode;     else         lastNode.Right = newNode;      newNode.Left = RedBlackTreeNode&lt;TKey, TValue&gt;.Void;     newNode.Right = RedBlackTreeNode&lt;TKey, TValue&gt;.Void;     newNode.IsRed = true;      InsertFixup(newNode);      Count++;     return result; }<\/code><\/pre>\n<p>\u041c\u0435\u0442\u043e\u0434 <code>Add<\/code> \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442 \u043a\u043e\u043e\u0440\u0434\u0438\u043d\u0430\u0442\u0443, \u0443\u043a\u0430\u0437\u044b\u0432\u0430\u044e\u0449\u0443\u044e \u043d\u0430 \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u043d\u043e\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435. \u041f\u0440\u0438 \u043d\u0430\u043b\u0438\u0447\u0438\u0438 \u0432 \u0434\u0435\u0440\u0435\u0432\u0435 \u0443\u0437\u043b\u0430 \u0441 \u043a\u043b\u044e\u0447\u043e\u043c <code>key<\/code> \u043f\u0440\u043e\u0441\u0442\u043e \u0432\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u043c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0432 \u0435\u0433\u043e \u0441\u043f\u0438\u0441\u043e\u043a \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432. \u0415\u0441\u043b\u0438 \u0436\u0435 \u043a\u043b\u044e\u0447 \u0432 \u0434\u0435\u0440\u0435\u0432\u0435 \u043f\u043e\u043a\u0430 \u043e\u0442\u0441\u0443\u0442\u0441\u0442\u0432\u0443\u0435\u0442, \u0441\u043e\u0437\u0434\u0430\u0451\u043c \u043d\u043e\u0432\u044b\u0439 \u0443\u0437\u0435\u043b \u0441 \u043f\u0435\u0440\u0435\u0434\u0430\u043d\u043d\u044b\u043c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435\u043c, \u0438 \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c \u0435\u0433\u043e \u0432 \u0434\u0435\u0440\u0435\u0432\u043e.<\/p>\n<p>\u041d\u043e \u043f\u0440\u044f\u043c\u043e \u0441\u0435\u0439\u0447\u0430\u0441 \u043a\u043e\u0434 \u0432\u044b\u0448\u0435 \u043f\u043e \u0441\u0443\u0442\u0438 \u043d\u0438\u0447\u0435\u043c \u043d\u0435 \u043e\u0442\u043b\u0438\u0447\u0430\u0435\u0442\u0441\u044f \u043e\u0442 \u0442\u0430\u043a\u043e\u0432\u043e\u0433\u043e \u0434\u043b\u044f \u043e\u0431\u044b\u043a\u043d\u043e\u0432\u0435\u043d\u043d\u043e\u0433\u043e BST. \u0414\u0430 \u0438 \u043a\u043e\u043c\u043f\u0438\u043b\u044f\u0442\u043e\u0440 \u043d\u0435 \u043e\u0431\u0440\u0430\u0434\u0443\u0435\u0442\u0441\u044f, \u0432\u0435\u0434\u044c <code>InsertFixup<\/code> \u043d\u0435 \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u043d. \u042d\u0442\u043e \u0438 \u0435\u0441\u0442\u044c \u0442\u0430 \u0441\u0430\u043c\u0430\u044f \u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u043e\u0432\u043a\u0430:<\/p>\n<pre><code class=\"cs\">private void InsertFixup(RedBlackTreeNode&lt;TKey, TValue&gt; node) {     RedBlackTreeNode&lt;TKey, TValue&gt; parent;      while ((parent = node.Parent).IsRed)     {         var grandParent = parent.Parent;          if (parent == grandParent.Left)         {             var uncle = grandParent.Right;             if (uncle.IsRed)             {                 parent.IsRed = false;                 uncle.IsRed = false;                 grandParent.IsRed = true;                 node = grandParent;             }             else             {                 if (node == parent.Right)                 {                     node = parent;                     LeftRotate(node);                     parent = node.Parent;                     grandParent = parent.Parent;                 }                  parent.IsRed = false;                 grandParent.IsRed = true;                 RightRotate(grandParent);             }         }         else         {             var uncle = grandParent.Left;             if (uncle.IsRed)             {                 parent.IsRed = false;                 uncle.IsRed = false;                 grandParent.IsRed = true;                 node = grandParent;             }             else             {                 if (node == parent.Left)                 {                     node = parent;                     RightRotate(node);                     parent = node.Parent;                     grandParent = parent.Parent;                 }                  parent.IsRed = false;                 grandParent.IsRed = true;                 LeftRotate(grandParent);             }         }     }      _root.IsRed = false; }<\/code><\/pre>\n<p>\u0417\u0434\u0435\u0441\u044c \u0432\u043e\u0437\u043d\u0438\u043a\u0430\u044e\u0442 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u0432\u0440\u0430\u0449\u0435\u043d\u0438\u044f \u2014 \u0441\u0435\u0440\u0434\u0446\u0435 \u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u043e\u0432\u043a\u0438, \u043a\u0430\u043a \u043f\u043e\u0441\u043b\u0435 \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u044f, \u0442\u0430\u043a \u0438 \u043f\u043e\u0441\u043b\u0435 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044f \u0434\u0430\u043d\u043d\u044b\u0445. \u0412\u0440\u0430\u0449\u0435\u043d\u0438\u0435 \u0432\u043b\u0435\u0432\u043e:<\/p>\n<pre><code class=\"cs\">private void LeftRotate(RedBlackTreeNode&lt;TKey, TValue&gt; node) {     var rightChild = node.Right;     var leftGrandchild = rightChild.Left;      node.Right = leftGrandchild;     if (!IsVoid(leftGrandchild))         leftGrandchild.Parent = node;                  var parent = node.Parent;     rightChild.Parent = parent;      if (IsVoid(parent))         _root = rightChild;     else if (node == parent.Left)         parent.Left = rightChild;     else         parent.Right = rightChild;      rightChild.Left = node;     node.Parent = rightChild; }<\/code><\/pre>\n<p>\u0418 \u0432\u0440\u0430\u0449\u0435\u043d\u0438\u0435 \u0432\u043f\u0440\u0430\u0432\u043e (\u043a\u043e\u0434 \u043e\u0442\u043b\u0438\u0447\u0430\u0435\u0442\u0441\u044f \u043e\u0442 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0435\u0433\u043e \u0437\u0430\u043c\u0435\u043d\u043e\u0439 <code>Left<\/code> \u043d\u0430 <code>Right<\/code> \u0438 \u043d\u0430\u043e\u0431\u043e\u0440\u043e\u0442):<\/p>\n<pre><code class=\"cs\">private void RightRotate(RedBlackTreeNode&lt;TKey, TValue&gt; node) {     var leftChild = node.Left;     var rightGrandChild = leftChild.Right;      node.Left = rightGrandChild;     if (!IsVoid(rightGrandChild))         rightGrandChild.Parent = node;      var parent = node.Parent;     leftChild.Parent = parent;      if (IsVoid(parent))         _root = leftChild;     else if (node == parent.Right)         parent.Right = leftChild;     else         parent.Left = leftChild;      leftChild.Right = node;     node.Parent = leftChild; }<\/code><\/pre>\n<p>\u0414\u0430\u043d\u043d\u044b\u0435 \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u044b, \u043f\u043e\u0440\u0430 \u043d\u0430\u0443\u0447\u0438\u0442\u044c\u0441\u044f \u0438\u0445 \u0443\u0434\u0430\u043b\u044f\u0442\u044c. \u041a\u0441\u0442\u0430\u0442\u0438, \u0432\u044b \u0437\u0430\u043c\u0435\u0447\u0430\u043b\u0438 \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u043e <a href=\"https:\/\/learn.microsoft.com\/en-us\/dotnet\/api\/system.collections.generic.linkedlistnode-1.list#system-collections-generic-linkedlistnode-1-list\" rel=\"noopener noreferrer nofollow\">List<\/a> \u0443 <code>LinkedListNode&lt;&gt;<\/code>? \u041a\u0430\u0436\u0434\u044b\u0439 \u0443\u0437\u0435\u043b \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u0441\u0441\u044b\u043b\u043a\u0443 \u043d\u0430 \u0441\u0432\u044f\u0437\u043d\u044b\u0439 \u0441\u043f\u0438\u0441\u043e\u043a, \u043a\u043e\u0442\u043e\u0440\u043e\u043c\u0443 \u043f\u0440\u0438\u043d\u0430\u0434\u043b\u0435\u0436\u0438\u0442. \u0414\u043e\u0432\u043e\u043b\u044c\u043d\u043e \u043f\u043e\u043b\u0435\u0437\u043d\u0430\u044f \u0432\u0435\u0449\u044c, \u0435\u0441\u043b\u0438 \u0432\u044b \u043d\u0435 \u0445\u043e\u0442\u0438\u0442\u0435 \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u043e \u0443\u0434\u0430\u043b\u0438\u0442\u044c \u043e\u0431\u044a\u0435\u043a\u0442 \u043d\u0435 \u0438\u0437 \u0442\u043e\u0439 \u043a\u043e\u043b\u043b\u0435\u043a\u0446\u0438\u0438. \u041c\u044b \u043f\u043e\u0439\u0434\u0451\u043c \u0442\u0435\u043c \u0436\u0435 \u043f\u0443\u0442\u0451\u043c. \u0414\u043e\u0431\u0430\u0432\u0438\u043c \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u043e \u0432 <code>RedBlackTreeNode&lt;&gt;<\/code>:<\/p>\n<pre><code class=\"cs\">public RedBlackTree&lt;TKey, TValue&gt; Tree { get; set; }<\/code><\/pre>\n<p>\u041a\u0440\u043e\u043c\u0435 \u0442\u043e\u0433\u043e, \u043d\u0430\u043c \u043f\u0440\u0438\u0433\u043e\u0434\u0438\u0442\u0441\u044f \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0432\u0441\u043f\u043e\u043c\u043e\u0433\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0445 \u043c\u0435\u0442\u043e\u0434\u043e\u0432:<\/p>\n<pre><code class=\"cs\">public RedBlackTreeCoordinate&lt;TKey, TValue&gt; GetMinimumCoordinate() {     return GetMinimumCoordinate(_root); }  public RedBlackTreeCoordinate&lt;TKey, TValue&gt; GetMinimumCoordinate(     RedBlackTreeNode&lt;TKey, TValue&gt; node) {     while (!IsVoid(node?.Left))         node = node.Left;      return !IsVoid(node)         ? new RedBlackTreeCoordinate&lt;TKey, TValue&gt;(node, node.Values.First)         : null; }  public RedBlackTreeCoordinate&lt;TKey, TValue&gt; GetMaximumCoordinate() {     return GetMaximumCoordinate(_root); }  public RedBlackTreeCoordinate&lt;TKey, TValue&gt; GetMaximumCoordinate(     RedBlackTreeNode&lt;TKey, TValue&gt; node) {     while (!IsVoid(node?.Right))         node = node.Right;      return !IsVoid(node)         ? new RedBlackTreeCoordinate&lt;TKey, TValue&gt;(node, node.Values.Last)         : null; }<\/code><\/pre>\n<p>\u041d\u0430\u043a\u043e\u043d\u0435\u0446, \u043c\u044b \u0433\u043e\u0442\u043e\u0432\u044b \u043a \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044e \u0434\u0430\u043d\u043d\u044b\u0445 \u043f\u043e \u043f\u0435\u0440\u0435\u0434\u0430\u043d\u043d\u043e\u0439 \u043a\u043e\u043e\u0440\u0434\u0438\u043d\u0430\u0442\u0435. \u041a\u043e\u0434 \u0431\u0443\u0434\u0435\u0442 \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0442\u044c <code>true<\/code>, \u0435\u0441\u043b\u0438 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u0435 \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u043e, \u0438 <code>false<\/code> \u0432 \u043f\u0440\u043e\u0442\u0438\u0432\u043d\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435:<\/p>\n<pre><code class=\"cs\">public bool Remove(RedBlackTreeCoordinate&lt;TKey, TValue&gt; coordinate) {     if (coordinate == null || coordinate.NodeElement.List == null)         return false;      var node = coordinate.TreeNode;     if (IsVoid(node) || node.Tree != this)         return false;      node.Values.Remove(coordinate.NodeElement);     if (node.Values.Count &gt; 0)         return true;      return Remove(node); }<\/code><\/pre>\n<p>\u041f\u0435\u0440\u0432\u044b\u043c \u0434\u0435\u043b\u043e\u043c \u043c\u044b \u0438\u0437\u044b\u043c\u0430\u0435\u043c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0438\u0437 \u0441\u043f\u0438\u0441\u043a\u0430 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0443\u0437\u043b\u0430. \u0415\u0441\u043b\u0438 \u043f\u043e\u0441\u043b\u0435 \u044d\u0442\u043e\u0433\u043e \u0432 \u0441\u043f\u0438\u0441\u043a\u0435 \u043e\u0441\u0442\u0430\u043b\u0438\u0441\u044c \u0434\u0430\u043d\u043d\u044b\u0435, \u0432\u044b\u0445\u043e\u0434\u0438\u043c \u0438\u0437 \u043c\u0435\u0442\u043e\u0434\u0430. \u041f\u0443\u0441\u0442\u043e\u0439 \u0436\u0435 \u0443\u0437\u0435\u043b \u043f\u043e\u0434\u043b\u0435\u0436\u0438\u0442 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044e:<\/p>\n<pre><code class=\"cs\">public bool Remove(RedBlackTreeNode&lt;TKey, TValue&gt; node) {     if (IsVoid(node) || node.Tree != this)         return false;      RedBlackTreeNode&lt;TKey, TValue&gt; child = null;     var nextNode = node;     var isNextNodeRed = nextNode.IsRed;                  if (IsVoid(node.Left))     {         child = node.Right;         Transplant(node, node.Right);     }     else if (IsVoid(node.Right))     {         child = node.Left;         Transplant(node, node.Left);     }     else     {         nextNode = GetMinimumCoordinate(node.Right).TreeNode;         isNextNodeRed = nextNode.IsRed;         child = nextNode.Right;                          if (nextNode != node.Right)         {             Transplant(nextNode, nextNode.Right);             nextNode.Right = node.Right;             nextNode.Right.Parent = nextNode;         }         else             child.Parent = nextNode;          Transplant(node, nextNode);         nextNode.Left = node.Left;         nextNode.Left.Parent = nextNode;         nextNode.IsRed = node.IsRed;     }      if (!isNextNodeRed)         RemoveFixup(child);      node.Tree = null;     Count--;      return true; }<\/code><\/pre>\n<p>\u0414\u0430\u0431\u044b \u043d\u0435 \u0432\u0438\u0434\u0435\u0442\u044c \u043e\u0448\u0438\u0431\u043e\u043a \u0432 \u043b\u043e\u0433\u0430\u0445 \u043a\u043e\u043c\u043f\u0438\u043b\u044f\u0446\u0438\u0438, \u043d\u0443\u0436\u043d\u043e \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u0442\u044c \u0434\u0432\u0430 \u043c\u0435\u0442\u043e\u0434\u0430: <code>Transplant<\/code> \u0438 <code>RemoveFixup<\/code>. \u041f\u0435\u0440\u0432\u044b\u0439 \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442 \u0437\u0430\u043c\u0435\u043d\u0443 \u043e\u0434\u043d\u043e\u0433\u043e \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u0430 \u043d\u0430 \u0434\u0440\u0443\u0433\u043e\u0435:<\/p>\n<pre><code class=\"cs\">private void Transplant(     RedBlackTreeNode&lt;TKey, TValue&gt; oldRoot,     RedBlackTreeNode&lt;TKey, TValue&gt; newRoot) {     var parent = oldRoot.Parent;      if (IsVoid(parent))         _root = newRoot;     else if (oldRoot == parent.Left)         parent.Left = newRoot;     else         parent.Right = newRoot;      newRoot.Parent = parent; }<\/code><\/pre>\n<p>\u0412\u0442\u043e\u0440\u043e\u0439 \u043c\u0435\u0442\u043e\u0434 \u2014 \u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u043e\u0432\u043a\u0430:<\/p>\n<pre><code class=\"cs\">private void RemoveFixup(RedBlackTreeNode&lt;TKey, TValue&gt; node) {     while (node != _root &amp;&amp; !node.IsRed)     {         var parent = node.Parent;          if (node == parent.Left)         {             var sibling = parent.Right;             if (IsVoid(sibling))                 break;              if (sibling.IsRed)             {                 sibling.IsRed = false;                 parent.IsRed = true;                 LeftRotate(parent);                 sibling = parent.Right;             }              if (!sibling.Left.IsRed &amp;&amp; !sibling.Right.IsRed)             {                 sibling.IsRed = true;                 node = parent;             }             else             {                 if (!sibling.Right.IsRed)                 {                     sibling.Left.IsRed = false;                     sibling.IsRed = true;                     RightRotate(sibling);                     sibling = parent.Right;                 }                  sibling.IsRed = parent.IsRed;                 parent.IsRed = false;                 sibling.Right.IsRed = false;                 LeftRotate(parent);                 node = _root;             }         }         else         {             var sibling = parent.Left;             if (IsVoid(sibling))                 break;              if (sibling.IsRed)             {                 sibling.IsRed = false;                 parent.IsRed = true;                 RightRotate(parent);                 sibling = parent.Left;             }              if (!sibling.Right.IsRed &amp;&amp; !sibling.Left.IsRed)             {                 sibling.IsRed = true;                 node = parent;             }             else             {                 if (!sibling.Left.IsRed)                 {                     sibling.Right.IsRed = false;                     sibling.IsRed = true;                     LeftRotate(sibling);                     sibling = parent.Left;                 }                  sibling.IsRed = parent.IsRed;                 parent.IsRed = false;                 sibling.Left.IsRed = false;                 RightRotate(parent);                 node = _root;             }         }     }      node.IsRed = false; }<\/code><\/pre>\n<p>\u0414\u043e\u0431\u0430\u0432\u043b\u044f\u0442\u044c \u0438 \u0443\u0434\u0430\u043b\u044f\u0442\u044c \u0434\u0430\u043d\u043d\u044b\u0435 \u043d\u0430\u0443\u0447\u0438\u043b\u0438\u0441\u044c, \u043e\u0441\u0442\u0430\u043b\u0430\u0441\u044c \u043e\u0434\u043d\u0430 \u0444\u0443\u043d\u0434\u0430\u043c\u0435\u043d\u0442\u0430\u043b\u044c\u043d\u0430\u044f \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044f: \u043f\u043e\u0438\u0441\u043a. \u0427\u0442\u043e\u0431\u044b \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u043a\u043e\u043e\u0440\u0434\u0438\u043d\u0430\u0442\u0443 \u043f\u043e \u0437\u0430\u0434\u0430\u043d\u043d\u044b\u043c \u043a\u043b\u044e\u0447\u0443 \u0438 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044e, \u0440\u0435\u0430\u043b\u0438\u0437\u0443\u0435\u043c \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u043d\u0435\u0431\u043e\u043b\u044c\u0448\u0438\u0445 \u043c\u0435\u0442\u043e\u0434\u043e\u0432:<\/p>\n<pre><code class=\"cs\">public RedBlackTreeCoordinate&lt;TKey, TValue&gt; GetCoordinate(     TKey key,     TValue value) {     return GetCoordinatesByKey(key).FirstOrDefault(c =&gt; c.Value.Equals(value)); }  public IEnumerable&lt;RedBlackTreeCoordinate&lt;TKey, TValue&gt;&gt; GetCoordinatesByKey(     TKey key) {     var node = GetNodeByKey(key);     if (IsVoid(node))         yield break;      for (var element = node.Values.First; element != null; element = element.Next)     {         yield return new RedBlackTreeCoordinate&lt;TKey, TValue&gt;(node, element);     } }  public RedBlackTreeNode&lt;TKey, TValue&gt; GetNodeByKey(TKey key) {     var node = _root;      while (!IsVoid(node) &amp;&amp; key.CompareTo(node.Key) != 0)     {         if (key.CompareTo(node.Key) &lt; 0)             node = node.Left;         else             node = node.Right;     }      return NodeOrNull(node); }<\/code><\/pre>\n<p>\u0422\u0443\u0442 \u0441\u0442\u043e\u0438\u0442 \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u043d\u0435\u043f\u0440\u0438\u044f\u0442\u043d\u043e\u0435 \u0437\u0430\u043c\u0435\u0447\u0430\u043d\u0438\u0435. \u0414\u0430, \u0432 \u0441\u0440\u0435\u0434\u043d\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u043f\u043e\u0438\u0441\u043a\u0430 \u043b\u043e\u0433\u0430\u0440\u0438\u0444\u043c\u0438\u0447\u0435\u0441\u043a\u0430\u044f, \u043d\u043e \u0447\u0442\u043e \u0431\u0443\u0434\u0435\u0442 \u043f\u0440\u0438 \u043d\u0430\u043b\u0438\u0447\u0438\u0438 \u0431\u043e\u043b\u044c\u0448\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439 \u0441 \u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u044b\u043c\u0438 \u043a\u043b\u044e\u0447\u0430\u043c\u0438? \u041a\u043e\u043b\u044c \u043c\u044b \u0438\u0449\u0435\u043c \u043e\u0431\u044a\u0435\u043a\u0442 \u0432 \u0443\u0437\u043b\u0435 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e, \u0442\u043e \u0443\u0432\u044b, \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u043e\u043a\u0430\u0436\u0435\u0442\u0441\u044f \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0439. \u041d\u043e \u044d\u0442\u043e \u0445\u0443\u0434\u0448\u0438\u0439 \u0441\u043b\u0443\u0447\u0430\u0439.<\/p>\n<p>\u041c\u043e\u0436\u043d\u043e, \u043d\u0430\u0432\u0435\u0440\u043d\u043e\u0435, \u043f\u0440\u0438\u0439\u0442\u0438 \u043a\u0430\u043a-\u0442\u043e \u043a \u043b\u043e\u0433\u0430\u0440\u0438\u0444\u043c\u0443, \u043d\u043e \u0431\u044b\u0441\u0442\u0440\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u043d\u0435 \u043f\u0440\u0438\u0434\u0443\u043c\u0430\u043b\u043e\u0441\u044c. \u0425\u0440\u0430\u043d\u0438\u0442\u044c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0432 \u043c\u0438\u043d\u0438-\u0434\u0435\u0440\u0435\u0432\u0435 \u0441 \u0445\u0435\u0448-\u043a\u043e\u0434\u043e\u043c \u0432 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u043a\u043b\u044e\u0447\u0430 \u0442\u043e\u0436\u0435 \u043d\u0435 \u0432\u0430\u0440\u0438\u0430\u043d\u0442: \u043e\u0431\u044a\u0435\u043a\u0442\u044b \u0432\u0435\u0434\u044c \u043c\u043e\u0433\u0443\u0442 \u0431\u044b\u0442\u044c \u043c\u0443\u0442\u0430\u0431\u0435\u043b\u044c\u043d\u044b\u043c\u0438 (\u0438\u0437\u043c\u0435\u043d\u044f\u0435\u043c\u044b\u043c\u0438). \u0414\u0430 \u0438 \u0443\u0441\u0442\u0440\u043e\u0439\u0441\u0442\u0432\u043e \u0443\u0437\u043b\u0430 \u0441\u0442\u0430\u043d\u0435\u0442 \u0437\u043d\u0430\u0447\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0441\u043b\u043e\u0436\u043d\u0435\u0435. \u0412 \u043e\u0431\u0449\u0435\u043c, \u044f \u043f\u043e\u0441\u0447\u0438\u0442\u0430\u043b, \u0447\u0442\u043e \u0438\u0433\u0440\u0430 \u043d\u0435 \u0441\u0442\u043e\u0438\u0442 \u0441\u0432\u0435\u0447. \u0412\u043e\u0437\u043c\u043e\u0436\u043d\u043e, \u0432\u044b \u0441\u043c\u043e\u0436\u0435\u0442\u0435 \u043f\u043e\u0434\u0441\u043a\u0430\u0437\u0430\u0442\u044c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c.<\/p>\n<p>\u0418 \u0442\u0430\u043a, \u043e\u0441\u043d\u043e\u0432\u043d\u044b\u0435 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u043d\u044b. \u041d\u043e \u044d\u0442\u043e\u0433\u043e \u043c\u0430\u043b\u043e. \u041a\u0430\u043a\u0430\u044f \u043a\u043e\u043b\u043b\u0435\u043a\u0446\u0438\u044f \u0431\u0435\u0437 \u043a\u043e\u043d\u0441\u0442\u0440\u0443\u043a\u0442\u043e\u0440\u0430, \u043f\u0440\u0438\u043d\u0438\u043c\u0430\u044e\u0449\u0435\u0433\u043e \u043d\u0430\u0431\u043e\u0440 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432? \u0414\u043e\u0431\u0430\u0432\u0438\u043c \u0442\u0430\u043a\u043e\u0439:<\/p>\n<pre><code class=\"cs\">public RedBlackTree() { }  public RedBlackTree(IEnumerable&lt;TValue&gt; values, Func&lt;TValue, TKey&gt; keySelector) {     foreach (var v in values)     {         Add(keySelector(v), v);     } }<\/code><\/pre>\n<p>\u041f\u0430\u0440\u0430 \u0440\u0435\u043c\u0430\u0440\u043e\u043a:<\/p>\n<ol>\n<li>\n<p>\u0415\u0441\u043b\u0438 \u0432\u044b \u0437\u0430\u0440\u0430\u043d\u0435\u0435 \u0437\u043d\u0430\u0435\u0442\u0435, \u0447\u0442\u043e \u043f\u0435\u0440\u0435\u0434\u0430\u0432\u0430\u0435\u043c\u0430\u044f \u043a\u043e\u043b\u043b\u0435\u043a\u0446\u0438\u044f \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u0430, \u043c\u043e\u0436\u043d\u043e \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0441\u043e\u0437\u0434\u0430\u043d\u0438\u0435 \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430: \u043f\u0435\u0440\u0432\u0430\u044f \u043f\u043e\u043b\u043e\u0432\u0438\u043d\u0430 \u0431\u0443\u0434\u0435\u0442 \u043b\u0435\u0432\u044b\u043c \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u043e\u043c, \u0432\u0442\u043e\u0440\u0430\u044f \u2014 \u043f\u0440\u0430\u0432\u044b\u043c, \u0438 \u043f\u043e\u0432\u0442\u043e\u0440\u044f\u0435\u043c \u043f\u0440\u043e\u0446\u0435\u0434\u0443\u0440\u0443 \u0434\u043b\u044f \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u044c\u0435\u0432. \u041e\u0441\u0442\u0430\u043d\u0435\u0442\u0441\u044f \u0442\u043e\u043b\u044c\u043a\u043e \u043f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u043e \u201c\u0440\u0430\u0441\u043a\u0440\u0430\u0441\u0438\u0442\u044c\u201d \u0443\u0437\u043b\u044b \u0438 \u043d\u0435 \u0437\u0430\u0431\u044b\u0442\u044c \u043f\u0440\u043e \u0433\u0440\u0443\u043f\u043f\u0438\u0440\u043e\u0432\u043a\u0443 \u043e\u0431\u044a\u0435\u043a\u0442\u043e\u0432 \u0441 \u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u044b\u043c\u0438 \u043a\u043b\u044e\u0447\u0430\u043c\u0438.<\/p>\n<\/li>\n<li>\n<p>\u042f \u043f\u0435\u0440\u0435\u0434\u0430\u044e \u043d\u0435 \u0441\u0430\u043c\u0438 \u043a\u043b\u044e\u0447\u0438, \u0430 \u0444\u0443\u043d\u043a\u0446\u0438\u044e-\u0441\u0435\u043b\u0435\u043a\u0442\u043e\u0440, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043f\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044e \u043e\u0442\u0434\u0430\u0451\u0442 \u0435\u0433\u043e \u043a\u043b\u044e\u0447.<\/p>\n<\/li>\n<\/ol>\n<p>\u0412\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u044f\u0441\u044c \u043a \u0432\u043e\u0441\u043f\u0440\u043e\u0438\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u044e \u0434\u0430\u043d\u043d\u044b\u0445 \u0432 DryWetMIDI: \u0430 \u043a\u0430\u043a \u043f\u0435\u0440\u0435\u0439\u0442\u0438 \u043a \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u043c\u0443 \u0441\u043e\u0431\u044b\u0442\u0438\u044e, \u0435\u0441\u043b\u0438 \u043f\u0440\u0438\u0448\u043b\u043e \u0432\u0440\u0435\u043c\u044f \u0435\u0433\u043e \u043f\u0440\u043e\u0438\u0433\u0440\u044b\u0432\u0430\u0442\u044c? \u201c\u0423\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c\u201d \u043d\u0430 \u0442\u0435\u043a\u0443\u0449\u0435\u0435 \u0441\u043e\u0431\u044b\u0442\u0438\u0435 \u044d\u0442\u043e \u043a\u0430\u043a \u0440\u0430\u0437 \u043a\u043e\u043e\u0440\u0434\u0438\u043d\u0430\u0442\u0430 \u0432 \u0434\u0435\u0440\u0435\u0432\u0435. \u041f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0443\u044e \u0432 \u0445\u0440\u043e\u043d\u043e\u043b\u043e\u0433\u0438\u0447\u0435\u0441\u043a\u043e\u043c \u043f\u043e\u0440\u044f\u0434\u043a\u0435 \u043f\u043e\u043c\u043e\u0433\u0430\u0435\u0442 \u043c\u0435\u0442\u043e\u0434 <code>GetNextCoordinate<\/code>:<\/p>\n<pre><code class=\"cs\">public RedBlackTreeCoordinate&lt;TKey, TValue&gt; GetNextCoordinate(     RedBlackTreeCoordinate&lt;TKey, TValue&gt; coordinate) {     if (coordinate == null || IsVoid(coordinate.TreeNode))         return null;      var nextElement = coordinate.NodeElement.Next;     if (nextElement != null)         return new RedBlackTreeCoordinate&lt;TKey, TValue&gt;(             coordinate.TreeNode,             nextElement);      var node = coordinate.TreeNode;      var right = node.Right;     if (!IsVoid(right))         return GetMinimumCoordinate(right);      var nextNode = node.Parent;      while (!IsVoid(nextNode))     {         if (node == nextNode.Left)             return new RedBlackTreeCoordinate&lt;TKey, TValue&gt;(                 nextNode,                 nextNode.Values.First);          node = nextNode;         nextNode = node.Parent;     }      return IsVoid(nextNode)         ? null         : new RedBlackTreeCoordinate&lt;TKey, TValue&gt;(nextNode, nextNode.Values.First); }<\/code><\/pre>\n<p>\u0418 \u043c\u0435\u0442\u043e\u0434-\u0430\u043d\u0442\u0438\u043f\u043e\u0434:<\/p>\n<pre><code class=\"cs\">public RedBlackTreeCoordinate&lt;TKey, TValue&gt; GetPreviousCoordinate(     RedBlackTreeCoordinate&lt;TKey, TValue&gt; coordinate) {     if (coordinate == null || IsVoid(coordinate.TreeNode))         return null;      var previousElement = coordinate.NodeElement.Previous;     if (previousElement != null)         return new RedBlackTreeCoordinate&lt;TKey, TValue&gt;(             coordinate.TreeNode,             previousElement);      var node = coordinate.TreeNode;      var left = node.Left;     if (!IsVoid(left))         return GetMaximumCoordinate(left);      var previousNode = node.Parent;      while (!IsVoid(previousNode))     {         if (node == previousNode.Right)             return new RedBlackTreeCoordinate&lt;TKey, TValue&gt;(                 previousNode,                 previousNode.Values.Last);          node = previousNode;         previousNode = node.Parent;     }      return IsVoid(previousNode)         ? null         : new RedBlackTreeCoordinate&lt;TKey, TValue&gt;(             previousNode,             previousNode.Values.Last); }<\/code><\/pre>\n<p>\u041c\u043e\u0436\u0435\u043c \u0434\u0430\u0436\u0435 \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u0432\u043e\u043e\u0431\u0449\u0435 \u0432\u0441\u0435 \u043a\u043e\u043e\u0440\u0434\u0438\u043d\u0430\u0442\u044b (\u0440\u0430\u0437\u0443\u043c\u0435\u0435\u0442\u0441\u044f, \u0447\u0435\u0440\u0435\u0437 <code>IEnumerable&lt;&gt;<\/code>, \u043f\u043e\u0431\u0435\u0440\u0435\u0436\u0451\u043c \u043f\u0430\u043c\u044f\u0442\u044c):<\/p>\n<pre><code class=\"cs\">public IEnumerable&lt;RedBlackTreeCoordinate&lt;TKey, TValue&gt;&gt; GetAllCoordinates() {     var coordinate = GetMinimumCoordinate();     if (coordinate == null || IsVoid(coordinate.TreeNode))         yield break;      do     {         yield return coordinate;     }     while ((coordinate = GetNextCoordinate(coordinate)) != null); }<\/code><\/pre>\n<p>\u042d\u0442\u043e\u0442 \u043c\u0435\u0442\u043e\u0434 \u043e\u0442\u043a\u0440\u044b\u0432\u0430\u0435\u0442 \u043d\u0430\u043c \u0434\u0432\u0435\u0440\u0438 \u0432 \u043e\u0431\u0449\u0435\u0441\u0442\u0432\u043e \u043f\u043e\u043b\u043d\u043e\u0446\u0435\u043d\u043d\u044b\u0445 \u043a\u043e\u043b\u043b\u0435\u043a\u0446\u0438\u0439 \u2014 \u043e\u0441\u0442\u0430\u043b\u043e\u0441\u044c \u0442\u043e\u043b\u044c\u043a\u043e \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u0442\u044c <code>IEnumerable&lt;&gt;<\/code>:<\/p>\n<pre><code class=\"cs\">public class RedBlackTree&lt;TKey, TValue&gt; : IEnumerable&lt;TValue&gt;  ...  public IEnumerator&lt;TValue&gt; GetEnumerator() {     foreach (var coordinate in GetAllCoordinates())     {         yield return coordinate.Value;     } }  IEnumerator IEnumerable.GetEnumerator() {     return GetEnumerator(); }<\/code><\/pre>\n<p>\u041a\u0440\u0430\u0441\u043d\u043e-\u0447\u0451\u0440\u043d\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e \u0433\u043e\u0442\u043e\u0432\u043e \u043a \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u044e.<\/p>\n<p><a class=\"anchor\" name=\"intervaltree\" id=\"intervaltree\"><\/a><\/p>\n<h2>\u0414\u0435\u0440\u0435\u0432\u043e \u0438\u043d\u0442\u0435\u0440\u0432\u0430\u043b\u043e\u0432<\/h2>\n<p>\u041d\u043e \u043d\u0430 \u044d\u0442\u043e\u043c \u043c\u043e\u0451 \u0432\u0437\u0430\u0438\u043c\u043e\u0434\u0435\u0439\u0441\u0442\u0432\u0438\u0435 \u0441 \u0444\u043b\u043e\u0440\u043e\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u043c\u0438\u0440\u0430 \u043d\u0435 \u0437\u0430\u043a\u043e\u043d\u0447\u0438\u043b\u043e\u0441\u044c. \u0412 DryWetMIDI \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u044c \u043c\u043e\u0436\u0435\u0442 \u0432\u044b\u0437\u0432\u0430\u0442\u044c, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u043c\u0435\u0442\u043e\u0434 <a href=\"https:\/\/melanchall.github.io\/drywetmidi\/api\/Melanchall.DryWetMidi.Multimedia.Playback.html#Melanchall_DryWetMidi_Multimedia_Playback_MoveToTime_Melanchall_DryWetMidi_Interaction_ITimeSpan_\" rel=\"noopener noreferrer nofollow\">MoveToTime<\/a> \u0438\u043b\u0438 <a href=\"https:\/\/melanchall.github.io\/drywetmidi\/api\/Melanchall.DryWetMidi.Multimedia.Playback.html#Melanchall_DryWetMidi_Multimedia_Playback_MoveToNextSnapPoint\" rel=\"noopener noreferrer nofollow\">MoveToNextSnapPoint<\/a> \u0438 \u043f\u0435\u0440\u0435\u043c\u0435\u0441\u0442\u0438\u0442\u044c\u0441\u044f \u0432 \u043d\u043e\u0432\u0443\u044e \u0442\u043e\u0447\u043a\u0443 \u0432\u043e\u0441\u043f\u0440\u043e\u0438\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u044f. \u041f\u0440\u0438 \u044d\u0442\u043e\u043c \u043f\u043e \u0443\u043c\u043e\u043b\u0447\u0430\u043d\u0438\u044e \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0430 \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u0442, \u043a\u0430\u043a\u0438\u0435 \u043d\u043e\u0442\u044b \u043d\u0430\u0445\u043e\u0434\u044f\u0442\u0441\u044f \u0432 \u043d\u043e\u0432\u043e\u0439 \u043f\u043e\u0437\u0438\u0446\u0438\u0438. \u0422\u0430\u043a \u043a\u0430\u043a \u043d\u043e\u0442\u044b \u0445\u0430\u0440\u0430\u043a\u0442\u0435\u0440\u0438\u0437\u0443\u044e\u0442\u0441\u044f \u043d\u0430\u0447\u0430\u043b\u043e\u043c \u0438 \u043a\u043e\u043d\u0446\u043e\u043c, \u0437\u0430\u0434\u0430\u0447\u0430 \u0441\u0432\u043e\u0434\u0438\u0442\u0441\u044f \u043a \u043d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u044e \u0432\u0441\u0435\u0445 \u0438\u043d\u0442\u0435\u0440\u0432\u0430\u043b\u043e\u0432, \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0449\u0438\u0445 \u0437\u0430\u0434\u0430\u043d\u043d\u0443\u044e \u0442\u043e\u0447\u043a\u0443.<\/p>\n<p>\u0417\u0434\u0435\u0441\u044c \u043c\u043e\u0438\u0445 \u0437\u043d\u0430\u043d\u0438\u0439 \u043e\u043a\u0430\u0437\u0430\u043b\u043e\u0441\u044c \u043d\u0435\u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e. \u041a\u0430\u043a \u0432\u044b\u043f\u043e\u043b\u043d\u0438\u0442\u044c \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u044b\u0439 (\u043d\u0435 \u043f\u0435\u0440\u0435\u0431\u043e\u0440\u043e\u043c) \u043f\u043e\u0438\u0441\u043a \u043e\u0442\u0440\u0435\u0437\u043a\u043e\u0432 \u044f \u043d\u0435 \u0437\u043d\u0430\u043b. \u0418 \u0441\u043d\u043e\u0432\u0430 \u0432\u0441\u0451 \u0441\u0434\u0435\u043b\u0430\u043b\u0438 \u0434\u043e \u043d\u0430\u0441 \u2014 \u0432\u0435\u043b\u0438\u043a\u0438\u0435 \u0443\u043c\u044b \u043f\u0440\u0438\u0434\u0443\u043c\u0430\u043b\u0438 <a href=\"https:\/\/en.wikipedia.org\/wiki\/Interval_tree\" rel=\"noopener noreferrer nofollow\">\u0434\u0435\u0440\u0435\u0432\u043e \u0438\u043d\u0442\u0435\u0440\u0432\u0430\u043b\u043e\u0432<\/a>. \u0427\u0442\u043e \u0441\u0430\u043c\u043e\u0435 \u0437\u0430\u043c\u0435\u0447\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0435, \u0435\u0433\u043e \u043c\u043e\u0436\u043d\u043e \u043f\u043e\u0441\u0442\u0440\u043e\u0438\u0442\u044c \u043d\u0430 \u043e\u0441\u043d\u043e\u0432\u0435 \u043a\u0440\u0430\u0441\u043d\u043e-\u0447\u0451\u0440\u043d\u043e\u0433\u043e.<\/p>\n<p>\u0418\u0434\u0435\u044f \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0430\u044f:<\/p>\n<ul>\n<li>\n<p>\u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u044f\u0432\u043b\u044f\u044e\u0442\u0441\u044f \u0438\u043d\u0442\u0435\u0440\u0432\u0430\u043b\u0430\u043c\u0438;<\/p>\n<\/li>\n<li>\n<p>\u043a\u0430\u0436\u0434\u044b\u0439 \u0443\u0437\u0435\u043b \u043f\u043e\u043c\u0438\u043c\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439 \u0445\u0440\u0430\u043d\u0438\u0442 \u043c\u0430\u043a\u0441\u0438\u043c\u0443\u043c \u0441\u0440\u0435\u0434\u0438 \u043a\u043e\u043d\u0446\u043e\u0432 \u0438\u043d\u0442\u0435\u0440\u0432\u0430\u043b\u043e\u0432 \u0442\u0435\u043a\u0443\u0449\u0438\u0445 \u0438 \u0434\u043e\u0447\u0435\u0440\u043d\u0438\u0445 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439; \u043d\u0430\u0437\u043e\u0432\u0451\u043c \u044d\u0442\u043e\u0442 \u0430\u0442\u0440\u0438\u0431\u0443\u0442 <strong>\u0433\u0440\u0430\u043d\u0438\u0446\u0435\u0439<\/strong>;<\/p>\n<\/li>\n<li>\n<p>\u043a\u043b\u044e\u0447\u043e\u043c \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043d\u0430\u0447\u0430\u043b\u043e \u0438\u043d\u0442\u0435\u0440\u0432\u0430\u043b\u0430.<\/p>\n<\/li>\n<\/ul>\n<figure class=\"full-width\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/aa4\/4e7\/17a\/aa44e717a1b18da8faf5e2c5abcc9a44.png\" width=\"780\" height=\"452\" sizes=\"auto, (max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/r\/w780\/getpro\/habr\/upload_files\/aa4\/4e7\/17a\/aa44e717a1b18da8faf5e2c5abcc9a44.png 780w,&#10;       https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/aa4\/4e7\/17a\/aa44e717a1b18da8faf5e2c5abcc9a44.png 781w\" loading=\"lazy\" decode=\"async\"\/><\/figure>\n<p>\u041e\u0442 \u0441\u043b\u043e\u0432 \u043a \u0434\u0435\u043b\u0443. \u0421\u0430\u043c\u043e \u0434\u0435\u0440\u0435\u0432\u043e \u043e\u0431\u044a\u044f\u0432\u0438\u043c \u0442\u0430\u043a:<\/p>\n<pre><code class=\"cs\">public sealed class IntervalTree&lt;TKey, TValue&gt; : RedBlackTree&lt;TKey, TValue&gt;     where TKey : IComparable&lt;TKey&gt;     where TValue : IInterval&lt;TKey&gt; { }<\/code><\/pre>\n<p>\u0421\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u043d\u0435 \u0432\u0441\u0435\u044f\u0434\u043d\u0430\u044f, \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0434\u043e\u043b\u0436\u043d\u044b \u0431\u044b\u0442\u044c \u0438\u043d\u0442\u0435\u0440\u0432\u0430\u043b\u0430\u043c\u0438:<\/p>\n<pre><code class=\"cs\">public interface IInterval&lt;TEndpoint&gt; {     TEndpoint Start { get; }      TEndpoint End { get; } }<\/code><\/pre>\n<p>\u0421\u043e\u0433\u043b\u0430\u0441\u043d\u043e \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u044e \u043d\u0430\u043c \u043d\u0443\u0436\u043d\u043e \u0434\u043e\u0431\u0430\u0432\u0438\u0442\u044c \u0432 \u0443\u0437\u0435\u043b \u0433\u0440\u0430\u043d\u0438\u0446\u0443. \u042f \u043d\u0435 \u0441\u0442\u0430\u043b \u0432\u043e\u0437\u0432\u043e\u0434\u0438\u0442\u044c \u0441\u043b\u043e\u0436\u043d\u044b\u0435 \u0438\u0435\u0440\u0430\u0440\u0445\u0438\u0438 \u043d\u0430\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u043d\u0438\u044f, \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u044f \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u044b\u0439 \u043a\u043b\u0430\u0441\u0441 \u0434\u043b\u044f \u0443\u0437\u043b\u0430 \u0438\u043d\u0442\u0435\u0440\u0432\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430, \u0438 \u043f\u0440\u043e\u0441\u0442\u043e \u0441\u043d\u0430\u0431\u0434\u0438\u043b <code>RedBlackTreeNode&lt;&gt;<\/code> \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u043e\u043c <code>Data<\/code>:<\/p>\n<pre><code class=\"cs\">public TKey Data { get; set; }<\/code><\/pre>\n<p>\u041f\u043e\u043b\u0443\u0447\u0438\u043b\u043e\u0441\u044c \u043d\u0435 \u0441\u043e\u0432\u0441\u0435\u043c \u043a\u0440\u0430\u0441\u0438\u0432\u043e: \u043d\u0430\u0437\u0432\u0430\u043d\u0438\u0435 \u043f\u043e\u0434\u0440\u0430\u0437\u0443\u043c\u0435\u0432\u0430\u0435\u0442 \u0432\u0441\u0451 \u0447\u0442\u043e \u0443\u0433\u043e\u0434\u043d\u043e, \u0430 \u043c\u044b \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0438\u0432\u0430\u0435\u043c \u0434\u043e\u043f\u0443\u0441\u0442\u0438\u043c\u044b\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0442\u0438\u043f\u043e\u043c <code>TKey<\/code>. \u041d\u043e \u0434\u043b\u044f \u043c\u043e\u0438\u0445 \u043d\u0443\u0436\u0434 \u044d\u0442\u043e \u043d\u0435 \u0431\u044b\u043b\u043e \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u043e\u0439.<\/p>\n<p>\u0421\u0442\u043e\u0438\u0442 \u043e\u0442\u043c\u0435\u0442\u0438\u0442\u044c, \u0447\u0442\u043e \u043c\u0435\u0442\u043e\u0434\u044b \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u0438 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044f \u0434\u0430\u043d\u043d\u044b\u0445 \u043f\u0435\u0440\u0435\u0434\u0430\u044e\u0442\u0441\u044f \u0434\u0435\u0440\u0435\u0432\u0443 \u0438\u043d\u0442\u0435\u0440\u0432\u0430\u043b\u043e\u0432 \u043f\u043e \u043d\u0430\u0441\u043b\u0435\u0434\u0441\u0442\u0432\u0443 \u043e\u0442 \u043a\u0440\u0430\u0441\u043d\u043e-\u0447\u0451\u0440\u043d\u043e\u0433\u043e \u0431\u0435\u0437 \u0438\u0437\u043c\u0435\u043d\u0435\u043d\u0438\u0439. \u041f\u043e\u044d\u0442\u043e\u043c\u0443 \u043e\u0441\u0442\u0430\u0451\u0442\u0441\u044f \u043b\u0438\u0448\u044c \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u0442\u044c \u043f\u043e\u0438\u0441\u043a. \u0417\u043d\u0430\u044f \u0433\u0440\u0430\u043d\u0438\u0446\u044b \u0443\u0437\u043b\u043e\u0432 (\u0438\u043b\u0438, \u0438\u043d\u0430\u0447\u0435 \u0433\u043e\u0432\u043e\u0440\u044f, \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u044c\u0435\u0432), \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u044d\u0442\u043e \u043d\u0435 \u0441\u043e\u0441\u0442\u0430\u0432\u0438\u0442 \u0442\u0440\u0443\u0434\u0430:<\/p>\n<pre><code class=\"cs\">public IEnumerable&lt;RedBlackTreeCoordinate&lt;TKey, TValue&gt;&gt; Search(TKey point) {     var queue = new Queue&lt;RedBlackTreeNode&lt;TKey, TValue&gt;&gt;();     queue.Enqueue(_root);      while (queue.Count &gt; 0)     {         var node = queue.Dequeue();          if (IsVoid(node) || node.Tree != this)             continue;          if (point.CompareTo(node.Data) &gt;= 0)             continue;          queue.Enqueue(node.Left);          for (var element = node.Values.First; element != null; element = element.Next)         {             var interval = element.Value;             if (interval.Start.CompareTo(point) &lt; 0 &amp;&amp;                 interval.End.CompareTo(point) &gt; 0)                 yield return new RedBlackTreeCoordinate&lt;TKey, TValue&gt;(node, element);         }          if (point.CompareTo(node.Key) &lt;= 0)             continue;          queue.Enqueue(node.Right);     } }<\/code><\/pre>\n<p>\u041d\u043e \u043a\u0430\u043a \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u0442 \u0443\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0430 \u044d\u0442\u043e\u0433\u043e \u0441\u0430\u043c\u043e\u0433\u043e \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u0430 <code>Data<\/code>? \u041d\u0430\u0447\u043d\u0451\u043c \u0441 \u043f\u0440\u043e\u0441\u0442\u043e\u0433\u043e. \u041d\u0430\u043f\u0438\u0448\u0435\u043c \u043c\u0435\u0442\u043e\u0434, \u043e\u0431\u043d\u043e\u0432\u043b\u044f\u044e\u0449\u0438\u0439 \u0433\u0440\u0430\u043d\u0438\u0446\u0443 \u0432 \u0437\u0430\u0434\u0430\u043d\u043d\u043e\u043c \u0443\u0437\u043b\u0435:<\/p>\n<pre><code class=\"cs\">public bool UpdateMax(RedBlackTreeNode&lt;TKey, TValue&gt; node) {     if (node.Values.Count == 0)         return false;      var result = node.Values.First.Value.End;      foreach (var value in node.Values)     {         if (value.End.CompareTo(result) &gt; 0)             result = value.End;     }      var left = node.Left;     if (!IsVoid(left))     {         var leftMax = left.Data;         if (leftMax.CompareTo(result) &gt; 0)             result = leftMax;     }      var right = node.Right;     if (!IsVoid(right))     {         var rightMax = right.Data;         if (rightMax.CompareTo(result) &gt; 0)             result = rightMax;     }      if (node.Data.Equals(result))         return false;      node.Data = result;     return true; }<\/code><\/pre>\n<p>\u0422\u0430\u043a\u0436\u0435 \u043f\u043e\u043d\u0430\u0434\u043e\u0431\u0438\u0442\u0441\u044f \u043c\u0435\u0442\u043e\u0434, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0437\u0430\u043f\u0443\u0441\u043a\u0430\u0435\u0442 \u043e\u0431\u043d\u043e\u0432\u043b\u0435\u043d\u0438\u0435 \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u0430 <code>Data<\/code> \u0432\u0432\u0435\u0440\u0445 \u043f\u043e \u0434\u0435\u0440\u0435\u0432\u0443. \u0412\u0435\u0434\u044c \u0435\u0441\u043b\u0438 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0432 \u0443\u0437\u043b\u0435 \u043f\u043e\u043c\u0435\u043d\u044f\u043b\u0438\u0441\u044c, \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e, \u043d\u0443\u0436\u043d\u043e \u043e\u0431\u043d\u043e\u0432\u0438\u0442\u044c \u0433\u0440\u0430\u043d\u0438\u0446\u0443 \u0432 \u0435\u0433\u043e \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u0435, \u0438 \u0432 \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u0435 \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044f \u0438 \u0442.\u0434.<\/p>\n<pre><code class=\"cs\">public void UpdateMaxUp(RedBlackTreeNode&lt;TKey, TValue&gt; node) {     while (true)     {         var parent = node.Parent;         if (IsVoid(parent) || !UpdateMax(parent))             break;          node = parent;     } }<\/code><\/pre>\n<p>\u041d\u043e \u0432 \u043a\u0430\u043a\u043e\u043c \u043c\u0435\u0441\u0442\u0435 \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u0442 \u0432\u044b\u0437\u043e\u0432 \u043c\u0435\u0442\u043e\u0434\u043e\u0432 <code>UpdateMax<\/code> \u0438 <code>UpdateMaxUp<\/code>? \u0427\u0442\u043e \u043c\u043e\u0436\u0435\u0442 \u043f\u0440\u0438\u0432\u0435\u0441\u0442\u0438 \u043a \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e\u0441\u0442\u0438 \u043f\u0435\u0440\u0435\u0441\u0447\u0438\u0442\u044b\u0432\u0430\u0442\u044c \u0433\u0440\u0430\u043d\u0438\u0446\u0443?<\/p>\n<p>\u0412 \u0434\u0435\u0440\u0435\u0432\u0435 \u0435\u0441\u0442\u044c \u0442\u043e\u043b\u044c\u043a\u043e \u0434\u0432\u0435 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438, \u043c\u043e\u0434\u0438\u0444\u0438\u0446\u0438\u0440\u0443\u044e\u0449\u0438\u0435 \u0435\u0433\u043e: \u0432\u0441\u0442\u0430\u0432\u043a\u0430 \u0438 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u0435. \u041d\u0430\u0447\u043d\u0451\u043c \u0441 \u043f\u0435\u0440\u0432\u043e\u0439. \u041a\u0430\u043a\u0438\u0435 \u043a\u043e\u043d\u043a\u0440\u0435\u0442\u043d\u043e \u0438\u043d\u0441\u0442\u0440\u0443\u043a\u0446\u0438\u0438 \u0432\u043e \u0432\u0440\u0435\u043c\u044f \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u0434\u0430\u043d\u043d\u044b\u0445 \u043c\u043e\u0433\u0443\u0442 \u043f\u0440\u0438\u0432\u0435\u0441\u0442\u0438 \u043a \u0438\u0437\u043c\u0435\u043d\u0435\u043d\u0438\u044e \u0433\u0440\u0430\u043d\u0438\u0446 \u0443\u0437\u043b\u043e\u0432? \u041f\u0440\u0435\u0436\u0434\u0435 \u0432\u0441\u0435\u0433\u043e \u2014 \u0432\u0441\u0442\u0430\u0432\u043a\u0430 \u043d\u043e\u0432\u043e\u0433\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f. \u0414\u043e\u0431\u0430\u0432\u0438\u043c \u0432 <code>RedBlackTree&lt;&gt;<\/code> \u043f\u0443\u0441\u0442\u043e\u0439 \u0432\u0438\u0440\u0442\u0443\u0430\u043b\u044c\u043d\u044b\u0439 \u043c\u0435\u0442\u043e\u0434 <code>OnValueAdded<\/code>:<\/p>\n<pre><code class=\"cs\">protected virtual void OnValueAdded(     RedBlackTreeCoordinate&lt;TKey, TValue&gt; coordinate,     TValue value) { }<\/code><\/pre>\n<p>\u0418 \u0432\u044b\u0437\u043e\u0432\u0435\u043c \u0435\u0433\u043e \u0432\u043d\u0443\u0442\u0440\u0438 <code>Add<\/code>. \u0412\u043e-\u043f\u0435\u0440\u0432\u044b\u0445, \u0442\u0443\u0442:<\/p>\n<pre><code class=\"cs\">OnValueAdded(coordinateOnExistingNode, value); return coordinateOnExistingNode;<\/code><\/pre>\n<p>\u0412\u043e-\u0432\u0442\u043e\u0440\u044b\u0445, \u0437\u0434\u0435\u0441\u044c:<\/p>\n<pre><code class=\"cs\">OnValueAdded(result, value); InsertFixup(newNode);<\/code><\/pre>\n<p>\u0420\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u0432\u043d\u0443\u0442\u0440\u0438 <code>IntervalTree&lt;&gt;<\/code>:<\/p>\n<pre><code class=\"cs\">protected override void OnValueAdded(     RedBlackTreeCoordinate&lt;TKey, TValue&gt; coordinate,     TValue value) {     base.OnValueAdded(coordinate, value);      var end = value.End;     if (!UpdateMaxByNewValue(coordinate.TreeNode, end))         return;      UpdateMaxUp(coordinate.TreeNode); }<\/code><\/pre>\n<p>\u041f\u0440\u0438 \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u0438 \u043b\u0435\u0433\u043a\u043e \u043f\u043e\u043d\u044f\u0442\u044c, \u043d\u0443\u0436\u043d\u043e \u043b\u0438 \u043f\u0440\u043e\u0432\u0435\u0441\u0442\u0438 \u043a\u0430\u0441\u043a\u0430\u0434 \u043e\u0431\u043d\u043e\u0432\u043b\u0435\u043d\u0438\u0439 \u0433\u0440\u0430\u043d\u0438\u0446\u044b. \u0422\u0430\u043a\u0443\u044e \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u0443 (\u0438 \u043e\u0431\u043d\u043e\u0432\u043b\u0435\u043d\u0438\u0435 \u0433\u0440\u0430\u043d\u0438\u0446\u044b \u0442\u0435\u043a\u0443\u0449\u0435\u0433\u043e \u0443\u0437\u043b\u0430) \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442 \u043c\u0435\u0442\u043e\u0434 <code>UpdateMaxByNewValue<\/code>:<\/p>\n<pre><code class=\"cs\">private bool UpdateMaxByNewValue(RedBlackTreeNode&lt;TKey, TValue&gt; node, TKey end) {     var data = node.Data;     if (data == null)         node.Data = end;     else if (data.CompareTo(end) &lt; 0)         node.Data = end;     else         return false;      return true; }<\/code><\/pre>\n<p>\u041d\u043e \u0435\u0441\u0442\u044c \u043a\u0443\u0434\u0430 \u0431\u043e\u043b\u0435\u0435 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u043e\u0435 \u043c\u0435\u0441\u0442\u043e, \u0433\u0434\u0435 \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u044f\u0442 \u0438\u0437\u043c\u0435\u043d\u0435\u043d\u0438\u044f \u0443\u0437\u043b\u043e\u0432: \u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u043e\u0432\u043a\u0430. \u042f \u0434\u0430\u0432\u043d\u043e \u043d\u0435 \u043f\u0440\u043e\u0434\u0443\u043c\u044b\u0432\u0430\u043b \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u043d\u0430 \u0431\u0443\u043c\u0430\u0436\u043a\u0435, \u043d\u043e \u0432\u0440\u0430\u0449\u0435\u043d\u0438\u044f \u0432 \u043a\u0440\u0430\u0441\u043d\u043e-\u0447\u0451\u0440\u043d\u043e\u043c \u0434\u0435\u0440\u0435\u0432\u0435 \u0437\u0430\u0441\u0442\u0430\u0432\u0438\u043b\u0438 \u044d\u0442\u043e \u0441\u0434\u0435\u043b\u0430\u0442\u044c.<\/p>\n<p>\u041f\u0440\u043e\u0432\u0435\u0434\u044f \u043a\u0430\u043a\u043e\u0435-\u0442\u043e \u0432\u0440\u0435\u043c\u044f \u0437\u0430 \u0440\u0438\u0441\u043e\u0432\u0430\u043d\u0438\u0435\u043c \u043f\u0430\u043b\u043e\u0447\u0435\u043a \u0438 \u043a\u0440\u0443\u0436\u043e\u0447\u043a\u043e\u0432, \u044f \u043f\u0440\u0438\u0448\u0451\u043b \u043a \u043c\u0435\u0442\u043e\u0434\u0443 \u0432\u043d\u0443\u0442\u0440\u0438 <code>RedBlackTree&lt;&gt;<\/code>:<\/p>\n<pre><code class=\"cs\">protected virtual void OnRotated(     RedBlackTreeNode&lt;TKey, TValue&gt; bottomNode,     RedBlackTreeNode&lt;TKey, TValue&gt; topNode) { }<\/code><\/pre>\n<p>\u0415\u0433\u043e \u044f \u0432\u044b\u0437\u044b\u0432\u0430\u044e \u0432 \u0441\u0430\u043c\u043e\u043c\u00a0 \u043a\u043e\u043d\u0446\u0435 \u043c\u0435\u0442\u043e\u0434\u043e\u0432 <code>LeftRotate<\/code> \u0438 <code>RightRotate<\/code>:<\/p>\n<pre><code class=\"cs\">OnRotated(node, rightChild);<\/code><\/pre>\n<p>\u0438<\/p>\n<pre><code class=\"cs\">OnRotated(node, leftChild);<\/code><\/pre>\n<p>\u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0435\u043d\u043d\u043e.<\/p>\n<p>\u0420\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f <code>OnRotated<\/code> \u0432 \u0434\u0435\u0440\u0435\u0432\u0435 \u0438\u043d\u0442\u0435\u0440\u0432\u0430\u043b\u043e\u0432:<\/p>\n<pre><code class=\"cs\">protected override void OnRotated(     RedBlackTreeNode&lt;TKey, TValue&gt; bottomNode,     RedBlackTreeNode&lt;TKey, TValue&gt; topNode) {     base.OnRotated(bottomNode, topNode);      UpdateMax(bottomNode);      if (bottomNode.Data.CompareTo(topNode.Data) &gt; 0)         topNode.Data = bottomNode.Data; }<\/code><\/pre>\n<p>\u0421 \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u0435\u043c \u0434\u0430\u043d\u043d\u044b\u0445 \u0440\u0430\u0437\u043e\u0431\u0440\u0430\u043b\u0438\u0441\u044c, \u043e\u0441\u0442\u0430\u043b\u043e\u0441\u044c \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u0435. \u041f\u043e \u0430\u043d\u0430\u043b\u043e\u0433\u0438\u0438 \u0441 <code>OnValueAdded<\/code> \u043e\u0431\u044a\u044f\u0432\u0438\u043c \u0432 \u043a\u0440\u0430\u0441\u043d\u043e-\u0447\u0451\u0440\u043d\u043e\u043c \u0434\u0435\u0440\u0435\u0432\u0435 \u043c\u0435\u0442\u043e\u0434 <code>OnValueRemoved<\/code>:<\/p>\n<pre><code class=\"cs\">protected virtual void OnValueRemoved(     RedBlackTreeNode&lt;TKey, TValue&gt; node) { }<\/code><\/pre>\n<p>\u0412\u044b\u0437\u044b\u0432\u0430\u0435\u043c \u0437\u0434\u0435\u0441\u044c:<\/p>\n<pre><code class=\"cs\">node.Values.Remove(coordinate.NodeElement); if (node.Values.Count &gt; 0) {     OnValueRemoved(node);     return true; }<\/code><\/pre>\n<p>\u0420\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u0432 <code>IntervalTree&lt;&gt;<\/code>:<\/p>\n<pre><code class=\"cs\">protected override void OnValueRemoved(RedBlackTreeNode&lt;TKey, TValue&gt; node) {     base.OnValueRemoved(node);      if (UpdateMax(node))         UpdateMaxUp(node); }<\/code><\/pre>\n<p>\u041a\u0430\u043a \u0432\u044b \u043f\u043e\u043c\u043d\u0438\u0442\u0435, \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u0435 \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442 \u0441\u043c\u0435\u043d\u0443 \u043e\u0434\u043d\u043e\u0433\u043e \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u0430 \u043d\u0430 \u0434\u0440\u0443\u0433\u043e\u0435. \u041f\u043e\u0442\u0440\u0430\u0442\u0438\u0432 \u0435\u0449\u0451 \u043e\u0434\u043d\u0443 \u0441\u0442\u0440\u0430\u043d\u0438\u0446\u0443 \u0431\u043b\u043e\u043a\u043d\u043e\u0442\u0430 \u043d\u0430 \u043f\u043e\u043d\u0438\u043c\u0430\u043d\u0438\u0435, \u0447\u0442\u043e \u043f\u0440\u0438 \u044d\u0442\u043e\u043c \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u0442 \u0441 \u0434\u0435\u0440\u0435\u0432\u043e\u043c, \u0432 <code>RedBlackTree&lt;&gt;<\/code> \u043f\u043e\u044f\u0432\u0438\u043b\u0441\u044f \u043c\u0435\u0442\u043e\u0434 <code>OnTransplanted<\/code>:<\/p>\n<pre><code class=\"cs\">protected virtual void OnTransplanted(RedBlackTreeNode&lt;TKey, TValue&gt; node) { }<\/code><\/pre>\n<p>\u0412\u044b\u0437\u0432\u0430\u0442\u044c \u0435\u0433\u043e \u043d\u0443\u0436\u043d\u043e \u0432\u0441\u0435\u0433\u043e \u043e\u0434\u0438\u043d \u0440\u0430\u0437, \u0432\u043e\u0442 \u0442\u0443\u0442:<\/p>\n<pre><code class=\"cs\">OnTransplanted(nextNode);  if (!isNextNodeRed)     RemoveFixup(child);<\/code><\/pre>\n<p>\u0418\u043d\u0442\u0435\u0440\u0432\u0430\u043b\u044c\u043d\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e \u043f\u0440\u043e\u0441\u0442\u043e \u0437\u0430\u043f\u0443\u0441\u043a\u0430\u0435\u0442 \u043a\u0430\u0441\u043a\u0430\u0434 \u043e\u0431\u043d\u043e\u0432\u043b\u0435\u043d\u0438\u044f \u0433\u0440\u0430\u043d\u0438\u0446\u044b:<\/p>\n<pre><code class=\"cs\">protected override void OnTransplanted(RedBlackTreeNode&lt;TKey, TValue&gt; node) {     base.OnTransplanted(node);      UpdateMax(node);     UpdateMaxUp(node); }<\/code><\/pre>\n<p>\u041f\u0440\u043e \u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u043e\u0432\u043a\u0443 \u043f\u043e\u0441\u043b\u0435 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044f \u043c\u043e\u0436\u043d\u043e \u043d\u0435 \u0434\u0443\u043c\u0430\u0442\u044c: \u0437\u0438\u0436\u0434\u0435\u0442\u0441\u044f \u043e\u043d\u0430, \u043a\u0430\u043a \u0438 \u043f\u0440\u0438 \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u0438, \u043d\u0430 \u0432\u0440\u0430\u0449\u0435\u043d\u0438\u044f\u0445, \u0430 \u043e \u043d\u0438\u0445 \u043c\u044b \u0443\u0436\u0435 \u043f\u043e\u0437\u0430\u0431\u043e\u0442\u0438\u043b\u0438\u0441\u044c.<\/p>\n<p>\u0414\u0435\u0440\u0435\u0432\u043e \u0438\u043d\u0442\u0435\u0440\u0432\u0430\u043b\u043e\u0432 \u0433\u043e\u0442\u043e\u0432\u043e. \u041d\u0430 \u0441\u0430\u043c\u043e\u043c \u0434\u0435\u043b\u0435, \u0441\u0442\u0440\u043e\u0438\u0442\u044c \u0435\u0433\u043e \u043c\u043e\u0436\u043d\u043e \u043f\u043e-\u0440\u0430\u0437\u043d\u043e\u043c\u0443. \u041d\u043e \u0440\u0430\u0441\u0448\u0438\u0440\u0435\u043d\u0438\u0435 \u043a\u0440\u0430\u0441\u043d\u043e-\u0447\u0451\u0440\u043d\u043e\u0433\u043e, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u0443\u0436\u0435 \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u043d\u043e, \u0432\u0438\u0434\u0438\u0442\u0441\u044f \u043d\u0430\u0438\u0431\u043e\u043b\u0435\u0435 \u043f\u0440\u043e\u0441\u0442\u044b\u043c \u0441\u043f\u043e\u0441\u043e\u0431\u043e\u043c.<\/p>\n<p><a class=\"anchor\" name=\"conclusion\" id=\"conclusion\"><\/a><\/p>\n<h2>\u0417\u0430\u043a\u043b\u044e\u0447\u0435\u043d\u0438\u0435<\/h2>\n<p>\u041d\u0430\u0432\u0435\u0440\u043d\u043e\u0435, \u0432\u044b \u0437\u0430\u043c\u0435\u0442\u0438\u043b\u0438, \u0447\u0442\u043e \u043c\u043d\u043e\u0433\u0438\u0435 \u043c\u0435\u0442\u043e\u0434\u044b \u0432\u043d\u0443\u0442\u0440\u0438 <code>RedBlackTree&lt;T&gt;<\/code> \u043d\u0435 \u044f\u0432\u043b\u044f\u044e\u0442\u0441\u044f \u0441\u043f\u0435\u0446\u0438\u0444\u0438\u043a\u043e\u0439 \u043a\u0440\u0430\u0441\u043d\u043e-\u0447\u0451\u0440\u043d\u043e\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430. \u041e\u043d\u0438 \u043f\u0440\u0438\u043c\u0435\u043d\u0438\u043c\u044b \u043a \u043b\u044e\u0431\u043e\u043c\u0443 \u0431\u0438\u043d\u0430\u0440\u043d\u043e\u043c\u0443 \u0434\u0435\u0440\u0435\u0432\u0443 \u043f\u043e\u0438\u0441\u043a\u0430. \u0410\u0434\u0435\u043f\u0442\u044b \u043a\u0440\u0430\u0441\u0438\u0432\u043e\u0439 \u0430\u0440\u0445\u0438\u0442\u0435\u043a\u0442\u0443\u0440\u044b \u0441\u0434\u0435\u043b\u0430\u044e\u0442 \u043a\u043b\u0430\u0441\u0441 <code>BinaryTree&lt;&gt;<\/code>, \u043e\u0442 \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u0431\u0443\u0434\u0435\u0442 \u043d\u0430\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u044c\u0441\u044f <code>RedBlackTree&lt;&gt;<\/code>. \u042f \u0436\u0435 \u0441\u0447\u0438\u0442\u0430\u044e, \u0447\u0442\u043e \u0432 \u0441\u043b\u0443\u0447\u0430\u0435 \u0432\u043e\u0437\u043d\u0438\u043a\u043d\u043e\u0432\u0435\u043d\u0438\u044f \u0442\u0430\u043a\u043e\u0439 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e\u0441\u0442\u0438, \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u044d\u0442\u043e \u043d\u0435 \u0441\u043e\u0441\u0442\u0430\u0432\u0438\u0442 \u0442\u0440\u0443\u0434\u0430. \u0410 \u043f\u0440\u044f\u043c\u043e \u0441\u0435\u0439\u0447\u0430\u0441 \u0432\u0432\u043e\u0434\u0438\u0442\u044c \u043b\u0438\u0448\u043d\u0438\u0435 \u043a\u043b\u0430\u0441\u0441\u044b \u0441\u043c\u044b\u0441\u043b\u0430 \u043d\u0435\u0442.<\/p>\n<p>\u041a\u0430\u043a \u0431\u044b\u043b\u043e \u0441\u043a\u0430\u0437\u0430\u043d\u043e \u0440\u0430\u043d\u0435\u0435, \u043c\u043d\u0435 \u043d\u0435 \u0443\u0434\u0430\u043b\u043e\u0441\u044c \u043d\u0430\u0439\u0442\u0438 \u0434\u043e\u0441\u0442\u043e\u0439\u043d\u0443\u044e \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0443 \u0441 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0435\u0439 \u043a\u0440\u0430\u0441\u043d\u043e-\u0447\u0451\u0440\u043d\u043e\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430. \u0412\u043e\u0437\u043c\u043e\u0436\u043d\u043e, \u043a\u043e\u0434, \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u043d\u044b\u0439 \u0432 \u044d\u0442\u043e\u0439 \u0441\u0442\u0430\u0442\u044c\u0435 \u0437\u0430\u0436\u0436\u0451\u0442 \u0432 \u0432\u0430\u0441 \u0438\u0441\u043a\u0440\u0443 \u0434\u043b\u044f \u0435\u0451 \u0441\u043e\u0437\u0434\u0430\u043d\u0438\u044f. \u041d\u043e \u0435\u0441\u043b\u0438 \u0442\u0430\u043a\u043e\u0432\u0430\u044f \u0432\u0441\u0451 \u0436\u0435 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442, \u0431\u0443\u0434\u0443 \u0440\u0430\u0434 \u0443\u0437\u043d\u0430\u0442\u044c.<\/p>\n<p>\u041a\u0430\u043a \u0438 \u043e\u0431\u0435\u0449\u0430\u043b, \u0437\u0430\u043a\u043e\u043d\u0447\u0443 \u0441\u0442\u0430\u0442\u044c\u044e \u0441\u0441\u044b\u043b\u043a\u0430\u043c\u0438 \u043d\u0430 \u0444\u0430\u0439\u043b\u044b \u0441 \u0433\u043e\u0442\u043e\u0432\u044b\u043c \u043a\u043e\u0434\u043e\u043c:<\/p>\n<ul>\n<li>\n<p><a href=\"https:\/\/github.com\/melanchall\/drywetmidi\/blob\/develop\/DryWetMidi\/Common\/Collections\/RedBlackTree\/RedBlackTreeNode.cs\" rel=\"noopener noreferrer nofollow\">RedBlackTreeNode.cs<\/a><\/p>\n<\/li>\n<li>\n<p><a href=\"https:\/\/github.com\/melanchall\/drywetmidi\/blob\/develop\/DryWetMidi\/Common\/Collections\/RedBlackTree\/RedBlackTreeCoordinate.cs\" rel=\"noopener noreferrer nofollow\">RedBlackTreeCoordinate.cs<\/a><\/p>\n<\/li>\n<li>\n<p><a href=\"https:\/\/github.com\/melanchall\/drywetmidi\/blob\/develop\/DryWetMidi\/Common\/Collections\/RedBlackTree\/RedBlackTree.cs\" rel=\"noopener noreferrer nofollow\">RedBlackTree.cs<\/a><\/p>\n<\/li>\n<li>\n<p><a href=\"https:\/\/github.com\/melanchall\/drywetmidi\/blob\/develop\/DryWetMidi\/Common\/Collections\/IntervalTree\/IInterval.cs\" rel=\"noopener noreferrer nofollow\">IInterval.cs<\/a><\/p>\n<\/li>\n<li>\n<p><a href=\"https:\/\/github.com\/melanchall\/drywetmidi\/blob\/develop\/DryWetMidi\/Common\/Collections\/IntervalTree\/IntervalTree.cs\" rel=\"noopener noreferrer nofollow\">IntervalTree.cs<\/a><\/p>\n<\/li>\n<\/ul>\n<\/div>\n<\/div>\n<\/div>\n<p><!----><!----><\/div>\n<p><!----><!----><br \/> \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\/articles\/920390\/\"> https:\/\/habr.com\/ru\/articles\/920390\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<div><!--[--><!--]--><\/div>\n<div id=\"post-content-body\">\n<div>\n<div class=\"article-formatted-body article-formatted-body article-formatted-body_version-2\">\n<div xmlns=\"http:\/\/www.w3.org\/1999\/xhtml\">\n<figure class=\"full-width\"><\/figure>\n<p>\u0427\u0442\u043e \u043c\u043e\u0436\u0435\u0442 \u0437\u0430\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u043e\u0431\u0440\u0430\u0442\u0438\u0442\u044c \u0432\u043d\u0438\u043c\u0430\u043d\u0438\u0435 \u043d\u0430 <a href=\"https:\/\/en.wikipedia.org\/wiki\/Red%E2%80%93black_tree\" rel=\"noopener noreferrer nofollow\">\u043a\u0440\u0430\u0441\u043d\u043e-\u0447\u0451\u0440\u043d\u044b\u0435 \u0434\u0435\u0440\u0435\u0432\u044c\u044f<\/a>, \u0438 \u043a\u0430\u043a \u0438\u0445 \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u0442\u044c? \u0421\u0442\u0430\u0442\u044c\u044f \u043e\u0442\u0432\u0435\u0442\u0438\u0442 \u043d\u0430 \u043e\u0431\u0430 \u044d\u0442\u0438 \u0432\u043e\u043f\u0440\u043e\u0441\u0430. \u0411\u043e\u043d\u0443\u0441\u043e\u043c \u0431\u0443\u0434\u0435\u0442 \u043f\u043e\u043a\u0430\u0437\u0430\u043d\u043e, \u043a\u0430\u043a \u043d\u0430 \u043e\u0441\u043d\u043e\u0432\u0435 \u043a\u0440\u0430\u0441\u043d\u043e-\u0447\u0451\u0440\u043d\u043e\u0433\u043e \u0441\u043a\u043e\u043d\u0441\u0442\u0440\u0443\u0438\u0440\u043e\u0432\u0430\u0442\u044c <a href=\"https:\/\/en.wikipedia.org\/wiki\/Interval_tree\" rel=\"noopener noreferrer nofollow\">\u0434\u0435\u0440\u0435\u0432\u043e \u0438\u043d\u0442\u0435\u0440\u0432\u0430\u043b\u043e\u0432<\/a>.<\/p>\n<hr\/>\n<p>\u0412\u0430\u0436\u043d\u043e\u0435 \u0437\u0430\u043c\u0435\u0447\u0430\u043d\u0438\u0435: \u0441\u0442\u0430\u0442\u044c\u044f \u0444\u043e\u043a\u0443\u0441\u0438\u0440\u0443\u0435\u0442\u0441\u044f \u043d\u0430 \u043a\u043e\u0434\u0435. \u201c\u041e\u201d \u0431\u043e\u043b\u044c\u0448\u043e\u0435, \u0434\u0432\u043e\u0438\u0447\u043d\u044b\u0435 \u0434\u0435\u0440\u0435\u0432\u044c\u044f, \u0441\u0432\u044f\u0437\u043d\u044b\u0435 \u0441\u043f\u0438\u0441\u043a\u0438 \u2014 \u0432\u0441\u0451 \u044d\u0442\u043e \u043e\u0441\u0442\u0430\u043d\u0435\u0442\u0441\u044f \u0437\u0430 \u043a\u0430\u0434\u0440\u043e\u043c. \u0421\u0442\u0430\u0442\u044c\u0438 \u0446\u0435\u043d\u043d\u044b \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b\u044c\u043d\u043e\u0441\u0442\u044c\u044e \u043c\u0430\u0442\u0435\u0440\u0438\u0430\u043b\u0430, \u0430 \u043f\u0435\u0440\u0435\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u044b\u0435 \u0432\u0435\u0449\u0438 (\u0432\u043a\u043b\u044e\u0447\u0430\u044f \u043c\u0435\u0445\u0430\u043d\u0438\u043a\u0443 \u043a\u0440\u0430\u0441\u043d\u043e-\u0447\u0451\u0440\u043d\u044b\u0445 \u0434\u0435\u0440\u0435\u0432\u044c\u0435\u0432) \u043e\u0431\u0441\u0443\u0436\u0434\u0430\u043b\u0438\u0441\u044c \u0443\u0436\u0435 \u043c\u043d\u043e\u0433\u043e \u0440\u0430\u0437, \u0432 \u0442\u043e\u043c \u0447\u0438\u0441\u043b\u0435 \u0438 \u0437\u0434\u0435\u0441\u044c, \u043d\u0430 \u0425\u0430\u0431\u0440\u0435.<\/p>\n<p>\u0415\u0441\u043b\u0438 \u0436\u0430\u0436\u0434\u0430 \u0433\u043e\u0442\u043e\u0432\u044b\u0445 \u0440\u0435\u0448\u0435\u043d\u0438\u0439 \u0443 \u0432\u0430\u0441 \u0442\u0430\u043a \u0436\u0435 \u0441\u0438\u043b\u044c\u043d\u0430, \u043a\u0430\u043a \u0431\u044b\u043b\u0430 \u0443 \u043c\u0435\u043d\u044f \u043f\u043e\u043b\u0433\u043e\u0434\u0430 \u043d\u0430\u0437\u0430\u0434, \u043a\u043e\u0433\u0434\u0430 \u044f \u043d\u0430\u0447\u0438\u043d\u0430\u043b \u0440\u0430\u0437\u0431\u0438\u0440\u0430\u0442\u044c\u0441\u044f \u0441 \u0442\u0435\u043c\u043e\u0439, \u0442\u043e \u043c\u043e\u0436\u0435\u0442\u0435 \u0441\u0440\u0430\u0437\u0443 \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u0438\u0442\u044c \u043a \u0440\u0430\u0437\u0434\u0435\u043b\u0443 <a href=\"#construction\" rel=\"noopener noreferrer nofollow\">\u041f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u0435<\/a>. \u0418\u043b\u0438 \u0432\u043e\u043e\u0431\u0449\u0435 \u0432 <a href=\"#conclusion\" rel=\"noopener noreferrer nofollow\">\u043a\u043e\u043d\u0435\u0446 \u0441\u0442\u0430\u0442\u044c\u0438<\/a> \u043a \u0441\u0441\u044b\u043b\u043a\u0430\u043c \u043d\u0430 \u0444\u0430\u0439\u043b\u044b.<\/p>\n<h2>\u041e\u0433\u043b\u0430\u0432\u043b\u0435\u043d\u0438\u0435<\/h2>\n<ul>\n<li>\n<p><a href=\"#why\" rel=\"noopener noreferrer nofollow\">\u0417\u0430\u0447\u0435\u043c?<\/a><\/p>\n<\/li>\n<li>\n<p><a href=\"#construction\" rel=\"noopener noreferrer nofollow\">\u041f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u0435<\/a><\/p>\n<\/li>\n<li>\n<p><a href=\"#intervaltree\" rel=\"noopener noreferrer nofollow\">\u0414\u0435\u0440\u0435\u0432\u043e \u0438\u043d\u0442\u0435\u0440\u0432\u0430\u043b\u043e\u0432<\/a><\/p>\n<\/li>\n<li>\n<p><a href=\"#conclusion\" rel=\"noopener noreferrer nofollow\">\u0417\u0430\u043a\u043b\u044e\u0447\u0435\u043d\u0438\u0435<\/a><\/p>\n<\/li>\n<\/ul>\n<p><a class=\"anchor\" name=\"why\" id=\"why\"><\/a><\/p>\n<h2>\u0417\u0430\u0447\u0435\u043c?<\/h2>\n<p>\u041f\u0435\u0440\u0435\u0434 \u0442\u0435\u043c, \u043a\u0430\u043a \u043e\u043a\u0443\u043d\u0443\u0442\u044c\u0441\u044f \u0432 \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u043e\u043d\u043d\u0443\u044e \u0431\u043e\u0442\u0430\u043d\u0438\u043a\u0443, \u043e\u0442\u0432\u0435\u0447\u0443 \u043d\u0430 \u0432\u043e\u043f\u0440\u043e\u0441, \u0437\u0430\u0434\u0430\u043d\u043d\u044b\u0439 \u0432 \u043d\u0430\u0447\u0430\u043b\u0435 \u0441\u0442\u0430\u0442\u044c\u0438. \u0412\u043e\u0437\u043d\u0438\u043a\u043b\u0430 \u0437\u0430\u0434\u0430\u0447\u0430:<\/p>\n<ul>\n<li>\n<p>\u043d\u0443\u0436\u043d\u0430 \u0443\u043f\u043e\u0440\u044f\u0434\u043e\u0447\u0435\u043d\u043d\u0430\u044f (\u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u0430\u044f \u043f\u043e \u043d\u0435\u043a\u043e\u0435\u043c\u0443 \u0430\u0442\u0440\u0438\u0431\u0443\u0442\u0443) \u043a\u043e\u043b\u043b\u0435\u043a\u0446\u0438\u044f \u043e\u0431\u044a\u0435\u043a\u0442\u043e\u0432;<\/p>\n<\/li>\n<li>\n<p>\u043f\u043e\u0440\u044f\u0434\u043e\u043a \u043d\u0435 \u0434\u043e\u043b\u0436\u0435\u043d \u043d\u0430\u0440\u0443\u0448\u0430\u0442\u044c\u0441\u044f \u043f\u0440\u0438 \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u0438 \u0438 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u0438 \u0434\u0430\u043d\u043d\u044b\u0445;<\/p>\n<\/li>\n<li>\n<p>\u0443\u043a\u0430\u0437\u0430\u043d\u043d\u044b\u0435 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438, \u0430 \u0442\u0430\u043a\u0436\u0435 \u043f\u043e\u0438\u0441\u043a \u043e\u0431\u044a\u0435\u043a\u0442\u0430 \u0432 \u043a\u043e\u043b\u043b\u0435\u043a\u0446\u0438\u0438 \u0441\u043b\u0435\u0434\u0443\u0435\u0442 \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0442\u044c \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e \u0431\u044b\u0441\u0442\u0440\u043e.<\/p>\n<\/li>\n<\/ul>\n<p>\u041a\u0430\u043a \u0438 \u0443 \u043f\u0440\u043e\u0448\u043b\u044b\u0445 \u043c\u043e\u0438\u0445 \u0441\u0442\u0430\u0442\u0435\u0439, \u0443 \u044d\u0442\u043e\u0439 \u043d\u043e\u0433\u0438 \u0440\u0430\u0441\u0442\u0443\u0442 \u0438\u0437 \u0440\u0430\u0431\u043e\u0442\u044b \u043d\u0430\u0434 \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u043e\u0439 <a href=\"https:\/\/github.com\/melanchall\/drywetmidi\" rel=\"noopener noreferrer nofollow\">DryWetMIDI<\/a>. \u041d\u0435\u0434\u0430\u0432\u043d\u0438\u0439 <a href=\"https:\/\/github.com\/melanchall\/drywetmidi\/releases\/tag\/v8.0.0\" rel=\"noopener noreferrer nofollow\">\u0440\u0435\u043b\u0438\u0437<\/a> \u043f\u043e\u0437\u0432\u043e\u043b\u0438\u043b \u0432\u043d\u043e\u0441\u0438\u0442\u044c \u0438\u0437\u043c\u0435\u043d\u0435\u043d\u0438\u044f \u0432 \u0432\u043e\u0441\u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u043c\u044b\u0435 \u043e\u0431\u044a\u0435\u043a\u0442\u044b (MIDI-\u0441\u043e\u0431\u044b\u0442\u0438\u044f, \u043d\u043e\u0442\u044b \u0438 \u0442.\u043f.) \u043d\u0430 \u043b\u0435\u0442\u0443. \u0415\u0441\u043b\u0438 \u043a\u0440\u0430\u0442\u043a\u043e, \u0442\u0435\u043f\u0435\u0440\u044c \u043c\u043e\u0436\u043d\u043e \u0443\u0434\u0430\u043b\u044f\u0442\u044c, \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0442\u044c \u0438 \u043c\u0435\u043d\u044f\u0442\u044c \u0434\u0430\u043d\u043d\u044b\u0435 \u0431\u0435\u0437 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e\u0441\u0442\u0438 \u043f\u0435\u0440\u0435\u0441\u043e\u0437\u0434\u0430\u0432\u0430\u0442\u044c \u044d\u043a\u0437\u0435\u043c\u043f\u043b\u044f\u0440 \u043a\u043b\u0430\u0441\u0441\u0430 <a href=\"https:\/\/melanchall.github.io\/drywetmidi\/api\/Melanchall.DryWetMidi.Multimedia.Playback.html\" rel=\"noopener noreferrer nofollow\">Playback<\/a>. \u0423\u0447\u0438\u0442\u044b\u0432\u0430\u044f, \u0447\u0442\u043e \u043e\u0431\u044a\u0435\u043a\u0442\u044b \u0432\u043d\u0443\u0442\u0440\u0438 \u0434\u043e\u043b\u0436\u043d\u044b \u0438\u0434\u0442\u0438 \u0432 \u0445\u0440\u043e\u043d\u043e\u043b\u043e\u0433\u0438\u0447\u0435\u0441\u043a\u043e\u043c \u043f\u043e\u0440\u044f\u0434\u043a\u0435, \u043f\u0440\u0438\u0445\u043e\u0434\u0438\u043c \u043a \u043f\u043e\u043a\u0430\u0437\u0430\u043d\u043d\u043e\u0439 \u0432\u044b\u0448\u0435 \u0437\u0430\u0434\u0430\u0447\u0435.<\/p>\n<p>\u0411\u0435\u0441\u0446\u0435\u043d\u043d\u044b\u0439 \u043e\u043f\u044b\u0442 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0438\u0445 \u043f\u043e\u043a\u043e\u043b\u0435\u043d\u0438\u0439 \u043f\u043e\u0434\u0441\u043a\u0430\u0437\u044b\u0432\u0430\u0435\u0442 \u2014 \u043d\u0443\u0436\u043d\u043e \u0441\u0430\u043c\u043e\u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u0443\u044e\u0449\u0435\u0435\u0441\u044f \u0431\u0438\u043d\u0430\u0440\u043d\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e \u043f\u043e\u0438\u0441\u043a\u0430 (<a href=\"https:\/\/en.wikipedia.org\/wiki\/Self-balancing_binary_search_tree\" rel=\"noopener noreferrer nofollow\">self-balancing binary search tree<\/a>). \u0418\u043b\u0438 \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u0435, \u043a\u043e\u043c\u0443 \u043a\u0430\u043a \u0431\u043e\u043b\u044c\u0448\u0435 \u043d\u0440\u0430\u0432\u0438\u0442\u0441\u044f. \u0421\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u044f, \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044f \u0438 \u043f\u043e\u0438\u0441\u043a\u0430 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u0432 \u0442\u0430\u043a\u043e\u0439 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0435 <code>O(logN)<\/code>, \u043a\u0430\u043a \u0432 \u0441\u0440\u0435\u0434\u043d\u0435\u043c, \u0442\u0430\u043a \u0438 \u0432 \u0445\u0443\u0434\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u044f\u0445. \u0427\u0435\u0433\u043e \u043d\u0435 \u0441\u043a\u0430\u0436\u0435\u0448\u044c \u043f\u0440\u043e \u043e\u0431\u044b\u0447\u043d\u043e\u0435 BST (<a href=\"https:\/\/en.wikipedia.org\/wiki\/Binary_search_tree\" rel=\"noopener noreferrer nofollow\">binary search tree<\/a>), \u043f\u043e\u0441\u043b\u0435 \u0441\u0435\u0440\u0438\u0438 \u043c\u043e\u0434\u0438\u0444\u0438\u043a\u0430\u0446\u0438\u0439 \u0432 \u043a\u043e\u0442\u043e\u0440\u043e\u043c \u043b\u0435\u0433\u043a\u043e \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0442\u0430\u043a\u0443\u044e \u0433\u0438\u0440\u043b\u044f\u043d\u0434\u0443:<\/p>\n<figure class=\"full-width\"><\/figure>\n<p>\u0421\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u0431\u0443\u0434\u0435\u0442, \u043e\u0447\u0435\u0432\u0438\u0434\u043d\u043e, \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0439 (\u0442.\u0435. <code>O(N)<\/code>). \u041f\u043e\u0434\u0434\u0435\u0440\u0436\u0430\u043d\u0438\u0435 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0439 \u0432\u044b\u0441\u043e\u0442\u044b \u0434\u0435\u0440\u0435\u0432\u0430 (\u0447\u0442\u043e \u0438 \u0434\u0430\u0451\u0442 \u0437\u0430\u0432\u0435\u0442\u043d\u044b\u0439 \u043b\u043e\u0433\u0430\u0440\u0438\u0444\u043c) \u2014 \u0437\u0430\u0434\u0430\u0447\u0430 \u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u043e\u0432\u043a\u0438, \u0441\u0443\u0442\u044c \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u0432 \u043f\u0435\u0440\u0435\u0443\u043f\u043e\u0440\u044f\u0434\u043e\u0447\u0438\u0432\u0430\u043d\u0438\u0438 \u0443\u0437\u043b\u043e\u0432 \u0431\u0435\u0437 \u043d\u0430\u0440\u0443\u0448\u0435\u043d\u0438\u044f \u0441\u0432\u043e\u0439\u0441\u0442\u0432 BST.<\/p>\n<p>\u0418 \u0442\u0430\u043a, \u0441\u043e \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u043e\u0439 \u0434\u0430\u043d\u043d\u044b\u0445 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u043b\u0438\u0441\u044c. \u041d\u043e \u0441\u0430\u043c\u043e\u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u0443\u044e\u0449\u0438\u0435\u0441\u044f \u0431\u0438\u043d\u0430\u0440\u043d\u044b\u0435 \u0434\u0435\u0440\u0435\u0432\u044c\u044f \u043f\u043e\u0438\u0441\u043a\u0430 \u0431\u044b\u0432\u0430\u044e\u0442 \u0440\u0430\u0437\u043d\u044b\u043c\u0438. \u041d\u0430\u0438\u0431\u043e\u043b\u0435\u0435 \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u044b <a href=\"https:\/\/en.wikipedia.org\/wiki\/AVL_tree\" rel=\"noopener noreferrer nofollow\">AVL-\u0434\u0435\u0440\u0435\u0432\u043e<\/a> \u0438 \u0433\u0432\u043e\u0437\u0434\u044c \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u044b \u2014 <a href=\"https:\/\/en.wikipedia.org\/wiki\/Red%E2%80%93black_tree\" rel=\"noopener noreferrer nofollow\">\u043a\u0440\u0430\u0441\u043d\u043e-\u0447\u0451\u0440\u043d\u043e\u0435<\/a> (red-black tree, RBT). \u041d\u0430 \u044d\u0442\u043e\u043c \u043c\u0435\u0441\u0442\u0435 \u044f \u0434\u043e\u043b\u0436\u0435\u043d \u0431\u044b\u043b \u0441\u043a\u0430\u0437\u0430\u0442\u044c \u043e \u043f\u0440\u043e\u0432\u0435\u0434\u0451\u043d\u043d\u043e\u043c \u0438\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u043d\u0438\u0438 \u043f\u043b\u044e\u0441\u043e\u0432 \u0438 \u043c\u0438\u043d\u0443\u0441\u043e\u0432 \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0438\u0437 \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u043e\u0432, \u043d\u043e \u0447\u0442\u043e-\u0442\u043e \u043f\u043e\u0448\u043b\u043e \u043d\u0435 \u0442\u0430\u043a. \u041f\u0440\u043e \u043a\u0440\u0430\u0441\u043d\u043e-\u0447\u0451\u0440\u043d\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e \u0438 \u0435\u0433\u043e \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u0430 \u044f \u0443\u0436\u0435 \u0437\u043d\u0430\u043b, \u0430 \u043f\u043e\u0442\u043e\u043c\u0443 \u0432\u044b\u0431\u043e\u0440 \u043f\u0430\u043b \u043d\u0430 \u043d\u0435\u0433\u043e. \u041f\u0440\u043e\u0444\u0435\u0441\u0441\u0438\u043e\u043d\u0430\u043b\u044c\u043d\u043e, \u043d\u0435 \u0442\u0430\u043a \u043b\u0438?<\/p>\n<p>\u041d\u043e \u043f\u0438\u0441\u0430\u0442\u044c \u0441\u0442\u0430\u0442\u044c\u0438 \u044d\u0442\u043e \u043d\u0435 \u0442\u043e\u043b\u044c\u043a\u043e \u0434\u0435\u043b\u0438\u0442\u044c\u0441\u044f \u0437\u043d\u0430\u043d\u0438\u044f\u043c\u0438. \u0412\u043e \u0432\u0440\u0435\u043c\u044f \u0440\u0430\u0431\u043e\u0442\u044b \u043d\u0430\u0434 \u0442\u0435\u043a\u0441\u0442\u043e\u043c \u0432\u043e\u0437\u043d\u0438\u043a\u0430\u0435\u0442 \u0436\u0435\u043b\u0430\u043d\u0438\u0435 \u0433\u043b\u0443\u0431\u0436\u0435 \u0440\u0430\u0437\u043e\u0431\u0440\u0430\u0442\u044c\u0441\u044f \u0432 \u0442\u0435\u043c\u0435. \u0411\u044b\u043b\u043e \u0431\u044b \u0441\u043e\u0432\u0441\u0435\u043c \u0433\u043b\u0443\u043f\u043e \u0434\u0430\u0436\u0435 \u0441\u0435\u0439\u0447\u0430\u0441 \u043d\u0435 \u0437\u0430\u0434\u0430\u0442\u044c\u0441\u044f \u0432\u043e\u043f\u0440\u043e\u0441\u043e\u043c, \u043a\u0430\u043a\u0430\u044f \u0436\u0435 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u0434\u0430\u043d\u043d\u044b\u0445 \u043b\u0443\u0447\u0448\u0435. \u041a\u0440\u0430\u0442\u043a\u0438\u0439 \u043f\u0435\u0440\u0435\u0441\u043a\u0430\u0437 \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u0445 \u043c\u0430\u0442\u0435\u0440\u0438\u0430\u043b\u043e\u0432 \u0442\u0430\u043a\u043e\u0432: \u0432 \u0446\u0435\u043b\u043e\u043c, \u043e\u043d\u0438 \u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u044b. \u0412 \u043a\u043e\u043d\u0446\u0435 \u043a\u043e\u043d\u0446\u043e\u0432, \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0443 \u043e\u0431\u043e\u0438\u0445 <code>O(logN)<\/code> \u0434\u043b\u044f \u0432\u0441\u0435\u0445 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439. \u041d\u044e\u0430\u043d\u0441\u044b, \u043a\u043e\u043d\u0435\u0447\u043d\u043e, \u043f\u0440\u0438\u0441\u0443\u0442\u0441\u0442\u0432\u0443\u044e\u0442:<\/p>\n<ul>\n<li>\n<p>AVL \u0447\u0443\u0442\u044c \u0431\u044b\u0441\u0442\u0440\u0435\u0435 \u043f\u0440\u0438 \u043f\u043e\u0438\u0441\u043a\u0435 \u0434\u0430\u043d\u043d\u044b\u0445 \u0432\u0432\u0438\u0434\u0443 <a href=\"https:\/\/en.wikipedia.org\/wiki\/AVL_tree#Comparison_to_other_structures\" rel=\"noopener noreferrer nofollow\">\u043c\u0435\u043d\u044c\u0448\u0435\u0439 \u0432\u044b\u0441\u043e\u0442\u044b<\/a> \u0434\u0435\u0440\u0435\u0432\u0430;<\/p>\n<\/li>\n<li>\n<p>RBT \u0432\u044b\u0438\u0433\u0440\u044b\u0432\u0430\u0435\u0442 \u0432 \u0441\u043a\u043e\u0440\u043e\u0441\u0442\u0438 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044f \u0438\u0437-\u0437\u0430 \u043c\u0435\u043d\u044c\u0448\u0435\u0433\u043e \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0430 \u0432\u0440\u0430\u0449\u0435\u043d\u0438\u0439 \u043f\u0440\u0438 \u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u043e\u0432\u043a\u0435 (AVL-\u0434\u0435\u0440\u0435\u0432\u0443 \u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f <code>O(logN)<\/code> \u0442\u0430\u043a\u043e\u0432\u044b\u0445 \u0432 \u0445\u0443\u0434\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u043f\u043e \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044e \u0441 <code>O(1)<\/code> \u0443 \u043a\u0440\u0430\u0441\u043d\u043e-\u0447\u0451\u0440\u043d\u043e\u0433\u043e).<\/p>\n<\/li>\n<\/ul>\n<p>\u041c\u043d\u0435 \u043f\u043e\u0432\u0435\u0437\u043b\u043e, \u043f\u043e\u0442\u043e\u043c\u0443 \u0447\u0442\u043e \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u0438\u0437\u043c\u0435\u043d\u0435\u043d\u0438\u044f \u0434\u0435\u0440\u0435\u0432\u0430 \u0432 \u043c\u043e\u0451\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u0432\u0430\u0436\u043d\u0435\u0435. \u041f\u043e\u0438\u0441\u043a \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u0442 \u043d\u0435\u0447\u0430\u0441\u0442\u043e: \u043f\u0440\u0438 <a href=\"https:\/\/melanchall.github.io\/drywetmidi\/api\/Melanchall.DryWetMidi.Multimedia.Playback.html#Melanchall_DryWetMidi_Multimedia_Playback_MoveToTime_Melanchall_DryWetMidi_Interaction_ITimeSpan_\" rel=\"noopener noreferrer nofollow\">\u043f\u0440\u044b\u0436\u043a\u0430\u0445<\/a> \u043f\u043e \u0442\u0430\u0439\u043c\u043b\u0430\u0439\u043d\u0443 \u0432\u043e\u0441\u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u043c\u044b\u0445 \u0434\u0430\u043d\u043d\u044b\u0445. \u0412 \u044d\u0442\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435, \u043a\u043e\u043d\u0435\u0447\u043d\u043e, \u043f\u043e\u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f \u043d\u0430\u0439\u0442\u0438 \u0441\u043e\u0431\u044b\u0442\u0438\u0435, \u0441 \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u0434\u043e\u043b\u0436\u043d\u043e \u043d\u0430\u0447\u0430\u0442\u044c\u0441\u044f \u043f\u0440\u043e\u0438\u0433\u0440\u044b\u0432\u0430\u043d\u0438\u0435 \u0432 \u043d\u043e\u0432\u043e\u0439 \u043f\u043e\u0437\u0438\u0446\u0438\u0438.<\/p>\n<p>\u0421\u0442\u0430\u0442\u044c\u044f \u043f\u0440\u0438\u0437\u0432\u0430\u043d\u0430 \u0434\u0430\u0442\u044c \u0438\u0441\u0447\u0435\u0440\u043f\u044b\u0432\u0430\u044e\u0449\u0438\u0435 \u043b\u0438\u0441\u0442\u0438\u043d\u0433\u0438 \u043a\u043e\u0434\u0430 \u0441 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0435\u0439 \u043a\u0440\u0430\u0441\u043d\u043e-\u0447\u0451\u0440\u043d\u043e\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430, \u043a\u0430\u043a \u043e\u0441\u043d\u043e\u0432\u043d\u044b\u0445 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439, \u0442\u0430\u043a \u0438 \u043f\u043e\u043b\u0435\u0437\u043d\u044b\u0445 \u0432\u0441\u043f\u043e\u043c\u043e\u0433\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0445. \u0418 \u0441\u043e\u0432\u0441\u0435\u043c \u0441\u043a\u043e\u0440\u043e \u0432\u044b \u0443\u0432\u0438\u0434\u0438\u0442\u0435 \u044d\u0442\u0438 \u043f\u043e\u043b\u044f \u043c\u043e\u043d\u043e\u0448\u0438\u0440\u0438\u043d\u043d\u043e\u0433\u043e \u0442\u0435\u043a\u0441\u0442\u0430.<\/p>\n<p><strong>\u201c\u0410 \u043f\u043e\u0447\u0435\u043c\u0443 \u0431\u044b \u043d\u0435 \u0432\u0437\u044f\u0442\u044c \u0443\u0436\u0435 \u0433\u043e\u0442\u043e\u0432\u044b\u0439 \u043a\u043e\u0434 \u0438\u0437 \u0418\u043d\u0442\u0435\u0440\u043d\u0435\u0442\u0430?\u201d<\/strong> \u2014 \u043c\u043e\u0436\u0435\u0442 \u0432\u043e\u0437\u043d\u0438\u043a\u043d\u0443\u0442\u044c \u0432\u043e\u043f\u0440\u043e\u0441. \u041f\u0440\u0438\u0437\u043d\u0430\u044e\u0441\u044c, \u0443 \u043c\u0435\u043d\u044f, \u043a\u0430\u043a \u0442\u0438\u043f\u0438\u0447\u043d\u043e\u0433\u043e \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u0442\u0435\u043b\u044f \u043f\u0440\u043e\u0444\u0435\u0441\u0441\u0438\u0438, \u044d\u0442\u043e \u0431\u044b\u043b\u043e \u043f\u0435\u0440\u0432\u044b\u043c \u0436\u0435\u043b\u0430\u043d\u0438\u0435\u043c. \u041d\u043e \u0441\u043a\u0430\u0437\u0430\u0442\u044c \u043b\u0435\u0433\u0447\u0435, \u0447\u0435\u043c \u0441\u0434\u0435\u043b\u0430\u0442\u044c. \u0420\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u044b \u043f\u043e\u0438\u0441\u043a\u0430 \u043f\u043e \u0444\u0440\u0430\u0437\u0435 <em>\u201cred black tree c#\u201d<\/em>:<\/p>\n<ul>\n<li>\n<p><a href=\"https:\/\/gist.github.com\/JamesRandall\/33b6102e20bdf3ba6a027e6481f92242\" rel=\"noopener noreferrer nofollow\">Red-Black Tree Implementation in C#<\/a>. \u041d\u0435\u0442 \u043c\u0435\u0442\u043e\u0434\u0430 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044f \u0434\u0430\u043d\u043d\u044b\u0445. \u041a\u0440\u043e\u043c\u0435 \u0442\u043e\u0433\u043e, \u0432 \u043a\u043e\u0434\u0435 \u043d\u0430\u0439\u0434\u0435\u043d \u0431\u0430\u0433 (\u0441\u043c. \u043a\u043e\u043c\u043c\u0435\u043d\u0442\u0430\u0440\u0438\u0438).<\/p>\n<\/li>\n<li>\n<p><a href=\"https:\/\/www.c-sharpcorner.com\/article\/working-with-red-black-trees-in-c-sharp\/\" rel=\"noopener noreferrer nofollow\">Working With Red-Black Trees In C#<\/a>. \u0418 \u0441\u043d\u043e\u0432\u0430 \u043d\u0435\u0442 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044f.<\/p>\n<\/li>\n<li>\n<p><a href=\"https:\/\/www.jot.fm\/issues\/issue_2005_03\/column6\/\" rel=\"noopener noreferrer nofollow\">Generic Red-Black Tree and its C# Implementation<\/a>. \u0418\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d \u043d\u043e\u0432\u0430\u0442\u043e\u0440\u0441\u043a\u0438\u0439 \u043c\u0435\u0442\u043e\u0434 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u043a\u043e\u0434\u0430: \u043a\u0430\u0440\u0442\u0438\u043d\u043a\u0430\u043c\u0438.<\/p>\n<\/li>\n<li>\n<p><a href=\"https:\/\/dzone.com\/articles\/red-black-trees-in-c-a-guide-to-efficient-self-bal\" rel=\"noopener noreferrer nofollow\">Red-Black Trees in C#<\/a>. \u041a\u043b\u044e\u0447 \u0438 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u043e\u0434\u0438\u043d \u0438 \u0442\u043e\u0442 \u0436\u0435 \u043e\u0431\u044a\u0435\u043a\u0442. \u042d\u0442\u043e \u043d\u0435\u0432\u0435\u0440\u043d\u043e, \u0440\u0430\u0437\u0443\u043c\u0435\u0435\u0442\u0441\u044f.<\/p>\n<\/li>\n<li>\n<p><a href=\"https:\/\/www.codeproject.com\/Articles\/8287\/Red-Black-Trees-in-C-\" rel=\"noopener noreferrer nofollow\">Red-Black Trees in C#<\/a> (\u0442\u043e \u0436\u0435 \u043d\u0430\u0437\u0432\u0430\u043d\u0438\u0435, \u043d\u043e \u0434\u0440\u0443\u0433\u0430\u044f \u0441\u0442\u0430\u0442\u044c\u044f). \u041a\u043b\u044e\u0447 \u043f\u0440\u043e\u0441\u0442\u043e <code>IComparable<\/code>, \u0430 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u2014 <code>object<\/code>. \u0422\u043e \u0435\u0441\u0442\u044c, \u043d\u0435 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044e\u0442\u0441\u044f \u0434\u0436\u0435\u043d\u0435\u0440\u0438\u043a\u0438.<\/p>\n<\/li>\n<\/ul>\n<p><strong>\u201c\u041d\u043e \u043d\u0430\u0432\u0435\u0440\u043d\u044f\u043a\u0430 \u0436\u0435 \u0435\u0441\u0442\u044c \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0438 \u0441 \u0433\u043e\u0442\u043e\u0432\u044b\u043c\u0438 \u043a\u043b\u0430\u0441\u0441\u0430\u043c\u0438?\u201d<\/strong> \u2014 \u0441\u043d\u043e\u0432\u0430 \u0441\u043f\u0440\u043e\u0441\u0438\u0442\u0435 \u0432\u044b. \u041e\u0442\u0432\u0435\u0447\u0430\u044e:<\/p>\n<ol>\n<li>\n<p>\u0412\u043e\u0437\u043c\u043e\u0436\u043d\u043e, \u043c\u043e\u0438 \u043d\u0430\u0432\u044b\u043a\u0438 \u043f\u043e\u0438\u0441\u043a\u0430 \u043f\u043b\u043e\u0445\u0438, \u043d\u043e \u044f \u043d\u0435 \u043e\u0431\u043d\u0430\u0440\u0443\u0436\u0438\u043b \u0437\u0430\u0441\u043b\u0443\u0436\u0438\u0432\u0430\u044e\u0449\u0443\u044e \u0434\u043e\u0432\u0435\u0440\u0438\u044f \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0443 \u0432 NuGet, \u0433\u0434\u0435 \u043a\u0440\u0430\u0441\u043d\u043e-\u0447\u0451\u0440\u043d\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e \u0443\u0434\u043e\u0432\u043b\u0435\u0442\u0432\u043e\u0440\u044f\u043b\u043e \u0431\u044b \u043c\u043e\u0438\u043c \u0442\u0440\u0435\u0431\u043e\u0432\u0430\u043d\u0438\u044f\u043c (\u0441\u043c. \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0439 \u0440\u0430\u0437\u0434\u0435\u043b).<\/p>\n<\/li>\n<li>\n<p>\u0412 \u0441\u0432\u043e\u0451\u043c \u043f\u0440\u043e\u0435\u043a\u0442\u0435 \u044f \u043d\u0430\u043c\u0435\u0440\u0435\u043d\u043d\u043e \u0438\u0437\u0431\u0435\u0433\u0430\u044e \u0441\u0442\u043e\u0440\u043e\u043d\u043d\u0438\u0445 \u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u0435\u0439. \u0422\u044f\u043d\u0443\u0442\u044c \u0446\u0435\u043b\u0443\u044e \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0443 \u0440\u0430\u0434\u0438 \u043e\u0434\u043d\u043e\u0433\u043e \u043a\u043b\u0430\u0441\u0441\u0430 \u0438\u043b\u0438 \u043c\u0435\u0442\u043e\u0434\u0430 \u043d\u0435 \u0432\u0441\u0435\u0433\u0434\u0430 \u0440\u0430\u0437\u0443\u043c\u043d\u043e.<\/p>\n<\/li>\n<li>\n<p>\u041c\u043d\u0435 \u0442\u0440\u0435\u0431\u043e\u0432\u0430\u043b\u043e\u0441\u044c \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u0442\u044c \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u0435 \u043c\u0435\u0442\u043e\u0434\u044b, \u0442\u0440\u0435\u0431\u0443\u044e\u0449\u0438\u0435 \u0434\u043e\u0441\u0442\u0443\u043f\u0430 \u043a\u043e \u0432\u043d\u0443\u0442\u0440\u0435\u043d\u043d\u043e\u0441\u0442\u044f\u043c \u0434\u0435\u0440\u0435\u0432\u0430.<\/p>\n<\/li>\n<\/ol>\n<p><a class=\"anchor\" name=\"construction\" id=\"construction\"><\/a><\/p>\n<h2>\u041f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u0435<\/h2>\n<p>\u041a\u0430\u043a \u0432 \u043c\u043e\u0451\u043c \u043f\u043e\u043d\u0438\u043c\u0430\u043d\u0438\u0438 \u0434\u043e\u043b\u0436\u0435\u043d \u0432\u044b\u0433\u043b\u044f\u0434\u0435\u0442\u044c \u043a\u043b\u0430\u0441\u0441, \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u044f\u044e\u0449\u0438\u0439 \u043a\u0440\u0430\u0441\u043d\u043e-\u0447\u0451\u0440\u043d\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e:<\/p>\n<ol>\n<li>\n<p><strong>\u041a\u043b\u044e\u0447 \u0438 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 <\/strong>\u2014<strong> \u0440\u0430\u0437\u043d\u044b\u0435 \u0441\u0443\u0449\u043d\u043e\u0441\u0442\u0438<\/strong>. \u0415\u0441\u043b\u0438 \u0432 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f \u0447\u0442\u043e-\u0442\u043e \u0441\u043b\u043e\u0436\u043d\u0435\u0435 <code>int<\/code>, \u0442\u043e \u043f\u043e\u0447\u0442\u0438 \u043d\u0430\u0432\u0435\u0440\u043d\u044f\u043a\u0430 \u0441\u0430\u043c\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u043d\u0435 \u0431\u0443\u0434\u0435\u0442 \u043a\u043b\u044e\u0447\u043e\u043c.<\/p>\n<\/li>\n<li>\n<p><strong>\u041a\u043b\u0430\u0441\u0441 \u0434\u043e\u043b\u0436\u0435\u043d \u0431\u044b\u0442\u044c \u043e\u0431\u043e\u0431\u0449\u0451\u043d\u043d\u044b\u043c<\/strong> (\u0434\u0436\u0435\u043d\u0435\u0440\u0438\u043a\u043e\u043c). \u041d\u0435 \u043d\u0443\u0436\u043d\u043e \u0441\u0442\u0440\u043e\u0438\u0442\u044c \u0434\u043e\u0433\u0430\u0434\u043e\u043a \u043f\u043e \u043f\u043e\u0432\u043e\u0434\u0443 \u043a\u043b\u044e\u0447\u0430 \u0438 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f, \u0438\u043b\u0438 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0432\u0441\u0435\u044f\u0434\u043d\u044b\u0439 <code>object<\/code> (\u0432\u0440\u044f\u0434 \u043b\u0438 \u0432\u0430\u043c \u043d\u0443\u0436\u0435\u043d \u0431\u043e\u043a\u0441\u0438\u043d\u0433).<\/p>\n<\/li>\n<li>\n<p><strong>\u041a\u043b\u044e\u0447\u0438 \u043c\u043e\u0433\u0443\u0442 \u043f\u043e\u0432\u0442\u043e\u0440\u044f\u0442\u044c\u0441\u044f<\/strong>. \u041f\u0440\u0438\u043c\u0435\u0440: \u0433\u0440\u0443\u043f\u043f\u0430 \u043d\u043e\u0442 \u0432 MIDI-\u0444\u0430\u0439\u043b\u0435, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0441\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u044e\u0442 \u0430\u043a\u043a\u043e\u0440\u0434. \u0412\u044b\u0445\u043e\u0434\u0438\u0442, \u0447\u0442\u043e \u0441\u043e\u0431\u044b\u0442\u0438\u044f \u0441\u0442\u0430\u0440\u0442\u0430 \u0442\u0430\u043a\u0438\u0445 \u043d\u043e\u0442 (= \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f) \u0438\u043c\u0435\u044e\u0442 \u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u043e\u0435 \u0432\u0440\u0435\u043c\u044f (= \u043a\u043b\u044e\u0447).<\/p>\n<\/li>\n<\/ol>\n<p>\u041f\u043e\u0441\u043b\u0435\u0434\u043d\u0438\u0439 \u043f\u0443\u043d\u043a\u0442 \u043d\u0430\u0438\u0431\u043e\u043b\u0435\u0435 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u0435\u043d, \u0438\u0431\u043e \u0432\u043b\u0438\u044f\u0435\u0442 \u043d\u0430 \u0444\u0438\u043d\u0430\u043b\u044c\u043d\u0443\u044e \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0443 \u0434\u0435\u0440\u0435\u0432\u0430. \u0418\u0437\u043d\u0430\u0447\u0430\u043b\u044c\u043d\u043e \u044f \u0440\u0435\u0448\u0438\u043b \u043d\u0435 \u043c\u0443\u0434\u0440\u0438\u0442\u044c: \u043f\u0443\u0441\u0442\u044c \u0443\u0437\u043b\u044b \u0441 \u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u044b\u043c\u0438 \u043a\u043b\u044e\u0447\u0430\u043c\u0438 \u0432\u0441\u0435\u0433\u0434\u0430 \u0438\u0434\u0443\u0442 \u0432\u043f\u0440\u0430\u0432\u043e. \u041f\u0440\u043e\u0442\u0438\u0432\u043e\u0440\u0435\u0447\u0438\u0435 \u2014 \u0441\u043b\u043e\u0432\u043e, \u043f\u0440\u0438\u0445\u043e\u0434\u044f\u0449\u0435\u0435 \u043c\u043d\u0435 \u043d\u0430 \u0443\u043c \u0441\u0435\u0439\u0447\u0430\u0441. \u0412\u0435\u0434\u044c \u043f\u043e \u0442\u0430\u043a\u043e\u0439 \u043b\u043e\u0433\u0438\u043a\u0435 \u0434\u0435\u0440\u0435\u0432\u043e \u0438\u0437 \u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u044b\u0445 \u043e\u0431\u044a\u0435\u043a\u0442\u043e\u0432 \u0431\u0443\u0434\u0435\u0442 \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0442\u044c \u0442\u043e\u043b\u044c\u043a\u043e \u043f\u0440\u0430\u0432\u044b\u0435 \u0443\u0437\u043b\u044b, \u0447\u0442\u043e \u043c\u0435\u043d\u044f\u0435\u0442 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u0432 \u0441\u0442\u043e\u0440\u043e\u043d\u0443 \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0439. \u0415\u0441\u043b\u0438 \u0436\u0435 \u043f\u0440\u043e\u0432\u0435\u0441\u0442\u0438 \u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u043e\u0432\u043a\u0443, \u0442\u043e \u043d\u0430\u0440\u0443\u0448\u0438\u0442\u0441\u044f \u043f\u0440\u0438\u043d\u0446\u0438\u043f \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u044f.<\/p>\n<p>\u0421\u043f\u0440\u0430\u0432\u0435\u0434\u043b\u0438\u0432\u043e\u0441\u0442\u0438 \u0440\u0430\u0434\u0438, \u044d\u0442\u043e\u0442 \u043f\u043e\u0434\u0445\u043e\u0434 \u0436\u0438\u0437\u043d\u0435\u0441\u043f\u043e\u0441\u043e\u0431\u0435\u043d (\u044f \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u043b). \u041d\u043e \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043e\u043f\u0438\u0441\u044b\u0432\u0430\u0435\u043c\u044b\u0435 \u0434\u0430\u043b\u0435\u0435 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u0441\u0442\u0430\u043d\u043e\u0432\u044f\u0442\u0441\u044f \u0447\u0443\u0442\u044c \u0441\u043b\u043e\u0436\u043d\u0435\u0435. \u042f \u043e\u0441\u0442\u0430\u043d\u043e\u0432\u0438\u043b\u0441\u044f \u043d\u0430 \u0442\u043e\u043c, \u0447\u0442\u043e \u043a\u043b\u044e\u0447\u0438 \u0432 \u0443\u0437\u043b\u0430\u0445 \u0434\u0435\u0440\u0435\u0432\u0430 \u0432\u0441\u0451-\u0442\u0430\u043a\u0438 \u0434\u043e\u043b\u0436\u043d\u044b \u0431\u044b\u0442\u044c \u0443\u043d\u0438\u043a\u0430\u043b\u044c\u043d\u044b\u043c\u0438. \u041f\u0440\u0438 \u044d\u0442\u043e\u043c \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u0434\u0430\u043d\u043d\u044b\u0435 \u0441 \u043f\u043e\u0432\u0442\u043e\u0440\u044f\u044e\u0449\u0438\u043c\u0438\u0441\u044f \u0438\u0434\u0435\u043d\u0442\u0438\u0444\u0438\u043a\u0430\u0442\u043e\u0440\u0430\u043c\u0438 \u043d\u0443\u0436\u043d\u043e \u0443\u043c\u0435\u0442\u044c. \u0420\u0435\u0448\u0435\u043d\u0438\u0435: \u0432\u043d\u0443\u0442\u0440\u0438 \u0443\u0437\u043b\u0430 \u0440\u0430\u0437\u043c\u0435\u0449\u0430\u0442\u044c \u043d\u0435 \u043e\u0434\u043d\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435, \u0430 \u043a\u043e\u043b\u043b\u0435\u043a\u0446\u0438\u044e \u043e\u043d\u044b\u0445. \u041a\u0430\u043a \u0438\u043c\u0435\u043d\u043d\u043e \u044d\u0442\u043e \u0431\u0443\u0434\u0435\u0442 \u0443\u0441\u0442\u0440\u043e\u0435\u043d\u043e \u2014 \u0440\u0435\u0448\u0430\u0442\u044c \u0432\u0430\u043c. \u042f \u0432\u044b\u0431\u0440\u0430\u043b <code>LinkedList&lt;&gt;<\/code>.<\/p>\n<p>\u0427\u0442\u043e\u0431\u044b \u043d\u0435 \u0437\u0430\u043f\u0443\u0442\u0430\u0442\u044c\u0441\u044f \u0432 \u0434\u0430\u043b\u044c\u043d\u0435\u0439\u0448\u0435\u043c \u043f\u043e\u0432\u0435\u0441\u0442\u0432\u043e\u0432\u0430\u043d\u0438\u0438 \u0438 \u0438\u0437\u0431\u0435\u0436\u0430\u0442\u044c \u043c\u043d\u043e\u0433\u043e\u0441\u043b\u043e\u0432\u043d\u043e\u0441\u0442\u0438, \u043f\u0440\u0438\u043c\u0435\u043c \u0442\u0430\u043a\u0443\u044e \u0442\u0435\u0440\u043c\u0438\u043d\u043e\u043b\u043e\u0433\u0438\u044e:<\/p>\n<ul>\n<li>\n<p>\u0434\u0435\u0440\u0435\u0432\u043e \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0438\u0437 <strong>\u0443\u0437\u043b\u043e\u0432<\/strong> (tree node), \u0438\u043c\u0435\u044e\u0449\u0438\u0445 \u043a\u043b\u044e\u0447;<\/p>\n<\/li>\n<li>\n<p>\u0443\u0437\u0435\u043b \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u0441\u043f\u0438\u0441\u043e\u043a <strong>\u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432<\/strong> (node element), \u0432 \u043d\u0430\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u043a\u0430\u0436\u0434\u044b\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u044d\u0442\u043e <code>LinkedListNode&lt;&gt;<\/code>;<\/p>\n<\/li>\n<li>\n<p>\u0432 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0435 \u0445\u0440\u0430\u043d\u0438\u0442\u0441\u044f <strong>\u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435<\/strong> (value), \u0442.\u0435. \u043e\u0431\u044a\u0435\u043a\u0442 \u0434\u0430\u043d\u043d\u044b\u0445, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043c\u044b \u043f\u043e\u043c\u0435\u0449\u0430\u0435\u043c \u0432 \u0434\u0435\u0440\u0435\u0432\u043e.<\/p>\n<\/li>\n<\/ul>\n<figure class=\"full-width\"><\/figure>\n<p>\u041f\u0435\u0440\u0435\u0434 \u0442\u0435\u043c, \u043a\u0430\u043a \u043d\u0430\u0447\u0430\u0442\u044c \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u0442\u044c, \u0434\u0438\u0441\u043a\u043b\u0435\u0439\u043c\u0435\u0440: \u043a\u043e\u0434 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c (\u0438 \u0431\u0443\u0434\u0435\u0442) \u0433\u0434\u0435-\u0442\u043e \u043d\u0435\u0438\u0434\u0435\u0430\u043b\u044c\u043d\u044b\u043c, \u0433\u0434\u0435-\u0442\u043e \u043d\u0435 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044e\u0449\u0438\u043c \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e\u0441\u0442\u0438 \u043d\u043e\u0432\u044b\u0445 \u0432\u0435\u0440\u0441\u0438\u0439 C#, \u0433\u0434\u0435-\u0442\u043e \u043d\u0435 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u0439 \u0432\u0430\u0448\u0438\u043c \u043f\u0440\u043e\u0444\u0435\u0441\u0441\u0438\u043e\u043d\u0430\u043b\u044c\u043d\u044b\u043c \u0432\u043a\u0443\u0441\u0430\u043c. \u041f\u0440\u0438\u043c\u0435\u0440 \u043d\u0435\u043e\u0434\u043d\u043e\u0437\u043d\u0430\u0447\u043d\u043e\u0433\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u2014 \u0441\u043f\u043e\u0441\u043e\u0431 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u0446\u0432\u0435\u0442\u0430 \u0443\u0437\u043b\u0430. \u041f\u0440\u0430\u0432\u0438\u043b\u0430 \u0445\u043e\u0440\u043e\u0448\u0435\u0433\u043e \u0442\u043e\u043d\u0430 \u043f\u043e\u0434\u0441\u043a\u0430\u0437\u044b\u0432\u0430\u044e\u0442, \u0447\u0442\u043e \u043d\u0443\u0436\u043d\u043e \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u044c <code>enum<\/code> \u0441 \u0434\u0432\u0443\u043c\u044f \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f\u043c\u0438 (<code>Red<\/code> \u0438 <code>Black<\/code>) \u0438 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0435\u0433\u043e \u0434\u043b\u044f \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u0430 <code>Color<\/code> \u0432 \u0443\u0437\u043b\u0435. \u0412 \u043f\u0435\u0440\u0432\u043e\u0439 \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u0438 \u044f \u0442\u0430\u043a \u0438 \u0441\u0434\u0435\u043b\u0430\u043b. \u041d\u043e \u043f\u043e\u0442\u043e\u043c \u043f\u043e\u0434\u0443\u043c\u0430\u043b \u2014 \u0446\u0432\u0435\u0442 \u0432\u0435\u0434\u044c \u043d\u0435 \u0431\u043e\u043b\u0435\u0435 \u0447\u0435\u043c \u043c\u0435\u0442\u0430\u0444\u043e\u0440\u0430 \u0434\u043b\u044f \u0430\u0442\u0440\u0438\u0431\u0443\u0442\u0430, \u043d\u0443\u0436\u043d\u043e\u0433\u043e \u043f\u0440\u043e\u0446\u0435\u0434\u0443\u0440\u0435 \u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u043e\u0432\u043a\u0438 \u0434\u0435\u0440\u0435\u0432\u0430. \u0418 \u0443\u0431\u0440\u0430\u043b <code>enum<\/code>, \u0430 \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u043e <code>Color<\/code> \u0437\u0430\u043c\u0435\u043d\u0438\u043b \u043d\u0430 \u0431\u0443\u043b\u0435\u0432\u043e <code>IsRed<\/code>. \u0411\u0440\u0438\u0442\u0432\u0430 \u041e\u043a\u043a\u0430\u043c\u0430 \u0432 \u0434\u0435\u0439\u0441\u0442\u0432\u0438\u0438.<\/p>\n<p>\u0427\u0442\u043e \u0436, \u0432\u043f\u0435\u0440\u0451\u0434! \u041f\u0435\u0440\u0432\u044b\u043c \u0434\u0435\u043b\u043e\u043c \u043e\u043f\u0438\u0448\u0435\u043c \u0443\u0437\u0435\u043b:<\/p>\n<pre><code class=\"cs\">public sealed class RedBlackTreeNode&lt;TKey, TValue&gt;     where TKey : IComparable&lt;TKey&gt; {     public static readonly RedBlackTreeNode&lt;TKey, TValue&gt; Void =         new RedBlackTreeNode&lt;TKey, TValue&gt;(default(TKey), null);      public RedBlackTreeNode(         TKey key,         RedBlackTreeNode&lt;TKey, TValue&gt; parent)     {         Key = key;         Parent = parent;     }      public TKey Key { get; set; }      public LinkedList&lt;TValue&gt; Values { get; } = new LinkedList&lt;TValue&gt;();      public RedBlackTreeNode&lt;TKey, TValue&gt; Left { get; set; }      public RedBlackTreeNode&lt;TKey, TValue&gt; Right { get; set; }      public RedBlackTreeNode&lt;TKey, TValue&gt; Parent { get; set; }      public bool IsRed { get; set; } }<\/code><\/pre>\n<p>\u041c\u043e\u0436\u043d\u043e \u0437\u0430\u043c\u0435\u0442\u0438\u0442\u044c \u0441\u0442\u0440\u0430\u043d\u043d\u0443\u044e \u043a\u043e\u043d\u0441\u0442\u0430\u043d\u0442\u0443 (\u0435\u0441\u043b\u0438 \u0432\u044b \u043f\u043e\u0437\u0432\u043e\u043b\u0438\u0442\u0435 \u043d\u0430\u0437\u0432\u0430\u0442\u044c \u0442\u0430\u043a <code>static readonly<\/code> \u043f\u043e\u043b\u0435) \u2014 <code>Void<\/code>. \u0427\u0442\u043e \u044d\u0442\u043e? \u0412 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u043f\u043e\u0441\u043e\u0431\u0438\u044f \u043f\u043e \u043a\u0440\u0430\u0441\u043d\u043e-\u0447\u0451\u0440\u043d\u043e\u043c\u0443 \u0434\u0435\u0440\u0435\u0432\u0443 \u044f \u0432\u044b\u0431\u0440\u0430\u043b \u043a\u043d\u0438\u0433\u0443 <a href=\"https:\/\/www.amazon.com\/dp\/0262033844\" rel=\"noopener noreferrer nofollow\">\u201cIntroduction to Algorithms\u201d<\/a> (\u0434\u043b\u044f \u0440\u0443\u0441\u0441\u043a\u043e\u044f\u0437\u044b\u0447\u043d\u043e\u0433\u043e \u0447\u0438\u0442\u0430\u0442\u0435\u043b\u044f \u0441\u0435\u0439 \u043a\u0438\u0440\u043f\u0438\u0447 \u043d\u0430 1000+ \u0441\u0442\u0440\u0430\u043d\u0438\u0446 \u0437\u043d\u0430\u043a\u043e\u043c \u043f\u043e\u0434 \u043d\u0430\u0437\u0432\u0430\u043d\u0438\u0435\u043c <em>\u201c\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b. \u041f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u0435 \u0438 \u0430\u043d\u0430\u043b\u0438\u0437\u201d<\/em>). \u0414\u043b\u044f \u0443\u0434\u043e\u0431\u0441\u0442\u0432\u0430 \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u043a\u0438 \u0433\u0440\u0430\u043d\u0438\u0447\u043d\u044b\u0445 \u0441\u043b\u0443\u0447\u0430\u0435\u0432 \u043b\u0438\u0441\u0442\u044c\u044f\u043c\u0438 \u0442\u0430\u043c \u0432\u0441\u0435\u0433\u0434\u0430 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043e\u0431\u044a\u0435\u043a\u0442 <code>nil<\/code>. \u042f \u0436\u0435 \u043f\u0440\u043e\u0441\u0442\u043e \u043d\u0430\u0437\u0432\u0430\u043b \u0435\u0433\u043e <code>Void<\/code>. \u0412 \u043c\u043e\u0451\u043c \u043a\u043e\u0434\u0435 \u0431\u0443\u0434\u0443\u0442 \u0438 \u0434\u0440\u0443\u0433\u0438\u0435 \u0440\u0430\u0441\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u044f \u0441 \u043a\u043d\u0438\u0433\u043e\u0439. \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0442\u0430\u043a\u0438\u0435 \u0432\u044b\u0440\u0430\u0437\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u0435 \u0438\u043c\u0435\u043d\u0430 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445, \u043a\u0430\u043a <code>w<\/code>, <code>x<\/code> \u0438 <code>y<\/code>, \u044f \u0440\u0435\u0448\u0438\u043b \u043d\u0435 \u0441\u043e\u0445\u0440\u0430\u043d\u044f\u0442\u044c.<\/p>\n<p>\u041a\u0430\u0441\u0430\u0442\u0435\u043b\u044c\u043d\u043e <code>IComparable&lt;TKey&gt;<\/code>: \u043a\u043b\u044e\u0447\u0438 \u043d\u0435 \u043c\u043e\u0433\u0443\u0442 \u0431\u044b\u0442\u044c \u0441\u043e\u0432\u0441\u0435\u043c \u0443\u0436 \u043b\u044e\u0431\u044b\u043c\u0438. \u041c\u044b, \u043e\u0447\u0435\u0432\u0438\u0434\u043d\u043e, \u0434\u043e\u043b\u0436\u043d\u044b \u0443\u043c\u0435\u0442\u044c \u0438\u0445 \u0441\u0440\u0430\u0432\u043d\u0438\u0432\u0430\u0442\u044c \u0434\u043b\u044f \u043d\u0430\u0432\u0438\u0433\u0430\u0446\u0438\u0438 \u043f\u043e \u0434\u0435\u0440\u0435\u0432\u0443. \u041d\u043e \u043d\u0430 \u044d\u0442\u043e\u043c \u0432\u0441\u0451, \u0431\u043e\u043b\u044c\u0448\u0435 \u043d\u0438\u043a\u0430\u043a\u0438\u0445 \u0442\u0440\u0435\u0431\u043e\u0432\u0430\u043d\u0438\u0439 \u043d\u0438 \u043a \u043a\u043b\u044e\u0447\u0443, \u043d\u0438 \u043a \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044e \u043d\u0435 \u0431\u0443\u0434\u0435\u0442 \u0438 \u043d\u0435 \u0434\u043e\u043b\u0436\u043d\u043e \u0431\u044b\u0442\u044c.<\/p>\n<p>\u0418 \u0442\u0430\u043a, \u0434\u0435\u0440\u0435\u0432\u043e \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0438\u0437 \u0443\u0437\u043b\u043e\u0432, \u0443\u0437\u043b\u044b \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0442 \u0441\u043f\u0438\u0441\u043a\u0438 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432, \u0430 \u043a\u0430\u0436\u0434\u044b\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0445\u0440\u0430\u043d\u0438\u0442 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435. \u041d\u043e \u0442\u043e\u0433\u0434\u0430 \u0432\u044b\u0445\u043e\u0434\u0438\u0442, \u0447\u0442\u043e \u0443\u0437\u043b\u043e\u043c \u043c\u044b \u043d\u0435 \u043c\u043e\u0436\u0435\u043c \u0443\u043a\u0430\u0437\u0430\u0442\u044c \u043d\u0430 \u043a\u043e\u043d\u043a\u0440\u0435\u0442\u043d\u043e\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435. \u0414\u043b\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0434\u0430\u043d\u043d\u043e\u0439 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u044b \u044f \u0432\u0432\u0451\u043b \u043f\u043e\u043d\u044f\u0442\u0438\u0435 <strong>\u043a\u043e\u043e\u0440\u0434\u0438\u043d\u0430\u0442\u044b<\/strong>:<\/p>\n<pre><code class=\"cs\">public sealed class RedBlackTreeCoordinate&lt;TKey, TValue&gt;     where TKey : IComparable&lt;TKey&gt; {     public RedBlackTreeCoordinate(         RedBlackTreeNode&lt;TKey, TValue&gt; treeNode,         LinkedListNode&lt;TValue&gt; nodeElement)     {         TreeNode = treeNode;         NodeElement = nodeElement;     }      public RedBlackTreeNode&lt;TKey, TValue&gt; TreeNode { get; }      public LinkedListNode&lt;TValue&gt; NodeElement { get; }      public TKey Key =&gt; TreeNode.Key;      public TValue Value =&gt; NodeElement.Value; }<\/code><\/pre>\n<p>\u041f\u043e\u0440\u0430 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u044c \u0441\u0430\u043c\u043e \u0434\u0435\u0440\u0435\u0432\u043e. \u0418\u0437 \u0432\u043d\u0443\u0442\u0440\u0435\u043d\u043d\u043e\u0441\u0442\u0435\u0439 \u043f\u043e\u043a\u0430 \u043e\u0431\u044a\u044f\u0432\u0438\u043c \u043a\u043e\u0440\u043d\u0435\u0432\u043e\u0439 \u0443\u0437\u0435\u043b, \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u043e, \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u044e\u0449\u0435\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439, \u0438 \u043f\u0430\u0440\u0443 \u0432\u0441\u043f\u043e\u043c\u043e\u0433\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0445 \u043c\u0435\u0442\u043e\u0434\u043e\u0432:<\/p>\n<pre><code class=\"cs\">public class RedBlackTree&lt;TKey, TValue&gt;     where TKey : IComparable&lt;TKey&gt; {     protected RedBlackTreeNode&lt;TKey, TValue&gt; _root =         RedBlackTreeNode&lt;TKey, TValue&gt;.Void;      public int Count { get; private set; }      protected bool IsVoid(         RedBlackTreeNode&lt;TKey, TValue&gt; node)     {         return node == null || node == RedBlackTreeNode&lt;TKe<\/code><\/pre>\n<\/div>\n<\/div>\n<\/div>\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-464011","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/464011","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=464011"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/464011\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=464011"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=464011"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=464011"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}