| removeNode tree |

removeNode := [:root :elem |
    | node branch left middle right target neighbor merged keys
     bIndex eIndex path branchOf keysOf fixKeysOf |

    root first == #L
        ifTrue: [
            eIndex := root indexOf: elem.
            eIndex = 0 ifTrue: [^nil] ifFalse: [root := root copyWithoutIndex: eIndex]]
        ifFalse: [
            path := OrderedCollection new.
            node := root.
            keysOf := [:val | val first == #L ifTrue: [nil] ifFalse: [val second]].
            branchOf := [:val | val first == #L ifTrue: [val] ifFalse: [val third]].
            fixKeysOf := [:nde |
                (keysOf value: nde) ifNotNilDo: [:kys |
                    kys become: {#K}, (((branchOf value: nde) allButFirst: 2) collect: [:br |
                        [br first == #L] whileFalse: [br := (branchOf value: br) second].
                        br second])]].
            [   keys := keysOf value: node.
                keys ifNil: [target := node] ifNotNil: [
                    branch := branchOf value: node.
                    bIndex := keys findLast: [:key | (key isSymbol ifTrue: [0] ifFalse: [key]) <= elem].
                    bIndex = 0 ifTrue: [^nil].
                    target := branch at: bIndex + 1].
                target first = #L] whileFalse: [path add: node. node := target].

            eIndex := target indexOf: elem ifAbsent: [^nil].
            target become: (target copyWithoutIndex: eIndex).
            (bIndex > 2 and: [eIndex = 2]) ifTrue: [keys at: bIndex put: target second].

            [   left := branch second.
                middle := branch size > 2 ifTrue: [branch third] ifFalse: [nil].
                right := branch size = 4 ifTrue: [branch fourth] ifFalse: [nil].

                (branchOf value: target) size = 2 ifTrue: [
                    neighbor := target caseOf: {[left]->[middle]. [middle]->[left]. [right]->[middle]}.
                    merged := target == left
                        ifTrue: [(branchOf value: target), (branchOf value: neighbor) allButFirst]
                        ifFalse: [(branchOf value: neighbor), (branchOf value: target) allButFirst].
                    (branchOf value: neighbor) size = 3
                        ifTrue: [
                            (branchOf value: neighbor) become: merged.
                            branch become: (branch copyWithout: target)]
                        ifFalse: [
                            target == left ifTrue: [target := neighbor flag: (neighbor := target)].
                            (branchOf value: target) become: ({target first}, (merged allButFirst: 3)).
                            fixKeysOf value: target.
                            (branchOf value: neighbor) become: (merged allButLast: 2)].
                        fixKeysOf value: neighbor].
                fixKeysOf value: node.
                branch size = 2 ifFalse: [false] ifTrue: [
                    path ifEmpty: [node become: branch last. false] ifNotEmpty: [
                        target := node.
                        node := path removeLast.
                        branch := node third.
                        true]]
            ] whileTrue].
    root].

World findATranscript: nil.
tree := #(N (K 28 55)
   (B (N (K 10 19)
         (B (N (K 4 7)
               (B (L  1  2  3) (L  4  5  6) (L  7  8  9)))
            (N (K 13 16)
               (B (L 10 11 12) (L 13 14 15) (L 16 17 18)))
            (N (K 22 25)
               (B (L 19 20 21) (L 22 23 24) (L 25 26 27)))))
      (N (K 37 46)
         (B (N (K 31 34)
               (B (L 28 29 30) (L 31 32 33) (L 34 35 36)))
            (N (K 40 43)
               (B (L 37 38 39) (L 40 41 42) (L 43 44 45)))
            (N (K 49 52)
               (B (L 46 47 48) (L 49 50 51) (L 52 53 54)))))
      (N (K 64 73)
         (B (N (K 58 61)
               (B (L 55 56 57) (L 58 59 60) (L 61 62 63)))
            (N (K 67 70)
               (B (L 64 65 66) (L 67 68 69) (L 70 71 72)))
            (N (K 76 79)
               (B (L 73 74 75) (L 76 77 78) (L 79 80 81))))))).

(1 to: 81) asArray shuffled do: [:each |
    tree := removeNode value: tree value: each.
    Transcript cr; show: each asString, ', ', (tree printString copyWithout: $#)]

class B(list):
  def __str__(self):
    return '(B %s)' % '\n'.join([str(i) for i in self]).replace('\n', '\n   ')

  def delete(self, i, k):
    if isinstance(self[i], N):
      self[i].delete0(k)
      if len(self[i].b) < 2:
        if i == 0:
          if len(self[i+1].b) == 3:
            self[i].b.append(self[i+1].b.pop(0))
            self[i+1].k = self[i+1].getk()
          else:
            self[i].b.extend(self[i+1].b)
            self.pop(i+1)
          self[i].k = self[i].getk()
        else:
          if len(self[i-1].b) == 3:
            self[i].b.insert(0, self[i-1].b.pop())
            self[i].k = self[i].getk()
          else:
            self[i-1].b.extend(self[i].b)
            self.pop(i)
          self[i-1].k = self[i-1].getk()
    else:
      self[i].remove(k)
      if len(self[i]) < 2:
        if i == 0:
          if len(self[i+1]) == 3:
            self[i].append(self[i+1].pop(0))
          else:
            self[i].extend(self.pop(i+1))
        else:
          if len(self[i-1]) == 3:
            self[i].insert(0, self[i-1].pop())
          else:
            self[i-1].extend(self.pop(i))

class L(list):
  def __str__(self):
    return '(L %s)' % ' '.join(['%2d' % i for i in self])

  def delete(self, k):
    self.remove(k)
    return self

class K(list):
  def __str__(self):
    return '(K %s)' % ' '.join(['%d' % i for i in self])

class N:
  def __init__(self, k=None, b=None):
    self.k = k
    self.b = b

  def __str__(self):
    return '(N %s\n   %s)' % (self.k, str(self.b).replace('\n', '\n   '))

  def delete(self, k):
    self.delete0(k)
    if len(self.b) < 2:
      return self.b[0]
    return self

  def delete0(self, k):
    for i, j in enumerate(self.k+[0x100000000]):
      if k < j:
        self.b.delete(i, k)
        self.k = self.getk()
        break

  def getk(self):
    if isinstance(self.b[0], L):
      return K([l[0] for l in self.b[1:]])
    else:
      def getmin(n):
        if isinstance(n.b[0], L):
          return n.b[0][0]
        return getmin(n.b[0])
      return K([getmin(n) for n in self.b[1:]])

def mk_data():
  r = [N(b=B([L([i, i+1, i+2]) for i in range(j, j+9, 3)])) for j in range(1, 81, 9)]
  for i in r:
    i.k = i.getk()
  r = [N(b=B(r[i*3:i*3+3])) for i in range(3)]
  for i in r:
    i.k = i.getk()
  r = N(b=B(r))
  r.k = r.getk()
  return r

def test(l):
  root = mk_data()
  print root, '\n'
  for i in l:
    root = root.delete(i)
    print 'del = %d\n%s\n' % (i, root)

if __name__ == '__main__':
  from random import shuffle

  test(range(1, 82))
  test(range(81, 0, -1))
  l = range(1, 82)
  shuffle(l)
  test(l)

use strict;
use warnings;
use Btrees;
use YAML::Syck;

my $nodes = shift || 8;
sub comp{ $_[0] <=> $_[1]}
my ($tree, $node);
($tree, $node) = bal_tree_add($tree, $_, \&comp) for (1..$nodes);

for (1..$nodes){
    ($tree, $node) = bal_tree_del($tree, $_, \&comp);
    print YAML::Syck::Dump($tree);
}

#!/usr/bin/ruby
require 'forwardable'
require 'pp'

#
# BPlusTree class
#
class BPlusTree
  extend Forwardable
  def_delegators :@tree, :root, :add, :delete, :get, :to_a, :disp
  attr_accessor :tree

  def initialize(param = {})
    @tree = BPlusTree.new(param)
  end

  def BPlusTree.new_from_assoc(assoc, param = {})
    ret = new(param)
    ret.tree = BPlusTree.new_from_assoc(assoc, param)
    return ret
  end


  class BPlusTree
    attr_accessor :root, :param

    def initialize(param = {})
      self.param = param
      self.root = Leaf.new(self.param)
    end

    def BPlusTree.new_from_assoc(assoc, param = {})
      new(param).create_bptree_from_assoc(assoc)
    end

    def add(key, value)
      ret, _ = self.root.add(key, value)
      increase_height if ret == :need_split
      return key
    end

    def delete(key)
      ret, di = self.root.delete(key)
      if ret == :need_balance and self.root.suitable_root? then
        decrease_height
      end
      return((di.nil?) ? nil : key)
    end

    def get(key)
      self.root.get(key)
    end

    def to_a
      self.root.to_a
    end

    def disp(with_data = false)
      self.root.disp(0, with_data)
    end

    def create_bptree_from_assoc(assoc)
      raise 'Multiple root node occured' if assoc.size > 1
      type, key, data = assoc[0]
      root = {:leaf => Leaf, :branch => Branch}[type].new_from_assoc(assoc[0])
      root.connect_nextp(nil)
      self.root = root
      return self
    end


    private
    def increase_height
      # create a new root
      newroot = Branch.new(self.param)

      # connect children to new root
      lbrother = self.root
      bbrother = self.root.split
      (newroot.add_child(lbrother).nil?  and
       newroot.add_child(bbrother).nil?) or
        raise("#{self.class}#increase_height: Internal error")

      self.root = newroot
    end

    def decrease_height
      self.root = self.root.get_child
    end
  end


  class Node
    attr_accessor :key, :param

    def initialize(param = {})
      self.key = []
      self.param = param

      @param[:maxentry]  ||= 3
      @param[:maxbranch] ||= 3
      @param[:minentry]  ||= (@param[:maxentry]  + 1) / 2
      @param[:minbranch] ||= (@param[:maxbranch] + 1) / 2

      return self
    end

    def maxentry
      @param[:maxentry]
    end
    def maxbranch
      @param[:maxbranch]
    end
    def minentry
      @param[:minentry]
    end
    def minbranch
      @param[:minbranch]
    end


    def min
      return self.key.first
    end

    protected
    def search_insert_pos(key)
      for i in 0..self.key.size - 1
        return i if key < self.key[i]
      end
      return self.key.size
    end
  end


  class Leaf < Node
    attr_accessor :data, :nextp

    def initialize(param = {})
      self.data = []
      self.nextp = nil
      super
    end

    def Leaf.new_from_assoc(assoc, param = {})
      new(param).create_bptree_from_assoc(assoc)
    end

    def add(key, value)
      before = search_insert_pos(key)
      self.key[before, 0]  = key
      self.data[before, 0] = value

      ret = nil
      ret = :need_split if self.key.size > self.maxentry
      return [ret, before]
    end

    def delete(key)
      pos = search_key(key)
      return [nil, nil] if pos.nil?

      self.key.delete_at(pos)
      self.data.delete_at(pos)

      ret = nil
      ret = :need_balance if self.key.size < self.minentry
      return [ret, pos]
    end

    def get(key)
      pos = search_key(key)
      return nil if pos.nil?
      return self.data[pos]
    end

    def to_a
      ret = self.key.zip(self.data)
      return ret if self.nextp.nil?
      return ret +  self.nextp.to_a
    end

    def disp(level, with_data = false)
      indent = '  ' * level
      print indent + '- Leaf' + ((level == 0) ? '(root)' : '') + ' ['
      print self.key.zip(self.data).inject('') {|before, (k, d)|
          if before.empty? then
            k.to_s + (with_data ? ':' + d.to_s : '')
          else
            before + ', ' + k.to_s + (with_data ? ':' + d.to_s : '')
          end
        }
      puts ']'
    end

    def pretty_print(pp)
      pp.group(1, '#<B+T::Leaf', '>') do
        pp.breakable
        pp.text('key:')
        pp.pp(self.key)
        pp.breakable
        pp.text('data:')
        pp.pp(self.data)
      end
    end


    def split
      range = (self.key.size / 2) .. self.key.size - 1

      sibling = Leaf.new(self.param)
      sibling.key[0, 0] = self.key[range]
      sibling.data[0, 0] = self.data[range]
      self.key[range] = nil
      self.data[range] = nil
      sibling.nextp = self.nextp
      self.nextp = sibling

      return sibling
    end

    def balance(bigbrother)
      if self.key.size + bigbrother.key.size <= self.maxentry then
        return :need_integrate
      end
      if self.key.size + bigbrother.key.size >  self.maxentry * 2 then
        raise "#{self.class}#balance: Internal error"
      end

      newkey  = self.key.dup + bigbrother.key
      newdata = self.data.dup + bigbrother.data
      keys = newkey.size
      boundary = keys / 2

      self.key        = newkey[0..boundary-1]
      bigbrother.key  = newkey[boundary..keys-1]

      self.data       = newdata[0..boundary-1]
      bigbrother.data = newdata[boundary..keys-1]

      return nil
    end

    def integrate(bigbrother)
      self.key  += bigbrother.key
      self.data += bigbrother.data
      self.nextp = bigbrother.nextp
      bigbrother.nextp = nil

      raise "#{self.class}: Internal error" if self.key.size > self.maxentry
      return nil
    end

    def get_child
      return self
    end

    def suitable_root?
      return true
    end

    def create_bptree_from_assoc(assoc)
      type, key, data = assoc
      unless type == :leaf then
        raise "#{self.class}#create_bptree_from_assoc: Internal error"
      end
      self.key = key
      self.data = data
      return self
    end

    def connect_nextp(before = nil)
      before.nextp = self unless before.nil?
      return self
    end


    private
    def search_key(key)
      for i in 0..self.key.size - 1
        return i if self.key[i] == key
      end
      return nil
    end
  end


  class Branch < Node
    attr_accessor :branch

    def initialize(param = {})
      self.branch = []
      super
    end

    def Branch.new_from_assoc(assoc, param = {})
      new(param).create_bptree_from_assoc(assoc)
    end

    def add(key, value)
      bi = search_branch(key)
      child = self.branch[bi]
      ret, before = child.add(key, value)
      self.key[bi] = child.key[before] if before == 0

      return [nil, bi] if ret.nil?
      raise "#{self.class}#add: Internal error" unless ret == :need_split

      # split child
      bbrother = child.split
      ret = self.add_child(bbrother)

      return [ret, bi] if ret.nil? or ret == :need_split
      raise "#{self.class}#add: Internal error"
    end

    def delete(key)
      bi = search_branch(key)
      child = self.branch[bi]
      ret, di = child.delete(key)
      self.key[bi] = child.key[di] if di == 0

      bj = nil
      until ret.nil?
        case ret
        when :need_balance
          # choose pair.
          bi, bj = self.choose_pair(bi)
          lbrother, bbrother = self.branch[bi..bj]

          # balance pair
          ret = lbrother.balance(bbrother)
          self.key[bj] = bbrother.min
        when :need_integrate
          # remove big-brother
          self.branch.delete_at(bj)
          self.key.delete_at(bj)

          # integrate pair
          ret = lbrother.integrate(bbrother)
        else
          raise "#{self.class}#delete: Internal error"
        end
      end

      ret = nil
      ret = :need_balance if self.key.size < self.minbranch
      return [ret, bi]
    end

    def get(key)
      bi = search_branch(key)
      return self.branch[bi].get(key)
    end

    def to_a
      return self.branch[0].to_a
    end

    def disp(level, with_data = false)
      indent = '  ' * level
      puts indent + '- Branch' + (level == 0 ? '(root)' : '') + ' [' +
        self.key.inject('') {|before, k|
          if before.empty? then
            "(#{k})"
          else
            before + ", #{k}"
          end
        } + ']'
      self.branch.map do |branch|
        branch.disp(level + 1, with_data)
      end
    end

    def pretty_print(pp)
      pp.group(1) do
        pp.text('#<B+T::Branch')
        pp.breakable
        pp.group(1, 'key:[', ']') do
          self.key.inject(false) do |before, key|
            pp.comma_breakable if before
            pp.pp(key)
            true
          end
        end

        pp.breakable
        pp.text('branch:')
      end

      pp.nest(1) do
        pp.breakable
        pp.group(1, '[', ']') do
          self.branch.inject(false) do |before, branch|
            pp.comma_breakable if before
            pp.pp(branch)
            true
          end
        end
      end

      pp.text('>')
    end


    def add_child(child)
      before = search_insert_pos(child.min)
      self.key[before, 0] = child.min
      self.branch[before, 0] = child

      return :need_split if self.key.size > self.maxbranch
      return nil
    end

    def split
      range = (self.key.size / 2) .. self.key.size - 1

      sibling = Branch.new(self.param)
      sibling.key[0, 0] = self.key[range]
      sibling.branch[0, 0] = self.branch[range]

      self.branch[range] = nil
      self.key[range] = nil

      return sibling
    end

    def balance(bigbrother)
      if self.key.size + bigbrother.key.size <= self.maxbranch then
        return :need_integrate
      end
      if self.key.size + bigbrother.key.size >  self.maxbranch * 2 then
        raise "#{self.class}#balance: Internal error"
      end

      # newkeyとnewbranchには，maxbranch * 2個の要素を置くための空間が必要
      newkey    = self.key.dup + bigbrother.key
      newbranch = self.branch.dup + bigbrother.branch
      keys = newkey.size
      boundary = keys / 2

      self.key       = newkey[0..boundary-1]
      bigbrother.key = newkey[boundary..keys-1]

      self.branch       = newbranch[0..boundary-1]
      bigbrother.branch = newbranch[boundary..keys-1]

      return nil
    end

    def integrate(bigbrother)
      for i in 0..bigbrother.key.size - 1
        self.add_child(bigbrother.branch[i])
      end

      raise "#{self.class}: Internal error" if self.key.size > self.maxbranch
      return nil
    end

    def get_child
      raise "#{self.class}#get_child: Internal error" if self.key.size != 1
      return self.branch[0]
    end

    def suitable_root?
      return true if self.key.size <= 1
      return false
    end

    def choose_pair(lbrother_idx)
      lbrother_idx -= 1 if lbrother_idx == self.key.size - 1
      bbrother_idx = lbrother_idx + 1
      raise "#{self.class}#choose_pair: Internal error" if key.size < 2
      return [lbrother_idx, bbrother_idx]
    end

    def create_bptree_from_assoc(assoc)
      type, key, branch = assoc
      unless type == :branch then
        raise "#{self.class}#create_bptree_from_assoc: Internal error"
      end
      self.key = key
      self.branch = branch.map do |child|
        {:leaf => Leaf, :branch => Branch}[child.first].new_from_assoc(child)
      end
      return self
    end

    def connect_nextp(before = nil)
      self.branch.inject(before) do |before, branch|
        branch.connect_nextp(before)
      end
    end


    private
    def search_branch(key)
      for i in 1..self.key.size - 1
        return i - 1 if key < self.key[i]
      end
      return self.key.size - 1
    end
  end
end

###########################################################################
# deleting test

puts '[Delete test 1]'
puts

assoc =
[[:branch, [1, 28, 55],
  [[:branch, [1, 10, 19],
    [[:branch, [1, 4, 7],
      [[:leaf, [1, 2, 3], ["data01", "data02", "data03"]],
       [:leaf, [4, 5, 6], ["data04", "data05", "data06"]],
       [:leaf, [7, 8, 9], ["data07", "data08", "data09"]]]],
     [:branch, [10, 13, 16],
      [[:leaf, [10, 11, 12], ["data10", "data11", "data12"]],
       [:leaf, [13, 14, 15], ["data13", "data14", "data15"]],
       [:leaf, [16, 17, 18], ["data16", "data17", "data18"]]]],
     [:branch, [19, 22, 25],
      [[:leaf, [19, 20, 21], ["data19", "data20", "data21"]],
       [:leaf, [22, 23, 24], ["data22", "data23", "data24"]],
       [:leaf, [25, 26, 27], ["data25", "data26", "data27"]]]]]],
   [:branch, [28, 37, 46],
    [[:branch, [28, 31, 34],
      [[:leaf, [28, 29, 30]