{"action":"closed","issue":{"url":"https://api.github.com/repos/ErpCloudSystem/tasks/issues/7","repository_url":"https://api.github.com/repos/ErpCloudSystem/tasks","labels_url":"https://api.github.com/repos/ErpCloudSystem/tasks/issues/7/labels{/name}","comments_url":"https://api.github.com/repos/ErpCloudSystem/tasks/issues/7/comments","events_url":"https://api.github.com/repos/ErpCloudSystem/tasks/issues/7/events","html_url":"https://github.com/ErpCloudSystem/tasks/issues/7","id":168183538,"number":7,"title":"Red-black BST: Insert (part 1)","user":{"login":"bsnisar","id":5427678,"avatar_url":"https://avatars.githubusercontent.com/u/5427678?v=3","gravatar_id":"","url":"https://api.github.com/users/bsnisar","html_url":"https://github.com/bsnisar","followers_url":"https://api.github.com/users/bsnisar/followers","following_url":"https://api.github.com/users/bsnisar/following{/other_user}","gists_url":"https://api.github.com/users/bsnisar/gists{/gist_id}","starred_url":"https://api.github.com/users/bsnisar/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/bsnisar/subscriptions","organizations_url":"https://api.github.com/users/bsnisar/orgs","repos_url":"https://api.github.com/users/bsnisar/repos","events_url":"https://api.github.com/users/bsnisar/events{/privacy}","received_events_url":"https://api.github.com/users/bsnisar/received_events","type":"User","site_admin":false},"labels":[],"state":"closed","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":0,"created_at":"2016-07-28T20:02:33Z","updated_at":"2016-08-03T18:37:16Z","closed_at":"2016-08-03T18:37:16Z","body":"Добавление в RBT (просто добавление без балансировок и всего остального):\r\n\r\nсоздать интерфейс \r\nTree<T> {\r\n   add(E elem);\r\n}\r\n\r\nВнутренней представление узла.\r\n\r\n`private class Node {\r\n     final T element;\r\n     Node root;\r\n     Node left;\r\n     Node right;\r\n}`\r\n\r\n\r\nТекущий код должен обеспечивать вставку элемента в дерево согласно правилу поиска элемента  в дерева: \r\n1. элемент больше чем узел - элемент идет в правое поддерево, и проверка повторяется у root узлом поддерева\r\n2.элемент меньше чем узел - элемент идет в левое поддерево, и проверка повторяется у root узлом поддерева\r\n3. элемент равен узлу -> элемент уже есть в дереве, ничего не добавляем.\r\n     \r\nGiven:\r\n        {A}\r\n     /         \\\r\n {B}        {C}\r\n\r\nДобавляем D. D больше C.\r\n\r\n1.     \r\n     {A}     <- D больше А, идем в право.  \r\n   /      \\\r\n{B}     {C}\r\n\r\n2.     \r\n     {A}       \r\n   /      \\\r\n{B}     {C}  <- D больше C, идем в право.\r\n\r\n3.     \r\n     {A}       \r\n   /      \\\r\n{B}     {C}  <- D больше C, идем в право.\r\n\r\n4.     \r\n     {A}       \r\n   /      \\\r\n{B}     {C}  \r\n              \\\r\n              {Nil} <- Лист дерева, эфемерный элемент, который представляет собой пустоту.                   Свободно добавляем D.\r\n\r\n\r\n5.     После добавления\r\n     {A}       \r\n   /      \\\r\n{B}     {C}  \r\n              \\\r\n              {D} \r\n\r\n\r\n\r\nNote: особенности имплементации в том что необходимо уметь сравнивать элементы на больше-меньше-равно. Для этого используется два варианта сравнения: Comparable<T> и Comparator<T>. Ознакомитесь с интерфейсом и контрактом этих двух методов (javadoc подробен и детален). \r\n\r\nПоэтому для функционирования дерева имплементация должна получать компаратор для сравнения элементов внутри себя. \r\n\r\nПример:\r\n`\r\nComparator<Integer> com = ....;\r\nTree<Integer> tree = new RadBlackTree(com);\r\n`\r\n\r\n "}}
{"actor":{"display_login":"bsnisar"}}