class Tree::BST

This is implementation Binary search tree using Tree::BinaryNode

Attributes

length[R]

Public Class Methods

new() click to toggle source
# File lib/data_struct/tree.rb, line 26
def initialize
  @root = nil
  @length, @height = 0
  @state_arr = []
end

Public Instance Methods

delete(key, node = @root) click to toggle source
# File lib/data_struct/tree.rb, line 50
def delete(key, node = @root)
  return @root = node if node.nil?

  if key < node.data 
    node.left = delete(key, node.left)
  elsif key > node.data 
    node.right = delete(key, node.right)
  else
    if node.left.nil?
      temp = node.right
      node = nil
      return temp
    elsif node.right.nil?
      temp = node.left
      node = nil
      return temp
    end

    temp = min(node.right)
    node.data = temp.data
    node.right = delete(temp.data, node.right)
  end
  @root = node
end
empty?() click to toggle source
# File lib/data_struct/tree.rb, line 80
def empty? 
  @length.zero?
end
find(val) click to toggle source
# File lib/data_struct/tree.rb, line 74
def find val
  recur_search @root, val
end
height?() click to toggle source
# File lib/data_struct/tree.rb, line 83
def height?
  recur_max_depth @root
end
insert(val) click to toggle source
# File lib/data_struct/tree.rb, line 32
def insert val
  in_length
  @root = recur_insert @root, val
end
max(node = @root) click to toggle source
# File lib/data_struct/tree.rb, line 43
def max(node = @root)
  cur = node
  unless node.right.nil?
    cur = cur.right
  end
  cur
end
min(node = @root) click to toggle source
# File lib/data_struct/tree.rb, line 36
def min(node = @root)
  cur = node
  unless node.left.nil?
    cur = cur.left
  end
  cur
end
to_a() click to toggle source
# File lib/data_struct/tree.rb, line 77
def to_a
  recur_pre_order @root, []
end

Private Instance Methods

de_length() click to toggle source
# File lib/data_struct/tree.rb, line 131
def de_length
  @length -= 1
end
in_length() click to toggle source
# File lib/data_struct/tree.rb, line 127
def in_length
  @length += 1
end
recur_insert(node, val) click to toggle source
# File lib/data_struct/tree.rb, line 88
def recur_insert node, val
  return BinaryNode.new(val) if node.nil? 
  if val < node.data
    node.left = recur_insert(node.left, val)
  elsif val > node.data
    node.right = recur_insert(node.right, val)
  end
  node
end
recur_max_depth(node) click to toggle source
# File lib/data_struct/tree.rb, line 116
def recur_max_depth node
  return 0 if node.nil?
  left_depth = recur_max_depth(node.left)
  right_depth = recur_max_depth(node.right)

  if left_depth > right_depth
    return left_depth + 1
  else
    return right_depth + 1
  end
end
recur_pre_order(node, state) click to toggle source
# File lib/data_struct/tree.rb, line 109
def recur_pre_order node, state
  return if node.nil?
  state << node.data
  recur_pre_order(node.left, state) 
  recur_pre_order(node.right, state)
  state
end