Method: Xunch::RBTree#lower_node

Defined in:

lib/xunch/utils/rb_tree.rb

#lower_node(key) ⇒ Object

# File 'lib/xunch/utils/rb_tree.rb', line 204

def lower_node(key)
  p = @root;
  while p != nil
    cmp = compare_key(key, p.key)
    if cmp > 0
      if p.right != nil
        p = p.right
      else
        if p == nil
          return nil
        else
          return RBTree::ImmutableNode.new(p.key,p.value)
        end
      end
    else
      if p.left != nil
        p = p.left
      else
        parent = p.parent
        ch = p
        while parent != nil && ch == parent.left
          ch = parent
          parent = parent.parent;
        end
        if parent == nil
          return nil
        else
          return RBTree::ImmutableNode.new(parent.key,parent.value)
        end
      end
    end
  end
  return nil
end