Как определить тип бинарного дерева поиска в Юлии? - PullRequest
Новая
       6

Как определить тип бинарного дерева поиска в Юлии?

0 голосов
/ 14 сентября 2018

Я пытаюсь определить тип Двоичного дерева поиска целых чисел в Юлии с помощью следующего: 

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

Теперь я хотел бы определить конструкторы и базовый Push! метод, использующий этот наивный подход: 

BST(key::Int) = BST(key, Nothing, Nothing)
BST() = BST(0)

function Base.push!(node::BST, key)
    if key < node.key
        if node.left.isnull
            node.left = BST(key)
        else
            push!(node.left.value, key)
        end
    elseif key > node.key
        if node.right.isnull
            node.right = BST(key)
        else
            push!(node.right.value, key)
        end
    end
end

root = BST()
push!(root, 1)
push!(root, 2)

Конечно, это не работает с Юлией 1.0! Я, конечно, не правильно понимаю использование союза. Они только абстрактный тип? Что может быть правильным способом определения этой структуры данных?

Документация Джулии плохо объясняет эту тему.

Предыдущий вопрос обратил внимание субъекта на устаревший тип Nullable: Как реализовать дерево бинарного поиска в Юлии?

1 Ответ

0 голосов
/ 14 сентября 2018

Вот как должен выглядеть код (предполагается, что вы не хотите хранить повторяющиеся значения в вашем BST, но я думаю, это именно то, что вы хотели): 

BST(key::Int) = BST(key, nothing, nothing)
BST() = BST(0)

function Base.push!(node::BST, key)
    if key < node.key
        if node.left === nothing
            node.left = BST(key)
        else
            push!(node.left, key)
        end
    elseif key > node.key
        if node.right === nothing
            node.right = BST(key)
        else
            push!(node.right, key)
        end
    end
end

На самом деле ваши определения былипочти нормально, с небольшими синтаксическими проблемами:

  • nothing - это значение, а Nothing - это тип, поэтому вам пришлось писать BST(key, nothing, nothing), а не BST(key, Nothing, Nothing)
  • , который вы тестируетеесли что-то ничего не дает, используя этот вид сравнения node.left === nothing (используйте ===, поскольку компилятор может оптимизировать этот код более легко)
  • вам пришлось push! получить объект BST, а не хранимое значениев нем так push!(node.right, key) не push!(node.right.value, key)
...