Блог

Я рекурсивно создаю сбалансированное двоичное дерево поиска в Ruby с использованием отсортированного массива. Однако у меня возникли проблемы с конечным возвращаемым значением. Вместо того, чтобы все узлы всплывали, создавали дерево и возвращали узел базового уровня 1, возвращался самый последний узел в нижней части дерева.

Похоже, что создаваемые узлы вообще не связаны друг с другом (печать экземпляра класса с использованием p list возвращает только последний узел). Как связать узлы вместе и вернуть корневой узел 1-го уровня?

Код:

 class Node
  include Comparable

  attr_accessor :value, :left, :right

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

class Tree
  attr_accessor :sorted_arr, :arr

  def initialize(arr)
    @arr = arr
    @sorted_arr = arr.sort.uniq
  end

  #Problem: nodes not being linked together

  def build_tree(arr, start, last)
    if start > last
      return nil
    end

    mid_index = (start   last) / 2
    
    @root = Node.new(arr[mid_index])


    @root.left = build_tree(arr, start, mid_index - 1)
    @root.right = build_tree(arr, mid_index   1, last)


    return @root
  end
end

list = Tree.new([1, 7, 4, 23, 8, 9, 4, 3, 6, 7, 9, 67, 6345, 324])
list.build_tree(list.sorted_arr, 0, list.sorted_arr.length-1)
p list


 

Вы должны использовать root вместо @root .
Те, которые начинаются с @ , являются переменными экземпляра, поэтому, когда вы вызываете:

 @root.left = build_tree(arr, start, mid_index - 1)
 

внутри этого build_tree вызова в конечном итоге вы также вызовете, для @root = Node.new(arr[mid_index]) которого он заменит значение, уже установленное в родительском вызове.