如何在 Julia 中实现二叉搜索树? [英] How to implement a Binary Search Tree in Julia?

问题描述

我正在尝试在 Julia 中实现 BST，但在调用插入函数时遇到了问题.当我尝试创建新节点时，结构保持不变.

I am trying to implement BST in Julia, but I encountered problem when I call insert function. When I try to create new node, the structure stays unchanged.

我的代码:

type Node
    key::Int64
    left
    right
end

function insert(key::Int64, node)
    if node == 0
        node = Node(key, 0, 0)
    elseif key < node.key
        insert(key, node.left)
    elseif key > node.key
        insert(key, node.right)
    end
end

root = Node(0,0,0)
insert(1,root)
insert(2,root)

我也尝试将零更改为无.我尝试的下一个版本是在 Node 中定义了数据类型，但是当我尝试调用没有任何值的插入时(类似于 C Null)它给了我错误.

I also tried to change zero to nothing. Next version which I tried is with defined datatypes in Node, but when I try to call insert with nothing value(similar to C Null) it gave me error.

感谢您的回答.

推荐答案

代码有很多问题.一是它的类型不稳定，左右可以包含任何东西.另一个是在插入函数内部设置局部变量节点不会影响任何更改.一个风格问题，修改其参数的函数通常有一个！作为名称中的最后一个字符，例如 insert!、push!设置索引！.

The code has a number of issues. One is that it is not type stable, left and right could contain anything. The other is that setting the local variable node inside the insert function will not affect change anything. A stylistic issue, functions that modify their arguments generally have a ! as the last character in the name, such as insert!, push! setindex!.

我认为以下应该可行:

type BST
    key::Int
    left::Nullable{BST}
    right::Nullable{BST}
end

BST(key::Int) = BST(key, Nullable{BST}(), Nullable{BST}())
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)

这个版本重载了 Julia 推送！函数，并使用 Nullable 类型，以便它可以区分叶子节点以及它需要继续搜索以找到插入键的位置.这是一个递归定义，并没有优化，使用循环而不是递归会更快.

This version overloads the Julia push! function, and uses the Nullable type so that it can distinguish between a leaf node and where it needs to continue searching to find where to insert the key. This is a recursive definition, and is not optimized, it would be much faster to do it with loops instead of recursive.

这篇关于如何在 Julia 中实现二叉搜索树?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！