Class: ConcurrentRedBlackTree::ConcurrentNode

Inherits:

Node

• Object
• Node
• ConcurrentRedBlackTree::ConcurrentNode

Defined in:

lib/red_black_tree.rb

Defined Under Namespace

Classes: EmptyConcurrentNode

Constant Summary

LEFT =

direction: ~LEFT == RIGHT, ~RIGHT == LEFT

-1

RIGHT =

0

Instance Method Summary

• #delete(key) ⇒ Object
• #insert(key, value) ⇒ Object
• #retrieve(key) ⇒ Object

Instance Method Details

#delete(key) ⇒ Object

# File 'lib/red_black_tree.rb', line 599

def delete(key)
  case key <=> @key
  when -1
    dir = LEFT
  when 0
    deleted = self
    node, rebalance = delete_node
  when 1
    dir = RIGHT
  else
    raise TypeError, "cannot compare #{key} and #{@key} with <=>"
  end
  if dir
    deleted, target, rebalance = child(dir).delete(key)
    node = new_child(dir, target)
    if rebalance
      node, rebalance = node.rebalance_for_delete(dir)
    end
  end
  [deleted, node, rebalance]
end

#insert(key, value) ⇒ Object

# File 'lib/red_black_tree.rb', line 563

def insert(key, value)
  case key <=> @key
  when -1
    dir = LEFT
  when 0
    node = new_value(value)
  when 1
    dir = RIGHT
  else
    raise TypeError, "cannot compare #{key} and #{@key} with <=>"
  end
  if dir
    target = child(dir).insert(key, value)
    node = new_child(dir, target)
    if black? and child(~dir).black? and target.red? and !target.children_color?(:BLACK)
      node = node.rebalance_for_insert(dir)
    end
  end
  node.pullup_red
end

#retrieve(key) ⇒ Object

# File 'lib/red_black_tree.rb', line 585

def retrieve(key)
  case key <=> @key
  when -1
    @left.retrieve(key)
  when 0
    @value
  when 1
    @right.retrieve(key)
  else
    nil
  end
end