tree sort

ツリーソート – 二分探索ツリーを使用したソート。時間計算量 – O(n²)。このようなツリーでは、左側の各ノードにはノードより小さい番号があり、右側にはノードより大きい番号があります。ルートから来て左から右に値を出力すると、ソートされた番号のリストが得られます。。驚くべきことですね?

二分探索ツリー図を考えてみましょう。

デリック・クッツェー (パブリックドメイン)

左下の各ノード、つまり右側のノードごとに、左下隅の最後から 2 番目の左ノードから数字を手動で読み取ってみてください。

次のようになります:

<オル>

左下の最後から２番目のノード – 3.

左分岐があります – 1.

この番号 (1) を選択してください

次に頂点 3 (1, 3) を取得します

右側はブランチ 6 ですが、ブランチが含まれています。したがって、同じように読みます。

ノード 6 の左分岐 4 (1、3、4)

ノード自体は 6 (1、3、4、6) です

右 7 (1、3、4、6、7)

ルートノードに移動します – 8 (1、3、4、6、7、8)

類推により、右側にすべてを出力します

最終的なリストを取得します – 1、3、4、6、7、8、10、13、14

コードでアルゴリズムを実装するには、次の 2 つの関数が必要です。

<オル>

二分探索ツリーの組み立て

二分探索ツリーを正しい順序で出力する

二分探索木は読み取られたときと同じ方法で組み立てられ、それが大きいか小さいかに応じて、左側または右側の各ノードに番号が付けられます。

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)

Важный нюанс что для чисел которые равны вершине придумано множество интересных механизмов подцепления к ноде, я же просто добавил счетчик к классу вершины, при распечатке числа возвращаются по счетчику.