I want to implement a BST using elixir can someone help me with how to approach this ?
Basically, nested improper lists. [right|left] nodes until you get to a branch that has a value instead of another node.
Either what @sribe suggested or you can use 2-ary tuples which will provide equivalent feature set. So you will have tuple in form of tree :: {tree() | node(), tree() | node()}.
I found this
But here the problem is I’m not able to understand how these things are working
def new(elements \\ [], comparator \\ fn a, b -> a - b end)
def new([], comparator), do: %__MODULE__{comparator: comparator}
def new(elements, comparator) when is_list(elements) do
tree = new([], comparator)
Enum.reduce(elements, tree, fn element, tree ->
insert(tree, element)
end)
end
def new(element, comparator), do: new([element], comparator)
What do you have problems with? Understanding the algorithm behind Binary Search Trees, or reading the mentioned Elixir code?
Your question is to broad.
I think you need 2 things:
- How to implement a tree structure in Elixir
- How to implement the algorithms to transform list to BST and how to traverse it.
Binary Search I know. I have implemented using javascript. This elixir code i’m not able to understand
Hey @siddhant3030, I wrote that BST library you linked. It was a side project that I was playing around with so I can’t guarantee the robustness of the code. But I am happy to answer any specific questions you have about it.
1 Like
Hey thanks for replying. Basically I didn’t understand this part.
Here you’re taking new function which takes list of elements and what does comparator do here?
Can you explain these four function and how does it work?
def new(elements \\ [], comparator \\ fn a, b -> a - b end)
def new([], comparator), do: %__MODULE__{comparator: comparator}
def new(elements, comparator) when is_list(elements) do
tree = new([], comparator)
Enum.reduce(elements, tree, fn element, tree ->
insert(tree, element)
end)
end
def new(element, comparator), do: new([element], comparator)
# This is a function head. If a function with multiple clauses has default values,
# such as this one, a head must be provided. So BST.new() always uses an empty List `[]`
# for the elements argument if none is provided, and it uses this function `fn a, b -> a - b end`
# as the default sorting (comparator) function if none is provided.
def new(elements \\ [], comparator \\ fn a, b -> a - b end)
# This clause of the function matches if an empty List was used for the elements
# argument, or if no arguments were provided (because the defaults from the function
# head are used). It returns a %BST{} struct with the default `root` of nil and
# comparator function.
#
# iex> BST.new()
# %BST{comparator: #Function<3.51101074/2 in BST.new/1>, root: nil}
def new([], comparator), do: %__MODULE__{comparator: comparator}
# This clause matches when the elements arguments is a non-empty List. First,
# it calls `new([], comparator)` which is the version of this function defined
# directly above this one. After that, it 'loops' through each element in the
# list, calling `insert/2` to insert the element into the tree.
def new(elements, comparator) when is_list(elements) do
tree = new([], comparator)
Enum.reduce(elements, tree, fn element, tree ->
insert(tree, element)
end)
end
# This clause matches when only one item is passed as the element argument,
# insead of a List. It then calls the version of this function defined above,
# because using `new([element])` would now match the function definition
# that has the `is_list(elements)` guard.
def new(element, comparator), do: new([element], comparator)
I wrote the different versions of the new/2 function to make using the library
easier, but using them is not necessary.
For example doing this:
tree = BST.new(1)
Is effectively the same as this:
tree = BST.new()
tree = BST.insert(tree, 1)
Which is also the same result as this:
tree = BST.new([1])
6 Likes
The comparator is a function that is stored in the BST struct, and is used each time a new element is inserted or updated so the library knows how to sort the elements correctly. For example, using the default comparator fn a, b -> a - b end would correctly sort integers, but a different comparator would need to be used if you are sorting a list of User structs like %User{name: "Alice"} that you want to organize by name.
This reads quite pythonic… As convinient as this actually seems, at the end it will only cause confusion…
Also it causes inconsistencies.
What if I want a BST with the single element [1, 2, 3, 4]? I have to wrap it in an extra list, but if I want a singleton BST of a number, an atom, or even a pid, just the value is enough… Even a set, which is a collection similar to how lists are, will be treated like singleton values here…
That is an interesting use case. I would have to see an example of this data set to contemplate the right approach. You could wrap your list in another list like you mentioned–my first instinct would be to put those values in a map.
What about in the case of list of integers? Will it return the sorted list
Also what happens if I put two similar items in a list?
Like this
[1, 4, 3, 7, 4]
A binary search tree by definition has distinct keys, so duplicates are not allowed. This library would “replace” the duplicate key. So if you create a tree with those values, the data structure looks like this (note 4 only ends up appearing once)
iex> tree = BST.new([1, 4, 3, 7, 4])
%BST{
comparator: #Function<3.51101074/2 in BST.new/1>,
root: %BST.Node{
data: 1,
left: nil,
right: %BST.Node{
data: 4,
left: %BST.Node{data: 3, left: nil, right: nil},
right: %BST.Node{data: 7, left: nil, right: nil}
}
}
}
You can then use the to_list/1 function to get the sorted list
iex> BST.to_list(tree)
[1, 3, 4, 7]
So what if I want to create a duplicate keys. In that case how do I do it?
Why do you want to do that?
A BST is an optimised data structure to answer the question “has a given element been in the original input”, not the question about how often it was in there…
It’s just a thought. I want to make that mistake where I can put duplicate keys and if I can write a function where I can delete all those duplicate keys. So basically something like this
Input
[1, 4, 7, 3, 4, 5, 4]
Output
[1, 7, 3, 5]
Sorry, I do not get it…
Removal of those duplicates is already there, for free…
Basically I want to create a BST which will have duplicate keys and a function which will delete all nodes matching that key.
