class DSA::BinarySearchTree

Public Instance Methods

[]=(key, value) click to toggle source
# File lib/DSA/binary_search_tree.rb, line 448
def []=(key, value)
  new_node = RedBlackTreeNode.new(key, value)
  if @root.nil?
    new_node.set_black!
    @root = new_node
  else
    node = insert(@root, new_node)
    fix_variance node if node.red? # when it is an existing node, it could be black
  end
end
bfs_print() click to toggle source

breadth first traversal

# File lib/DSA/binary_search_tree.rb, line 467
def bfs_print
  puts '=' * 100
  level = [@root]
  until level.empty?
    next_level = []
    level.each do |node|
      if node
        printf "<#{node.key}, #{node.value}>"
        printf "(#{node.parent.key}|" if node != @root
        if node.red?
          printf "R)\t"
        else
          printf "B)\t"
        end
        next_level.push node.left
        next_level.push node.right
      else
        printf "<Nil>\t"
        next_level.push nil
        next_level.push nil
      end
    end
    puts
    if next_level.count(nil) < next_level.length
      level = next_level
    else
      level = []
    end
  end
  puts '=' * 100
end
delete(key) click to toggle source
# File lib/DSA/binary_search_tree.rb, line 459
def delete(key)
  return nil if @root.nil?
  node = find_node @root, key
  return nil if node.nil?
  rb_delete_node(node).first.value
end

Private Instance Methods

deletion_restructure(node) click to toggle source

rotations and re-color in different cases(zig-zig and zig-zag) for deletion

# File lib/DSA/binary_search_tree.rb, line 581
def deletion_restructure(node)
  parent = node.parent
  grand_parent = parent.parent
  if left_child?(node) && left_child?(parent)
    right_up_rotation parent
    if grand_parent.red?
      parent.set_red!
    else
      parent.set_black!
    end
    node.set_black!
    grand_parent.set_black!
  elsif right_child?(node) && left_child?(parent)
    left_up_rotation node
    right_up_rotation node
    if grand_parent.red?
      node.set_red!
    else
      node.set_black!
    end
    parent.set_black!
    grand_parent.set_black!
  elsif right_child?(node) && right_child?(parent)
    left_up_rotation parent
    if grand_parent.red?
      parent.set_red!
    else
      parent.set_black!
    end
    node.set_black!
    grand_parent.set_black!
  else
    right_up_rotation node
    left_up_rotation node
    if grand_parent.red?
      node.set_red!
    else
      node.set_black!
    end
    parent.set_black!
    grand_parent.set_black!
  end
end
fix_deficit(sibling) click to toggle source

the heavier side after a black leaf deleted

# File lib/DSA/binary_search_tree.rb, line 517
def fix_deficit(sibling)
  parent = sibling.parent
  if sibling.black?
    x = has_red_child? sibling
    if x
      deletion_restructure(x)
    else # if sibling does not have a red child
      sibling.set_red!
      if parent.red?
        parent.set_black!
      else
        fix_deficit sibling_of(parent)
      end
    end
  else # when my sibling is red
    if left_child? sibling
      heavy_node = sibling.right
      right_up_rotation sibling
    else
      heavy_node = sibling.left
      left_up_rotation sibling
    end
    sibling.set_black!
    parent.set_red!
    fix_deficit heavy_node
  end
end
fix_variance(node) click to toggle source
# File lib/DSA/binary_search_tree.rb, line 555
def fix_variance(node)
  # for root, recolor to black when necessary
  if node == @root
    node.set_black! if node.red?
    return
  end

  parent = node.parent
  return if parent.black? # we are good

  # otherwise we have the double red
  grand_parent = parent.parent
  uncle = sibling_of parent

  if uncle && uncle.red?
    parent.set_black!
    uncle.set_black!
    grand_parent.set_red!
    fix_variance grand_parent
  else
    restructure( node )
  end

end
has_red_child?(node) click to toggle source
# File lib/DSA/binary_search_tree.rb, line 545
def has_red_child?(node)
  if node.left && node.left.red?
    node.left
  elsif node.right && node.right.red?
    node.right
  else
    nil
  end
end
left_up_rotation(node) click to toggle source
# File lib/DSA/binary_search_tree.rb, line 685
def left_up_rotation(node)
  parent = node.parent
  grand_parent = parent.parent

  node.parent = grand_parent
  if left_child? parent
    grand_parent.left = node
  elsif right_child? parent
    grand_parent.right = node
  else
    @root = node
  end

  parent.right = node.left
  node.left.parent = parent if node.left

  node.left = parent
  parent.parent = node

end
rb_delete_node(node) click to toggle source
# File lib/DSA/binary_search_tree.rb, line 500
def rb_delete_node(node)
  node, replace_node, sibling = delete_node(node)
  value = [node, replace_node]

  return value if node.red? # red is always fine
  if node.black?
    if replace_node # if it has a child(the replace_node), it must be red
      replace_node.set_black!
    else # it is a black leaf, it is complicated
      fix_deficit sibling
    end
  end

  value
end
restructure(node) click to toggle source

rotations and re-color in different cases(zig-zig and zig-zag) for insertion

# File lib/DSA/binary_search_tree.rb, line 626
def restructure(node)
  parent = node.parent
  grand_parent = parent.parent
  if left_child?(node) && left_child?(parent)
    right_up_rotation parent
    parent.set_black!
    node.set_red!
    grand_parent.set_red!
  elsif right_child?(node) && left_child?(parent)
    left_up_rotation node
    right_up_rotation node
    node.set_black!
    parent.set_red!
    grand_parent.set_red!
  elsif right_child?(node) && right_child?(parent)
    left_up_rotation parent
    parent.set_black!
    node.set_red!
    grand_parent.set_red!
  else
    right_up_rotation node
    left_up_rotation node
    node.set_black!
    parent.set_red!
    grand_parent.set_red!
  end
end
right_up_rotation(node) click to toggle source
# File lib/DSA/binary_search_tree.rb, line 664
def right_up_rotation(node)
  parent = node.parent
  grand_parent = parent.parent

  node.parent = grand_parent
  if left_child? parent
    grand_parent.left = node
  elsif right_child? parent
    grand_parent.right = node
  else
    @root = node
  end

  parent.left = node.right
  node.right.parent = parent if node.right

  node.right = parent
  parent.parent = node

end
sibling_of(node) click to toggle source
# File lib/DSA/binary_search_tree.rb, line 654
def sibling_of(node)
  parent = node.parent
  return nil if parent.nil?
  if left_child? node
    parent.right
  else
    parent.left
  end
end