binary search tree

bst.rb

#!usr/bin/env ruby
class BST
  def initialize
  end

  def get key
    node = _get(root, key)
    node ? node.val : node
  end

  def put key, val
    @root = _put(root, key, val)
  end

  def min
    node = _min root
    node ? node.key : node
  end

  def max
    node = _max root
    node ? node.key : node
  end

  def floor key
    node = _floor root, key
    node ? node.key : node
  end

  def ceiling key
    node = _ceiling root, key
    node ? node.key : node
  end

  # 找到排名是 n + 1 的结点
  # 即它前面有 n 个小于它的结点
  def select n
    node = _select root, n
    node ? node.key : node
  end

  # select 的逆操作
  def rank key
    _rank root, key
  end

  def del_min
    _del_min root
  end

  def del_max
    _del_max root
  end


  def del key
    _del root, key
  end

  def all_keys
    keys min, max
  end

  def keys low, high
    queue = []
    _keys root, queue, low, high
    queue
  end

  attr_accessor :root

  class Node
    attr_accessor :key, :val, :n, :left, :right
    def initialize(key, val, n)
      @key = key
      @val = val
      @n = n
    end

  end

  private

  def size node
    node ? node.n : 0
  end

  def _get(node, key)
    return nil if node.nil?
    if node.key > key
      _get(node.left, key)
    elsif node.key < key
      _get(node.right, key)
    else
      node
    end
  end

  def _put(node, key, val)
    return Node.new(key, val, 1) if node.nil?
    if node.key > key
      node.left = _put(node.left, key, val)
    elsif node.key < key
      node.right = _put(node.right, key, val)
    else
      node.val = val
    end
    node.n = size(node.left) + size(node.right) + 1
    node
  end

  def _min node
    return nil if node.nil?
    if !node.left.nil?
      _min node.left
    else
      node
    end
  end

  def _max node
    return nil if node.nil?
    if !node.right.nil?
      _max node.right
    else
      node
    end
  end

  def _floor node, key
    return nil if node.nil?
    if node.key > key
      _floor node.left, key
    elsif node.key < key
      x = _floor node.right, key
      x ? x : node
    else
      node
    end
  end

  def _ceiling node, key
    return nil if node.nil?
    if node.key > key
      x = _ceiling node.left, key
      x ? x : node
    elsif node.key < key
      _ceiling node.right, key
    else
      node
    end
  end

  def _select node, n
    return nil if node.nil?
    left_size = size node.left
    if left_size > n
      _select node.left, n
    elsif left_size < n
      _select node.right, (n - left_size - 1)
    else
      node
    end
  end

  def _rank node, key
    return 0 if node.nil?
    if node.key > key
      _rank node.left, key
    elsif node.key < key
      size(node.left) + 1 + _rank(node.right, key)
    else
      size node.left
    end
  end

  def _del_min node
    return nil if node.nil?
    if node.left
      node.left = _del_min node.left
    else
      return node.right
    end
    node.n = size(node.left) + 1 + size(node.right)
    node
  end

  def _del_max node
    return nil if node.nil?
    if node.right
      node.right = _del_max node.right
    else
      return node.left
    end
    node.n = size(node.left) + 1 + size(node.right)
    node
  end

  def _del node, key
    return nil if node.nil?
    if node.key > key
      node.left = _del node.left, key
    elsif node.key < key
      node.right = _del node.right, key
    else
      return node.left if node.right.nil?
      return node.right if node.left.nil?

      t = node
      node = _min t.right
      node.right = _del_min t.right
      node.left = t.left
      t.right = nil
      t.left = nil
    end
    node.n = size(node.right) + 1 + size(node.left)
    node
  end

  #找到范围落在 low 与 high 之间的所有 key
  #与中序遍历类似
  #尽量扩充边界,直到不满足条件
  def _keys node, queue, low, high
    return if node.nil?
    if node.key > low
      _keys node.left, queue, low, high
    end

    if node.key >= low && node.key <= high
      queue << node.key
    end

    if node.key < high
      _keys node.right, queue, low, high
    end
  end


end

bst = BST.new

bst.put('s',8)
bst.put('e',6)
bst.put('x',1)
bst.put('a',2)
bst.put('c',1)
bst.put('r',3)
bst.put('h',2)
bst.put('m',1)

# puts bst.min
# puts bst.max
# puts bst.floor 'i'
# puts bst.ceiling 'n'
# puts bst.select 1
# puts bst.del_min
# puts bst.min
# puts bst.del_max
# puts bst.max
# bst.del 'e'
# puts bst.rank 'r'

# puts bst.all_keys
# puts bst.keys 'a', 'x'