class Bstree::Node

Attributes

left[RW]
parent[RW]
right[RW]
val[RW]

Public Class Methods

new(val, parent=nil) click to toggle source
# File lib/bstree/node.rb, line 5
def initialize(val, parent=nil)
  @val = val
  @parent = parent
  @left = nil
  @right = nil
end

Public Instance Methods

insert(new_val) click to toggle source
# File lib/bstree/node.rb, line 12
def insert(new_val)
  if new_val > val
    if right
      right.insert(new_val)
    else
      @right = Bstree::Node.new(new_val, self)
    end
  elsif new_val < val
    if left
      left.insert(new_val)
    else
      @left = Bstree::Node.new(new_val, self)
    end
  end
end
remove(rem_val) click to toggle source
# File lib/bstree/node.rb, line 40
def remove(rem_val)
  node = search(rem_val)

  if node
    if node.left && node.right
      swap_val = node.right.minimum_val
      node.right.remove(swap_val)
      node.val = swap_val
      true

    elsif node.left
      node.left.parent = node.parent
      node.parent.left = node.left
      true

    elsif node.right
      node.right.parent = node.parent
      node.parent.right = node.right
      true

    else
      if node.val > node.parent.val
        node.parent.right = nil
        true
      elsif node.val < node.parent.val
        node.parent.left = nil
        true
      end
    end
  else
    false
  end
end
to_in_order_array(vals = []) click to toggle source
# File lib/bstree/node.rb, line 74
def to_in_order_array(vals = [])
  if left
    left.to_in_order_array(vals)
  end

  vals << val

  if right
    right.to_in_order_array(vals)
  end

  vals
end

Protected Instance Methods

minimum_val() click to toggle source
# File lib/bstree/node.rb, line 90
def minimum_val
  if left
    left.minimum_val
  else
    val
  end
end