Tree sort – sorting by binary search tree. Time complexity – O(n²). 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 from left to right, we get a sorted list of numbers. Amazing, right?
Let’s consider the binary search tree diagram:
Derrick Coetzee (public domain)
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.
It will look like this:
- The second to last node on the bottom left is 3.
- It has a left branch – 1.
- We take this number (1)
- Next we take the vertex itself 3 (1, 3)
- On the right is branch 6, but it contains branches. Therefore, we read it in the same way.
- Left branch of node 6 is number 4 (1, 3, 4)
- The node itself is 6 (1, 3, 4, 6)
- Right 7 (1, 3, 4, 6, 7)
- We go up to the root node – 8 (1,3, 4,6, 7, 8)
- Print everything on the right by analogy
- We get the final list – 1, 3, 4, 6, 7, 8, 10, 13, 14
To implement the algorithm in code, two functions are required:
- Building a Binary Search Tree
- Print out the binary search tree in the correct order
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.
Example in Lua:
function Node:new(value, lhs, rhs)
output = {}
setmetatable(output, self)
self.__index = self
output.value = value
output.lhs = lhs
output.rhs = rhs
output.counter = 1
return output
end
function Node:Increment()
self.counter = self.counter + 1
end
function Node:Insert(value)
if self.lhs ~= nil and self.lhs.value > value then
self.lhs:Insert(value)
return
end
if self.rhs ~= nil and self.rhs.value < value then
self.rhs:Insert(value)
return
end
if self.value == value then
self:Increment()
return
elseif self.value > value then
if self.lhs == nil then
self.lhs = Node:new(value, nil, nil)
else
self.lhs:Insert(value)
end
return
else
if self.rhs == nil then
self.rhs = Node:new(value, nil, nil)
else
self.rhs:Insert(value)
end
return
end
end
function Node:InOrder(output)
if self.lhs ~= nil then
output = self.lhs:InOrder(output)
end
output = self:printSelf(output)
if self.rhs ~= nil then
output = self.rhs:InOrder(output)
end
return output
end
function Node:printSelf(output)
for i=0,self.counter-1 do
output = output .. tostring(self.value) .. " "
end
return output
end
function PrintArray(numbers)
output = ""
for i=0,#numbers do
output = output .. tostring(numbers[i]) .. " "
end
print(output)
end
function Treesort(numbers)
rootNode = Node:new(numbers[0], nil, nil)
for i=1,#numbers do
rootNode:Insert(numbers[i])
end
print(rootNode:InOrder(""))
end
numbersCount = 10
maxNumber = 9
numbers = {}
for i=0,numbersCount-1 do
numbers[i] = math.random(0, maxNumber)
end
PrintArray(numbers)
Treesort(numbers)
Важный нюанс что для чисел которые равны вершине придумано множество интересных механизмов подцепления к ноде, я же просто добавил счетчик к классу вершины, при распечатке числа возвращаются по счетчику.
Ссылки
https://gitlab.com/demensdeum/algorithms/-/tree/master/sortAlgorithms/treesort
Источники
Convert Sorted Array to Binary Search Tree (LeetCode 108. Algorithm Explained) – YouTube
Sorting algorithms/Tree sort on a linked list – Rosetta Code
How to handle duplicates in Binary Search Tree? – GeeksforGeeks
Tree Sort | GeeksforGeeks – YouTube