２分探索木を右回転する

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

実装

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 right_rotate(root::Node)::Node
    old_root_node = root
    new_root_node = root.left

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

    return new_root_node
end


root = insert(nothing, 4)

insert(root, 2)
insert(root, 5)
insert(root, 1)
insert(root, 3)

@show root

root = right_rotate(root)

@show root

結果

yuu@penguin:~/yatai$ julia thessaly.jl
root = Node(4, Node(2, Node(1, nothing, nothing), Node(3, nothing, nothing)), Node(5, nothing, nothing))
root = Node(2, Node(1, nothing, nothing), Node(4, Node(3, nothing, nothing), Node(5, nothing, nothing)))