Tree sort

Tree sort – binary search tree sort. Time complexity – O(n²). In such a tree, each node has numbers less than the node on the left, more than the node on the right, when coming from the root and printing the values ​​from left to right, we get a sorted list of numbers. Surprising huh?

Consider the binary search tree schema:

Derrick Coetzee (public domain)

Try to manually read the numbers starting from the penultimate left node of the lower left corner, for each node on the left – a node – on the right.

It will turn out like this:

  1. The penultimate node at the bottom left is 3.
  2. She has a left branch – 1.
  3. Take this number (1)
  4. Next, take the vertex 3 (1, 3) itself
  5. To the right is branch 6, but it contains branches. Therefore, we read it in the same way.
  6. Left branch of node 6 number 4 (1, 3, 4)
  7. Node 6 itself (1, 3, 4, 6)
  8. Right 7 (1, 3, 4, 6, 7)
  9. Go up to the root node – 8 (1,3, 4 ,6, 7, 8)
  10. Print everything on the right by analogy
  11. Get the final list – 1, 3, 4, 6, 7, 8, 10, 13, 14

To implement the algorithm in code, you need two functions:

  1. Building a binary search tree
  2. Printing the binary search tree in the correct order

They assemble a binary search tree in the same way as they read it, a number is attached to each node on the left or right, depending on whether it is less or more.

Lua example:

Node = {value = nil, lhs = nil, rhs = nil}

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)

An important nuance is that for numbers that are equal to the vertex, a lot of interesting mechanisms for hooking to the node have been invented, but I just added a counter to the vertex class, when printing, the numbers are returned by the counter.

Links

https://gitlab.com/demensdeum /algorithms/-/tree/master/sortAlgorithms/treesort

References

TreeSort Algorithm Explained and Implemented with Examples in Java | Sorting Algorithms | Geekific – YouTube

Tree sort – YouTube

Convert Sorted Array to Binary Search Tree (LeetCode 108. Algorithm Explained) – YouTube

Sorting algorithms/Tree sort on a linked list – Rosetta Code

Tree Sort – GeeksforGeeks

Tree sort – Wikipedia

How to handle duplicates in Binary Search Tree? – GeeksforGeeks

Tree Sort | GeeksforGeeks – YouTube