Return to Answer

added 1677 characters in body

Source Link

edited Dec 26, 2017 at 13:17

Note: (Partially note to self) This probably isn't the fully best way to do this, the validation method should validate behavior rather than class. I should write more about that.

My first thought upon seeingFirst off, I think that BST isn't that great of a name for this class is. I'd go with Tree, because that is what it isn't really necessarystores. In a binary search tree

Anyways, it's sufficientfirst thing first: I'd make it possible to keep track ofpass root to the rootinitializer by making it an argument with a default value:

def initialize(root = nil)
  @root = root
end

Next thing's next: The #insert method!

I notice that you're checking if self.root is nil. In ruby, then the root refersthere's a slightly faster (IIRC) and much more ruby way of doing this: self.root.nil?. It's a neat, built-in nil check. In addition, there's no reason to everything elsemodify @root using its accessor, you can actually just modify it directly.

ButAlso, I will trynoticed that wherever you return a value, you're either returning the root, or the node that was passed in. I also note that you're always setting the node that was passed in as the root. So, you're actually always comparing to understand how you've done thisroot. With that in mind, here are some little bits of cleanup (incomplete, I'll come back and howfinish it can be improved.):

def insert(value, node)
  # When this occurs, it will set @root.value == node.value
  @root = Node.new(value) if @root.nil? 

  return @root if @root.value == value

  if node.value > value
    if node.left_child.nil?
      node.left_child = Node.new(value)
    else 
      insert(value, node.left_child) 
    end
  else
    if node.right_child.nil?
      node.right_child = Node.new(value)
    else 
      insert(value, node.right_child) 
    end
  end
  return node
end

Other notes

Here's an interesting example of how someone else implemented BSTs in ruby

My first thought upon seeing this class is that it isn't really necessary. In a binary search tree, it's sufficient to keep track of the root, then the root refers to everything else.

But, I will try to understand how you've done this and how it can be improved.

Note: (Partially note to self) This probably isn't the fully best way to do this, the validation method should validate behavior rather than class. I should write more about that.

First off, I think that BST isn't that great of a name for this class. I'd go with Tree, because that is what it stores.

Anyways, first thing first: I'd make it possible to pass root to the initializer by making it an argument with a default value:

def initialize(root = nil)
  @root = root
end

Next thing's next: The #insert method!

I notice that you're checking if self.root is nil. In ruby, there's a slightly faster (IIRC) and much more ruby way of doing this: self.root.nil?. It's a neat, built-in nil check. In addition, there's no reason to modify @root using its accessor, you can actually just modify it directly.

Also, I noticed that wherever you return a value, you're either returning the root, or the node that was passed in. I also note that you're always setting the node that was passed in as the root. So, you're actually always comparing to root. With that in mind, here are some little bits of cleanup (incomplete, I'll come back and finish it):

def insert(value, node)
  # When this occurs, it will set @root.value == node.value
  @root = Node.new(value) if @root.nil? 

  return @root if @root.value == value

  if node.value > value
    if node.left_child.nil?
      node.left_child = Node.new(value)
    else 
      insert(value, node.left_child) 
    end
  else
    if node.right_child.nil?
      node.right_child = Node.new(value)
    else 
      insert(value, node.right_child) 
    end
  end
  return node
end

Other notes

Here's an interesting example of how someone else implemented BSTs in ruby

Source Link

created Dec 26, 2017 at 12:30

thesecretmaster

I'll be writing this review assuming that BST stands for Binary Search Tree, and that you're only concerned with constructing the tree, not searching through it. With that in mind, let's start:

Node class

First, for the easy part: in your definition of Node#initialize, you've got a space between the method name and the parenthesis initialize (. While ruby read that fine (it'll even work if you take out the parenthesis all together), it's considered best practice to put the parenthesis right up against the method name, so def initialize(value).

Different methods of dealing with the children

Also, you do not need to initialize @left_child and @right_child to nil. Instance variables do not need to be initialized. If you try and manipulate an uninitialized instance variable, it will behave as if it is set to nil. So, you can simply exclude @left_child and @right_child from your Node#initialize method.

However, if you wanted to allow them to be passed in optionally, you can use arguments or parameters with default values. Here's an example of parameters with default values:

def initialize(value, left_child = nil, right_child = nil)
  @value = value
  @left_child = left_child
  @right_child = right_child
end

and here's and example with hash arguments with defaults:

def initialize(value, left_child: nil, right_child: nil)
  @value = value
  @left_child = left_child
  @right_child = right_child
end

I personally prefer the second, because in that case you could easily pass a right_child without the left_child and vise versa. Otherwise, to pass a right_child, you'd need to pass nil for left_child.

Also, you may want to validate that @left_child and @right_child are both Nodes. In that case, you would want to define attr_readers for those variables and not attr_accessors. You would manually define the accessors like so:

def left_child=(left_child)
  if left_child.is_a? Node
    @left_child = left_child
  else
    # Some handling for invalid left children, e.g.
    throw "Invalid left child: #{left_child}"
  end
end

and the same for @right_child. You could even do it for value too! Or, if you wanted to get fancier, you could define a private validate_node method to avoid duplication in left_node= and right_node=:

def left_child=(left_child)
  @left_child = validate_node(left_child)
end

def right_child=(right_child)
  @right_child = validate_node(right_child)
end

private

def validate_node(node)
  if node.is_a? Node
    node
  else
    throw "You've passed an invalid node: #{node}"
  end
end

In case you didn't know, private methods are methods that (without some ruby magic) cannot be called outside of that class. They are private to that class.

I think that's all for the Node class, so let's move onward!

BST Class

My first thought upon seeing this class is that it isn't really necessary. In a binary search tree, it's sufficient to keep track of the root, then the root refers to everything else.

But, I will try to understand how you've done this and how it can be improved.