![\"\"](\"https:\/\/demensdeum.com\/blog\/wp-content\/uploads\/2022\/08\/tree.png\")
<\/p>\nTree sort \u2013 sorting by binary search tree. Time complexity – O(n\u00b2). In such a tree, each node has numbers on the left less than the node, on the right greater than the node, when coming from the root and printing values \u200b\u200bfrom left to right, we get a sorted list of numbers. Amazing, right?<\/p>\n
Let’s consider the binary search tree diagram:<\/p>\n
<\/p>\n
Derrick Coetzee<\/a> (public domain)<\/span><\/p>\n Try manually reading the numbers starting from the second to last left node in the lower left corner, for each node on the left – a node on the right.<\/p>\n It will look like this:<\/p>\n To implement the algorithm in code, two functions are required:<\/p>\n A binary search tree is assembled in the same way as it is read, each node is assigned a number on the left or right, depending on whether it is smaller or larger.<\/p>\n Example in Lua:<\/p>\n \u0412\u0430\u0436\u043d\u044b\u0439 \u043d\u044e\u0430\u043d\u0441 \u0447\u0442\u043e \u0434\u043b\u044f \u0447\u0438\u0441\u0435\u043b \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0440\u0430\u0432\u043d\u044b \u0432\u0435\u0440\u0448\u0438\u043d\u0435 \u043f\u0440\u0438\u0434\u0443\u043c\u0430\u043d\u043e \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u044b\u0445 \u043c\u0435\u0445\u0430\u043d\u0438\u0437\u043c\u043e\u0432 \u043f\u043e\u0434\u0446\u0435\u043f\u043b\u0435\u043d\u0438\u044f \u043a \u043d\u043e\u0434\u0435, \u044f \u0436\u0435 \u043f\u0440\u043e\u0441\u0442\u043e \u0434\u043e\u0431\u0430\u0432\u0438\u043b \u0441\u0447\u0435\u0442\u0447\u0438\u043a \u043a \u043a\u043b\u0430\u0441\u0441\u0443 \u0432\u0435\u0440\u0448\u0438\u043d\u044b, \u043f\u0440\u0438 \u0440\u0430\u0441\u043f\u0435\u0447\u0430\u0442\u043a\u0435 \u0447\u0438\u0441\u043b\u0430 \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u044e\u0442\u0441\u044f \u043f\u043e \u0441\u0447\u0435\u0442\u0447\u0438\u043a\u0443.<\/p>\n https:\/\/gitlab.com\/demensdeum\/algorithms\/-\/tree\/master\/sortAlgorithms\/treesort<\/a><\/p>\n TreeSort Algorithm Explained and Implemented with Examples in Java | Sorting Algorithms | Geekific – YouTube<\/a><\/p>\n Tree sort – YouTube<\/a><\/p>\n Convert Sorted Array to Binary Search Tree (LeetCode 108. Algorithm Explained) – YouTube<\/a><\/p>\n Sorting algorithms\/Tree sort on a linked list – Rosetta Code<\/a><\/p>\n Tree Sort – GeeksforGeeks<\/a><\/p>\n Tree sort – Wikipedia<\/a><\/p>\n How to handle duplicates in Binary Search Tree? – GeeksforGeeks<\/a><\/p>\n Tree Sort | GeeksforGeeks – YouTube<\/a><\/p>\n","protected":false},"excerpt":{"rendered":" Tree sort \u2013 sorting by binary search tree. Time complexity – O(n\u00b2). In such a tree, each node has numbers on the left less than the node, on the right greater than the node, when coming from the root and printing values \u200b\u200bfrom left to right, we get a sorted list of numbers. Amazing, right?Continue reading “Tree sort”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[61,52],"tags":[131,190,207],"class_list":["post-3409","post","type-post","status-publish","format-standard","hentry","category-techie","category-tutorials","tag-algorithms","tag-sorting","tag-tree-sort","entry"],"translation":{"provider":"WPGlobus","version":"3.0.2","language":"hi","enabled_languages":["en","ru","zh","de","fr","ja","pt","hi"],"languages":{"en":{"title":true,"content":true,"excerpt":false},"ru":{"title":true,"content":true,"excerpt":false},"zh":{"title":true,"content":true,"excerpt":false},"de":{"title":true,"content":true,"excerpt":false},"fr":{"title":true,"content":true,"excerpt":false},"ja":{"title":true,"content":true,"excerpt":false},"pt":{"title":true,"content":true,"excerpt":false},"hi":{"title":false,"content":false,"excerpt":false}}},"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/demensdeum.com\/blog\/hi\/wp-json\/wp\/v2\/posts\/3409","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/demensdeum.com\/blog\/hi\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/demensdeum.com\/blog\/hi\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/hi\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/hi\/wp-json\/wp\/v2\/comments?post=3409"}],"version-history":[{"count":7,"href":"https:\/\/demensdeum.com\/blog\/hi\/wp-json\/wp\/v2\/posts\/3409\/revisions"}],"predecessor-version":[{"id":3870,"href":"https:\/\/demensdeum.com\/blog\/hi\/wp-json\/wp\/v2\/posts\/3409\/revisions\/3870"}],"wp:attachment":[{"href":"https:\/\/demensdeum.com\/blog\/hi\/wp-json\/wp\/v2\/media?parent=3409"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/hi\/wp-json\/wp\/v2\/categories?post=3409"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/hi\/wp-json\/wp\/v2\/tags?post=3409"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}\n
\n
\n\n\nfunction Node:new(value, lhs, rhs)\n output = {}\n setmetatable(output, self)\n self.__index = self \n output.value = value\n output.lhs = lhs\n output.rhs = rhs\n output.counter = 1\n return output \nend\n\nfunction Node:Increment()\n self.counter = self.counter + 1\nend\n\nfunction Node:Insert(value)\n if self.lhs ~= nil and self.lhs.value > value then\n self.lhs:Insert(value)\n return\n end\n\n if self.rhs ~= nil and self.rhs.value < value then\n self.rhs:Insert(value)\n return\n end\n\n if self.value == value then\n self:Increment()\n return\n elseif self.value > value then\n if self.lhs == nil then\n self.lhs = Node:new(value, nil, nil)\n else\n self.lhs:Insert(value)\n end\n return\n else\n if self.rhs == nil then\n self.rhs = Node:new(value, nil, nil)\n else\n self.rhs:Insert(value)\n end\n return\n end\nend\n\nfunction Node:InOrder(output)\n if self.lhs ~= nil then\n output = self.lhs:InOrder(output)\n end\n output = self:printSelf(output)\n if self.rhs ~= nil then\n output = self.rhs:InOrder(output)\n end\n return output\nend\n\nfunction Node:printSelf(output)\n for i=0,self.counter-1 do\n output = output .. tostring(self.value) .. \" \"\n end\n return output\nend\n\nfunction PrintArray(numbers)\n output = \"\"\n for i=0,#numbers do\n output = output .. tostring(numbers[i]) .. \" \"\n end \n print(output)\nend\n\nfunction Treesort(numbers)\n rootNode = Node:new(numbers[0], nil, nil)\n for i=1,#numbers do\n rootNode:Insert(numbers[i])\n end\n print(rootNode:InOrder(\"\"))\nend\n\n\nnumbersCount = 10\nmaxNumber = 9\n\nnumbers = {}\n\nfor i=0,numbersCount-1 do\n numbers[i] = math.random(0, maxNumber)\nend\n\nPrintArray(numbers)\nTreesort(numbers)<\/code><\/pre>\n<\/div>\n\u0421\u0441\u044b\u043b\u043a\u0438<\/h3>\n
\u0418\u0441\u0442\u043e\u0447\u043d\u0438\u043a\u0438<\/h3>\n