Inserting in RED-BLACK TREE in Julia language

Jaciara Ferreira 0
Viewed 67

i am new at julia and i have the following question:

How can i insert nodes in a RED_BLACK tree made of strings and another stucture? For example: Code the functions necessary to insert and remove nodes of the type represented in Figure 1 for trees of type RED-BLACK. Demonstrate how it works in the insertion with the following names:

  • James James
  • Joe Joe
  • Livia Livia Displaying the memory contents after the operation.

THE TYPE MENTIONED ("in figure 1"):

"""
structure that represents Full names
"""
mutable struct Nomes
    key::Int
    nome::String
end

"""
Nomes( nome::String )
Register constructor for names with no accents
"""
function Nomes( nome::String )
    key = sum( [ Int( c ) for c in nome ] )
    Nomes( key, nome )
end
red-black-tree insert julia string
1 Answers

DataStructures has Red-Black trees. You must define isless for your data structure if you are going to store the Nomes directly in the tree (you could just store their keys as integers if they are unique).

using DataStructures

Base.isless(n1::Nomes, n2::Nomes) = n1.key < n2.key

rbtree = RBTree{Nomes}()

for nom in ["Sue", "John"]
    insert!(rbtree, Nomes(nom))
end

@show rbtree

rbtree = RBTree{Nomes}(DataStructures.RBTreeNode{Nomes}(false, Nomes(301, 
"Sue"), DataStructures.RBTreeNode{Nomes}(false, nothing, nothing, 
nothing, nothing), DataStructures.RBTreeNode{Nomes}(true, Nomes(399, 
"John"), DataStructures.RBTreeNode{Nomes}(false, nothing, nothing, 
nothing, nothing), DataStructures.RBTreeNode{Nomes}(false, nothing, 
nothing, nothing, nothing), DataStructures.RBTreeNode{Nomes}(#= circular 
reference @-2 =#)), nothing), DataStructures.RBTreeNode{Nomes}(false, 
nothing, nothing, nothing, nothing), 2)
userNbYh0
Related