btree.rb

btree.rb

class AbstractNode
  @@root = nil

  def initialize(n, keys, parent)
    @slot = n
    @keys = keys
    @parent = parent
    @@root = self unless @@root
  end

  attr_writer :parent

  def root
    @@root
  end

  def position(k)
    i = 0
    @keys.each do |key|
      break if(k < key)
      i = i + 1
    end
    i
  end

  def balance
    len = @keys.length
    if(len > @slot)
      prepare_balance
      m = len / 2
      ck = @keys[m]
      left, right = split(m)
      @parent.balance_parent(ck, left, right, self)
    end
  end

  def prepare_balance
    #log
    unless @parent
      @parent = Node.new(@slot, [], nil, [])
      @@root = @parent
    end
  end

  def search(k)
    i = 0
    @keys.each do |key|
      return k if(k == key)
      break if(k < key)
      i += 1
    end
    search_children(k, i)
  end

  def log
    len = @keys.length
    p "len: #{len}"
    p "keys: " + @keys.to_s
    p "@slot: #{@slot}"
    m = len / 2
    p "m: " + m.to_s
    mk = @keys[m]
    p "mk: " + mk.to_s
  end
end

class Node < AbstractNode
  def initialize(n, keys, parent, children)
    super(n, keys, parent)
    @children = children
    @children.each do |c|
      c.parent = self
    end
  end

  def search_children(k, i)
    return nil unless @children[i]
    @children[i].search(k)
  end

  def insert(k)
    pos = position(k)
    c = @children[pos]
    c.insert(k)
  end

  def split(m)
    left = Node.new(@slot, @keys[0..m-1], @parent, @children[0..m])
    right = Node.new(@slot, @keys[[email protected]], 
                     @parent, @children[m+1, @children.length-1])
    @keys.delete_at(m)
    return left, right
  end

  def balance_parent(k, left, right, child) 
    pos = position(k)
    @keys.insert(pos, k)
    merge_children(pos, left, right)
    @children.delete(child)
    balance
  end

  def merge_children(pos, left, right)
    @children.insert(pos, left);
    @children.insert(pos + 1, right)
  end

  def dump(indent)
    puts indent + "Node: #{@keys.to_s} self: #{self} @parent=#{@parent}"
    @children.each do |c|
      c.dump("  " << indent) if c
    end
  end
end

class Leaf < AbstractNode
  def initialize(n, keys, parent)
    super(n, keys, parent)
  end

  def insert(k)
    pos = position(k)
    @keys.insert(pos, k)
    balance
  end

  def search_children(k, i)
    nil
  end

  def split(m)
    left = Leaf.new(@slot, @keys[0..m-1], @parent)
    right = Leaf.new(@slot, @keys[[email protected]], @parent)
    @keys.delete_at(m)
    return left, right
  end

  def dump(indent)
    puts indent + "Leaf: #{@keys.to_s} @parent=#{@parent}"
  end
end

l = Leaf.new(4, [], nil)
(1..80).each do |i|
  l.root.insert(i)
  l.root.dump("")
  puts 
end

root = l.root
puts "root.search(27): #{root.search(27)}"
puts "root.search(80): #{root.search(80)}"
puts "root.search(81): #{root.search(81)}"