B-Tree

Node.rb

class Node
  attr_accessor :keys, :parent

  def initialize (p, key)
    # keys = [P0, K1 ,P1, K2, ...., Pn ]
    if key.class == Array
      @keys = key
    else
    @keys = [nil,key,nil]
  end
    @parent = p
  end   # end of Constructor of Node class


  def addKey key
    for k in @keys
      if k == nil or k.class == Node
        next
      elsif key < k
        i =@keys.index(k)
        @keys.insert(i, nil)
        @keys.insert(i,key)
        return i
      end
    end
    @keys.push(key)
    @keys.push(nil)
    return @keys.index(key)
  end  # end of addKey

  def delKey key
    for k in @keys
      if k == nil or k.class == Node
              next
      elsif key == k
        i = @keys.index(k)
        @keys.delete_at(i)
        @keys.delete_at(i)
        return true
      end
    end
    return false
  end

  def size # return NUmber of Keys
    return @keys.size()/2
  end  # end of size

end   #end of Node class

B_Tree.rb

require 'Node'

class B_Tree
  attr_accessor :Root
  def initialize m
    @Root = nil
    @M_WAY = m
  end  # end of Constructor of B_Tree class

  def depth node
    keys = node.keys
    ps= []
    for p in keys
      next if p.class == keys[1].class
      ps.push(depth(p)) if p != nil
    end
    return 1 if ps == []
    return 1+ps.max

  end

  def isFull node
    if node.size() >= @M_WAY-1
      return true
    else
      return false
    end
  end  # end of isFull

  def isUnder node
    if node.size() <= @M_WAY/2-1
      return true
    else
      return false
    end # end of isUnder
  end

  def inorder node
    if node == nil
      return
    end
    for k in node.keys
      if k.class ==Node
        inorder(k)
      elsif k == nil
        next
      else
        print k,"(",depth(node),") "
      end
    end
  end  # end of inorder

  def left_merge neighbor, parent, node
    keys, n_keys, p_keys = node.keys, neighbor.keys, parent.keys
    n_index = p_keys.index(neighbor)
    neighbor.addKey(p_keys[n_index+1])
    n_keys.pop
    neighbor.keys = n_keys + keys
    2.times {p_keys.delete_at(n_index+1)}
    for k in neighbor.keys
      if k.class == Node
        k.parent = neighbor
      end
    end
  end

  def right_merge  neighbor, parent, node
    keys, n_keys, p_keys = node.keys, neighbor.keys, parent.keys
    n_index = p_keys.index(node)
    node.addKey(p_keys[n_index+1])
    keys.pop
    node.keys = keys + n_keys
    2.times {p_keys.delete_at(n_index+1)}
    for k in node.keys
      if k.class == Node
        k.parent = node
      end
    end
  end

  def left_loan neighbor, parent, node
    p_keys , n_keys,keys = parent.keys, neighbor.keys,node.keys
    n_index = p_keys.index(node)
    node.addKey(p_keys[n_index-1])
    keys[0],keys[2] = keys[2],keys[0]
    p_keys[n_index-1] = n_keys[n_keys.size-2]
    keys[0] = n_keys[n_keys.size-1]
    keys[0].parent = node if keys[0] != nil
    neighbor.keys = n_keys.slice(0,n_keys.size() -2)
  end

  def right_loan neighbor, parent, node
    p_keys , n_keys,keys = parent.keys, neighbor.keys, node.keys
    n_index = p_keys.index(node)
    node.addKey(p_keys[n_index+1])
    p_keys[n_index+1] = n_keys[1]
    keys[keys.size-1] = n_keys[0]
    n_keys[0].parent =node if n_keys[0] != nil
    neighbor.keys = n_keys.slice(2,n_keys.size()-2)
  end

  def search skey
    cur_node = @Root
    found = false
    begin
      s_node = cur_node
      keys = cur_node.keys
      for k in keys
        cur_node = k if k == keys[keys.size-1]
        next if k.class == Node or k == nil
        if skey == k
          found = true
          break
        elsif skey < k
          cur_node = keys[keys.index(k)-1]
          break
        end       # end of if
      end         # end of for

    end while !found and cur_node!=nil
    return found, s_node
  end             # end of search

  def insert nkey
    if @Root == nil
      @Root = Node.new(nil,nkey)
      return true
    else
      # Tree 가 비어있지 않을 때
      duplicate, node = search(nkey)
      if duplicate
        puts "중복되는 데이터를 삽입하였습니다 #{nkey}"
        return false
      end
      newNode = nil
      while true # 잘 들어갈때 까지.
        unless isFull(node)
          # Node에 여유가 있을 때
          i=node.addKey(nkey)
          keys = node.keys()
          keys[i+1] = newNode
          return true
        else
          i=node.addKey(nkey)
          keys = node.keys()
          keys[i+1] = newNode
          if node.size % 2 == 0 : center_index = keys.size/2+1
          else center_index = keys.size/2
          end
          leftkeys = keys.slice(0,center_index)
          rightkeys = keys.slice(center_index+1,keys.size - center_index)
          node.keys = leftkeys
          newNode = Node.new(node.parent,rightkeys)
          tmpkeys = newNode.keys
          for p in tmpkeys
            if p.class == Node
              p.parent = newNode
            end
          end
          if node.parent == nil
            # 부모 노드가 존재하지 않을 때
            @Root = Node.new(nil,keys[center_index])
            rkeys = @Root.keys
            rkeys[0],rkeys[2] = node, newNode
            node.parent = newNode.parent = @Root
            return true
          else
            # 부모 노드가 존재할 경우
            nkey = keys[center_index]
            node = node.parent
          end # end of 부모노드가 존재하지 않을 때
        end   # end of 노드에 여유가 있을 때

      end     # end of while
    end       # end of 트리가 비어있지 않을 때
  end         # end of insert

  def delete dkey
    if @Root == nil
      puts "비어있는 트리입니다. " 
    end
    found, node = search(dkey)
    if not found
      puts "없는 키에대한 삭제입니다 #{dkey}"
      return false
    end
    keys = node.keys
    if keys[0] == nil
      #leaf Node일때
      node.delKey(dkey)
      @Root = nil if @Root.size() <1 
      return true if (not isUnder node) or nil == @Root
      # Under flow 처리 루틴
      parent = node.parent
      # LEAF 노드 삭제 하는거
      until parent == nil

        p_keys = parent.keys
        n_index = p_keys.index(node)
        if n_index != p_keys.size() -1
          #오른쪽 집에서 빌리기
          neighbor = p_keys[n_index+2]
          if neighbor.size()-1 > @M_WAY/2-1
            # 옆집이 부자면
            right_loan(neighbor, parent, node)
            return true
          else
            # 옆집도 거지면
            right_merge(neighbor, parent,node)
            grandson,parent ,node =node, parent.parent,parent
            return true if not isUnder node
          end

        else
          #왼쪽 집에서 빌리기
          neighbor = p_keys[n_index-2]
          # 오른쪽 집 없어서 왼쪽집
          if neighbor.size()-1 > @M_WAY/2-1
            # 왼쪽집 부자면
            left_loan(neighbor, parent, node)
            return true
          else
            # 왼쪽집 거지면
            left_merge(neighbor, parent,node)
            grandson, parent ,node = neighbor, parent.parent,parent
            return true if not isUnder node
          end
        end

      end
      #Root까지 왔을때 처리 하는거
      if @Root.size <1
        @Root = grandson
        grandson.parent = nil
      end
      return true
    else
      # leaf node 가 아닐때
      i=keys.index(dkey)
      p = keys[i+1]
      ch_node = p
      until p == nil
        ch_node = p
        ch_keys = p.keys
        p=ch_keys[0]
      end
      ckeys = ch_node.keys
      c_key = ckeys[1]
      delete(c_key)
      found, node = search(dkey)
      keys = node.keys
      i=keys.index(dkey)
      keys[i] = c_key
      return true
    end
  end

end    # end of B_Tree class