２分探索木を左回転する

２分探索木を左回転してみます。

実装

mutable struct Node
    key::Int
    left::Union{Node, Nothing}
    right::Union{Node, Nothing}
end

function insert(root::Union{Node, Nothing}, key::Int)::Node
    if root === nothing
        root = Node(key, nothing, nothing)
    elseif root.key > key
        root.left = insert(root.left, key)
    elseif root.key < key
        root.right = insert(root.right, key)
    end

    return root
end

function left_rotate(root::Node)::Node
    old_root_node = root
    new_root_node = root.right

    old_root_node.right = new_root_node.left
    new_root_node.left = old_root_node

    return new_root_node
end


root = insert(nothing, 10)

insert(root, 8)
insert(root, 12)

insert(root, 2)
insert(root, 9)
insert(root, 11)
insert(root, 15)

root = left_rotate(root)

@show root

結果

yuu@penguin:~/yatai$ julia nagai.jl 
root = Node(12, Node(10, Node(8, Node(2, nothing, nothing), Node(9, nothing, nothing)), Node(11, nothing, nothing)), Node(15, nothing, nothing))