algorithm_v4

binary_search_symbol_table.rb

#!/usr/bin/env ruby
class BSST
  def initialize(capacity = 2)
    @keys = Array.new(capacity)
    @vals = Array.new(capacity)
    @n = 0
  end

  def is_empty?
    @n == 0
  end

  def size
    @n
  end

  def resize n
    return nil if n < @n
    keys = Array.new(n)
    vals = Array.new(n)
    i = 0
    while i < @n
      keys[i] = @keys[i]
      vals[i] = @vals[i]
      i += 1
    end
    @keys = keys
    @vals = vals
  end

  def delete key
    return nil if is_empty?
    index = rank(key)
    if index < @n && @keys[index] == key
      j = index
      while j < @keys.length - 1
        @keys[j] = @keys[j+1]
        @vals[j] = @vals[j+1]
        j += 1
      end
      @keys[j] = nil
      @vals[j] = nil
    end
    @n -= 1
    if @n > 0 && @n < @keys.length / 4
      resize(@keys.length  / 2)
    end
  end

  # 用二分查找法返回符号表中 key 值比传入参数小的元素的个数
  # 是 BSST 的基础
  def rank key
    lo = 0
    hi = @n - 1
    while lo <= hi
      mid = (lo + hi) / 2
      if @keys[mid] > key
        hi = mid - 1
      elsif @keys[mid] < key
        lo = mid + 1
      else
        break mid
      end
    end
    lo
  end

  # 返回符号表中 key 对应的 value
  def get key
    return nil if is_empty?
    index = rank(key)
    if index < @n && @keys[index] == key
      @vals[index]
    else
      nil
    end
  end

  def put key, val
    if val.nil?
      delete(key)
    else
      index = rank(key)

      if index < @n && @keys[index] == key
        @keys[index] = val
      else
        if @n == @keys.length
          resize(2 * @n)
        end
        j = @n
        while j > index
          @keys[j] = @keys[j - 1]
          @vals[j] = @vals[j - 1]
          j -= 1
        end
        @keys[index] = key
        @vals[index] = val
        @n += 1
      end
    end
  end

  # 返回 keys 中等于或小于 key 的最大 key
  def floor key
    return nil if key.nil?
    i = rank(key)
    if i < @n && @keys[i] == key
      key
    elsif i == 0
      nil
    else
      @keys[i - 1]
    end

  end

  # 返回 keys 中等于或大于 key 的最小 key
  def ceiling key
    return nil if key.nil?
    i = rank(key)
    if i < @n && @keys[i] == key
      key
    elsif i == @n
      nil
    else
      @keys[i]
    end
  end

end

要改 BST 为 BSST

is_empty 改为 is_empty?

@values 改为 @vals