I'm working on modernizing Rosetta Code's infrastructure. Starting with communications. Please accept this time-limited open invite to RC's Slack.. --Michael Mol (talk) 20:59, 30 May 2020 (UTC)

# Red black tree sort/Julia

## Julia

Code originally by Koustav Chowdhury.

`""" Modified from JuliaCollections/DataStructures.jl's file red_black_tree.jl """ # leftChild has keys which are less than the node# rightChild has keys which are greater than the node# isred is true if it's a Red Node, else it's false# keys are uniquemutable struct RBTreeNode{K}    isred::Bool    data::Union{K, Nothing}    leftChild::Union{Nothing, RBTreeNode{K}}    rightChild::Union{Nothing, RBTreeNode{K}}    parent::Union{Nothing, RBTreeNode{K}}     RBTreeNode{K}() where K = new{K}(true, nothing, nothing, nothing, nothing)     RBTreeNode{K}(d::K) where K = new{K}(true, d, nothing, nothing, nothing)end RBTreeNode() = RBTreeNode{Any}()RBTreeNode(d) = RBTreeNode{Any}(d) function create_null_node(K::Type)    node = RBTreeNode{K}()    node.isred = false    return nodeend mutable struct RBTree{K}    root::RBTreeNode{K}    nil::RBTreeNode{K}    count::Int     function RBTree{K}() where K        rb = new()        rb.nil = create_null_node(K)        rb.root = rb.nil        rb.count = 0        return rb    endend RBTree() = RBTree{Any}() Base.length(tree::RBTree) = tree.count """    search_node(tree, key) Returns the last visited node, while traversing through in binary-search-tree fashion looking for `key`."""function search_node(tree::RBTree{K}, d::K) where K    node = tree.root    while node !== tree.nil && d != node.data        if d < node.data            node = node.leftChild        else            node = node.rightChild        end    end    return nodeend """    haskey(tree, key) Returns true if `key` is present in the `tree`, else returns false."""function Base.haskey(tree::RBTree{K}, d::K) where K    node = search_node(tree, d)    return (node.data == d)end """    insert_node!(tree::RBTree, node::RBTreeNode) Inserts `node` at proper location by traversing through the `tree` in a binary-search-tree fashion."""function insert_node!(tree::RBTree, node::RBTreeNode)    node_y = nothing    node_x = tree.root     while node_x !== tree.nil        node_y = node_x        if node.data < node_x.data            node_x = node_x.leftChild        else            node_x = node_x.rightChild        end    end     node.parent = node_y    if node_y == nothing        tree.root = node    elseif node.data < node_y.data        node_y.leftChild = node    else        node_y.rightChild = node    endend """    left_rotate!(tree::RBTree, node_x::RBTreeNode) Performs a left-rotation on `node_x` and updates `tree.root`, if required."""function left_rotate!(tree::RBTree, node_x::RBTreeNode)    node_y = node_x.rightChild    node_x.rightChild = node_y.leftChild    if node_y.leftChild !== tree.nil        node_y.leftChild.parent = node_x    end    node_y.parent = node_x.parent    if (node_x.parent == nothing)        tree.root = node_y    elseif (node_x == node_x.parent.leftChild)        node_x.parent.leftChild = node_y    else        node_x.parent.rightChild = node_y    end    node_y.leftChild = node_x    node_x.parent = node_yend """    right_rotate!(tree::RBTree, node_x::RBTreeNode) Performs a right-rotation on `node_x` and updates `tree.root`, if required."""function right_rotate!(tree::RBTree, node_x::RBTreeNode)    node_y = node_x.leftChild    node_x.leftChild = node_y.rightChild    if node_y.rightChild !== tree.nil        node_y.rightChild.parent = node_x    end    node_y.parent = node_x.parent    if (node_x.parent == nothing)        tree.root = node_y    elseif (node_x == node_x.parent.leftChild)        node_x.parent.leftChild = node_y    else        node_x.parent.rightChild = node_y    end    node_y.rightChild = node_x    node_x.parent = node_yend """   fix_insert!(tree::RBTree, node::RBTreeNode) This method is called to fix the property of having no two adjacent nodes of red color in the `tree`."""function fix_insert!(tree::RBTree, node::RBTreeNode)    parent = nothing    grand_parent = nothing    # for root node, we need to change the color to black    # other nodes, we need to maintain the property such that    # no two adjacent nodes are red in color    while  node != tree.root && node.parent.isred        parent = node.parent        grand_parent = parent.parent         if (parent == grand_parent.leftChild) # parent is the leftChild of grand_parent            uncle = grand_parent.rightChild             if (uncle.isred) # uncle is red in color                grand_parent.isred = true                parent.isred = false                uncle.isred = false                node = grand_parent            else  # uncle is black in color                if (node == parent.rightChild) # node is rightChild of its parent                    node = parent                    left_rotate!(tree, node)                end                # node is leftChild of its parent                node.parent.isred = false                node.parent.parent.isred = true                right_rotate!(tree, node.parent.parent)            end        else # parent is the rightChild of grand_parent            uncle = grand_parent.leftChild             if (uncle.isred) # uncle is red in color                grand_parent.isred = true                parent.isred = false                uncle.isred = false                node = grand_parent            else  # uncle is black in color                if (node == parent.leftChild) # node is leftChild of its parent                    node = parent                    right_rotate!(tree, node)                end                # node is rightChild of its parent                node.parent.isred = false                node.parent.parent.isred = true                left_rotate!(tree, node.parent.parent)            end        end    end    tree.root.isred = falseend """    insert!(tree, key) Inserts `key` in the `tree` if it is not present."""function Base.insert!(tree::RBTree{K}, d::K) where K    # if the key exists in the tree, no need to insert    haskey(tree, d) && return tree     # insert, if not present in the tree    node = RBTreeNode{K}(d)    node.leftChild = node.rightChild = tree.nil     insert_node!(tree, node)     if node.parent == nothing        node.isred = false    elseif node.parent.parent == nothing        ;    else        fix_insert!(tree, node)    end    tree.count += 1    return treeend """    delete_fix(tree::RBTree, node::Union{RBTreeNode, Nothing}) This method is called when a black node is deleted because it violates the black depth property of the RBTree."""function delete_fix(tree::RBTree, node::Union{RBTreeNode, Nothing})    while node != tree.root && !node.isred         if node == node.parent.leftChild            sibling = node.parent.rightChild            if sibling.isred                sibling.isred = false                node.parent.isred = true                left_rotate!(tree, node.parent)                sibling = node.parent.rightChild            end             if !sibling.rightChild.isred && !sibling.leftChild.isred                sibling.isred = true                node = node.parent            else                if !sibling.rightChild.isred                    sibling.leftChild.isred = false                    sibling.isred = true                    right_rotate!(tree, sibling)                    sibling = node.parent.rightChild                end                 sibling.isred = node.parent.isred                node.parent.isred = false                sibling.rightChild.isred = false                left_rotate!(tree, node.parent)                node = tree.root            end        else            sibling = node.parent.leftChild            if sibling.isred                sibling.isred = false                node.parent.isred = true                right_rotate!(tree, node.parent)                sibling = node.parent.leftChild            end             if !sibling.rightChild.isred && !sibling.leftChild.isred                sibling.isred = true                node = node.parent            else                if !sibling.leftChild.isred                    sibling.rightChild.isred = false                    sibling.isred = true                    left_rotate!(tree, sibling)                    sibling = node.parent.leftChild                end                 sibling.isred = node.parent.isred                node.parent.isred = false                sibling.leftChild.isred = false                right_rotate!(tree, node.parent)                node = tree.root            end        end    end    node.isred = false    return nothingend """    rb_transplant(tree::RBTree, u::Union{RBTreeNode, Nothing}, v::Union{RBTreeNode, Nothing}) Replaces `u` by `v` in the `tree` and updates the `tree` accordingly."""function rb_transplant(tree::RBTree, u::Union{RBTreeNode, Nothing}, v::Union{RBTreeNode, Nothing})    if u.parent == nothing        tree.root = v    elseif u == u.parent.leftChild        u.parent.leftChild = v    else        u.parent.rightChild = v    end    v.parent = u.parentend """   minimum_node(tree::RBTree, node::RBTreeNode) Returns the RBTreeNode with minimum value in subtree of `node`."""function minimum_node(tree::RBTree, node::RBTreeNode)    (node === tree.nil) && return node    while node.leftChild !== tree.nil        node = node.leftChild    end    return nodeend """    delete!(tree::RBTree, key) Deletes `key` from `tree`, if present, else returns the unmodified tree."""function Base.delete!(tree::RBTree{K}, d::K) where K    z = tree.nil    node = tree.root     while node !== tree.nil        if node.data == d            z = node        end         if d < node.data            node = node.leftChild        else            node = node.rightChild        end    end     (z === tree.nil) && return tree     y = z    y_original_color = y.isred    x = RBTreeNode{K}()    if z.leftChild === tree.nil        x = z.rightChild        rb_transplant(tree, z, z.rightChild)    elseif z.rightChild === tree.nil        x = z.leftChild        rb_transplant(tree, z, z.leftChild)    else        y = minimum_node(tree, z.rightChild)        y_original_color = y.isred        x = y.rightChild         if y.parent == z            x.parent = y        else            rb_transplant(tree, y, y.rightChild)            y.rightChild = z.rightChild            y.rightChild.parent = y        end         rb_transplant(tree, z, y)        y.leftChild = z.leftChild        y.leftChild.parent = y        y.isred = z.isred    end     !y_original_color && delete_fix(tree, x)    tree.count -= 1    return treeend """    function sortednodes(node::RBTreeNode{K}) where K Return a sorted node list. Recursive."""function sortednodes(node::RBTreeNode{K}, nilnode) where K    if (node !== nilnode)        left = sortednodes(node.leftChild, nilnode)        right = sortednodes(node.rightChild, nilnode)        return append!(push!(left, node), right)    else        return RBTreeNode{K}[]    endend """   Print the RBTree (red black tree) as a list of nodes with their keys."""function Base.print(io::IO, tree::RBTree)    println(io, "Red-Black tree node list is:")    for node in sortednodes(tree.root, tree.nil)        left = node.leftChild === tree.nil ? "empty" : string(node.leftChild.data)        color = node.isred ? "red" : "black"        right = node.rightChild === tree.nil ? "empty" : string(node.rightChild.data)        parent = node.parent isa Nothing ? "empty" : string(node.parent.data)        println(io, "(left: \$left, color: \$color, current: \$(node.data), right: \$right, parent: \$parent)")    endend function RBTsort()    tree, data = RBTree(), Int[]    while length(unique(data)) < 30        data = rand(1:1000, 30)    end    for i in data        insert!(tree, i)    end    println("After adding 30 nodes, ", tree)    # data is already in random order here, so use that order for deletion task    for i in 1:15        delete!(tree, data[i])    end    println("After deleting 15 of the nodes, ", tree)end RBTsort() `
Output:
```After adding 30 nodes, Red-Black tree node list is:
(left: empty, color: red, current: 12, right: empty, parent: 18)
(left: 12, color: black, current: 18, right: 19, parent: 58)
(left: empty, color: red, current: 19, right: empty, parent: 18)
(left: 18, color: red, current: 58, right: 67, parent: 94)
(left: empty, color: black, current: 67, right: 78, parent: 58)
(left: empty, color: red, current: 78, right: empty, parent: 67)
(left: 58, color: black, current: 94, right: 155, parent: 207)
(left: empty, color: black, current: 112, right: 153, parent: 155)
(left: empty, color: red, current: 153, right: empty, parent: 112)
(left: 112, color: red, current: 155, right: 187, parent: 94)
(left: empty, color: red, current: 181, right: empty, parent: 187)
(left: 181, color: black, current: 187, right: empty, parent: 155)
(left: 94, color: black, current: 207, right: 488, parent: empty)
(left: empty, color: black, current: 215, right: empty, parent: 253)
(left: 215, color: black, current: 253, right: 401, parent: 488)
(left: empty, color: red, current: 305, right: empty, parent: 319)
(left: 305, color: black, current: 319, right: 390, parent: 401)
(left: empty, color: red, current: 390, right: empty, parent: 319)
(left: 319, color: red, current: 401, right: 408, parent: 253)
(left: empty, color: black, current: 408, right: 445, parent: 401)
(left: empty, color: red, current: 445, right: empty, parent: 408)
(left: 253, color: red, current: 488, right: 862, parent: 207)
(left: empty, color: red, current: 606, right: empty, parent: 653)
(left: 606, color: black, current: 653, right: 731, parent: 754)
(left: empty, color: red, current: 731, right: empty, parent: 653)
(left: 653, color: red, current: 754, right: 842, parent: 862)
(left: empty, color: black, current: 842, right: empty, parent: 754)
(left: 754, color: black, current: 862, right: 1000, parent: 488)
(left: empty, color: red, current: 948, right: empty, parent: 1000)
(left: 948, color: black, current: 1000, right: empty, parent: 862)

After deleting 15 of the nodes, Red-Black tree node list is:
(left: empty, color: red, current: 12, right: empty, parent: 18)
(left: 12, color: black, current: 18, right: 19, parent: 58)
(left: empty, color: red, current: 19, right: empty, parent: 18)
(left: 18, color: red, current: 58, right: 78, parent: 153)
(left: empty, color: black, current: 78, right: empty, parent: 58)
(left: 58, color: black, current: 153, right: 181, parent: 305)
(left: empty, color: black, current: 181, right: empty, parent: 153)
(left: 153, color: black, current: 305, right: 606, parent: empty)
(left: empty, color: black, current: 319, right: empty, parent: 401)
(left: 319, color: black, current: 401, right: 445, parent: 606)
(left: empty, color: black, current: 445, right: empty, parent: 401)
(left: 401, color: red, current: 606, right: 754, parent: 305)
(left: empty, color: black, current: 731, right: empty, parent: 754)
(left: 731, color: black, current: 754, right: 948, parent: 606)
(left: empty, color: black, current: 948, right: empty, parent: 754)
```