用Ruby实现算法--二叉查找树

二叉查找树的性质

• 若任意节点的左子树不为空，则左子树上所有结点的值均小于它的根结点的值；
• 任意节点的右子树不为空，则右子树上所有结点的值均大于它的根结点的值；
• 任意节点的左、右子树也分别为二叉查找树。
• 没有键值相等的节点（no duplicate nodes）。

节点

根据二叉查找树性质不难写出节点类

class Node

  attr_reader :value
  attr_accessor :left, :right

  def initialize(v)
    @value = v
  end

end

插入节点

根据二叉查找树的性质:

1. 若值等于根节点, 不插入
2. 若根节点为空, 插入根节点
3. 若值小于根节点, 插入左子树
4. 若值大于根节点

def insert(v)
  case value <=> v
  when 1 then insert_left(v)
  when -1 then insert_right(v)
  when 0 then false 
  end
end

def inspect
  "{#{value}::#{left.inspect}|#{right.inspect}}"
end

private

  def insert_left(v)
    if left
      left.insert(v)
    else
      self.left = Node.new(v)
    end
  end

  def insert_right(v)
    if right
      right.insert(v)
    else
      self.right = Node.new(v)
    end
  end

空节点

在上面的Node对象中, left和right为nil, 这样在插入时就需要判断左右是否为nil, 在之后的查找中也需要做nil判断, 十分的繁琐
加入空节点的概念就可以去除冗余的nil判断, 简化代码

class EmptyNode
  # 预留给查询用
  def include?(*)
    false
  end

  def insert(*)
    false
  end

  def inspect
    "{}"
  end
  
end

重新定义一下Node的代码

class Node

  attr_reader :value
  attr_accessor :left, :right

  def initialize(v)
    @value = v
    @left = EmptyNode.new
    @right = EmptyNode.new
  end

  def inspect
    "{#{value}::#{left.inspect}|#{right.inspect}}"
  end

  def insert(v)
    case value <=> v
      when 1 then insert_left(v)
      when -1 then insert_right(v)
      when 0 then false
    end
  end

  private
    # 插入时不再需要nil判断, 空节点的insert返回false
    def insert_left(v)
      left.insert(v) or @left = Node.new(v)
    end

    def insert_right(v)
      right.insert(v) or @right = Node.new(v)
    end

end

查找

因为二叉树的左右是有序的, 使用递归就可以简单实现, 步骤如下

1. 若树是空的, 则查找未命中
2. 若等于根节点, 则查找命中
3. 若小于根节点, 则查找左子树
4. 若大于根节点, 则查找右子树

  def include?(v)
    case value <=> v
      when 1 then left.include?(v)
      when -1 then right.include?(v)
      when 0 then true
    end
  end

现在找不到值时, 自然会返回false
若是没有EmptyNode的定义, 这里会有很繁琐的nil判断