Ruby 二叉搜索树插入方法堆栈级别太深

Question

我正在尝试为二叉搜索树编写一个递归插入方法，但一直收到 stack level too deep 一直给我错误是怎么回事？

我的节点class

class Node
  attr_accessor :value, :left, :right

  def initialize(value)
    @value = value
    left = nil
    right = nil
  end
end

二叉搜索树class

class Bst
  attr_accessor :root, :size

  def initialize
    @root = nil
    @size = 0
  end

  def insert(value, root=nil)
    if @root == nil
      @root = Node.new(value)
    end
    if value < @root.value
      if @root.left == nil
        @root.left = Node.new(value)
      else
        return insert(value, @root.left)
      end
      return root
    end
    if value > @root.value
      if @root.right == nil
        @root.right = Node.new(value)
      else
        return insert(value, @root.right)
      end
    end
    return root
  end

一旦我尝试将 4 添加到树中，就会发生这种情况

tree = Bst.new
tree.insert(10)
tree.insert(6)
tree.insert(19)
tree.insert(4)

Answer 1

当您递归并提供新的 root 时，您仍在将值与 @root.value 进行比较。

由于 4 仍然小于 10，您递归并将 @root.left 作为 root 传递。但是，从未使用过 root；您再次比较 @root.value，并与 @root.left 进行递归，而这些永远不会改变；因此，你有无限的递归（或者至少是无限的，直到你炸毁堆栈）。

您想与 root.value 进行比较，并用 root.left 递归。

@root 和 root 是不同的东西会造成混淆，并导致逻辑错误。更好的变量命名可能会避免此错误。

编辑：

class Node
  attr_accessor :value, :left, :right

  def initialize(value)
    @value = value
    @left = nil
    @right = nil
  end
end

class Bst
  attr_accessor :root, :size

  def initialize
    @root = nil
    @size = 0
  end

  def insert(value, node=nil)
    unless @root
      @root = Node.new(value)
      return
    end

    node ||= @root

    if value < node.value
      if node.left
        return insert(value, node.left)
      else
        node.left = Node.new(value)
      end
    elsif value > node.value
      if node.right
        return insert(value, node.right)
      else
        node.right = Node.new(value)
      end
    end
    @size += 1
    return node
  end
end

tree = Bst.new
tree.insert(10)
tree.insert(6)
tree.insert(19)
tree.insert(4)

p tree

Ruby 二叉搜索树插入方法堆栈级别太深

Ruby Binary Search Tree insert method stack level too deep

ruby

binary-search-tree