Программирование на языке Ruby

  end

 end

 items = [1, 2, 3, 4, 5, 6, 7]
 tree = Tree.new
 items.each {|x| tree.insert(x)}

 tree.traverse {|x| print "#{x} "}
 print "\n"
 # Печатается "1 2 3 4 5 6 7 "

Такое дерево не слишком интересно. Но оно годится в качестве введения и фундамента, на котором можно возводить здание.

9.3.2. Сортировка с помощью двоичного дерева

Двоичное дерево позволяет эффективно реализовать сортировку произвольных данных. (Правда, если данные уже отсортированы, оно вырождается в обычный связанный список.) Причина ясна: при каждом сравнении мы исключаем половину мест, в которые можно поместить новый узел.

Хотя в настоящее время такой способ сортировки применяется редко, знать о нем не повредит. Код в листинге 9.2 основан на предыдущем примере.

Листинг 9.2. Сортировка с помощью двоичного дерева

 class Tree

  # Предполагается, что определения взяты из предыдущего примера...

  def insert(x)
  if @data == nil
  @data = x
  elsif x <= @data
  if @left == nil
  @left = Tree.new x
  else
  @left.insert x
  end
  else
  if @right == nil
  @right = Tree.new x
  else
  @right.insert x
  end
  end
  end

  def inorder
  @left.inorder {|y| yield y} if @left != nil
  yield @data
  @right.inorder {|y| yield y} if bright != nil
  end

  def preorder
  yield @data
  @left.preorder {|y| yield y} if @left != nil
  @right.preorder {|y| yield y} if @right != nil
  end

  def postorder
  @left.postorder {|y| yield y} if @left != nil
  @right.postorder {|y| yield y} if @right != nil
  yield @data
  end
 end

 items = [50, 20, 80, 10, 30, 70, 90, 5, 14,
  28, 41, 66, 75, 88, 96]

 tree = Tree.new

 items.each {|x| tree.insert(x)}

 tree.inorder {|x| print x, " "}
 print "\n"
 tree.preorder {|x| print x, " "}
 print "\n"
 tree.postorder {|x| print x, " "}
 print "\n"

# Печатается:
 # 5 10 14 20 28 30 41 50 66 70 75 80 88 90 96
 # 50 20 10 5 14 30 28 41 80 70 66 75 90 88 96
 # 5 14 10 28 41 30 20 66 75 70 88 96 90 80 50

9.3.3. Использование двоичного дерева как справочной таблицы

Пусть дерево уже отсортировано. Тогда оно может служить прекрасной справочной таблицей; например, для поиска в сбалансированном дереве, содержащем миллион узлов, понадобится не более 20 сравнений (глубина дерева равна логарифму числа узлов по основанию 2). Чтобы поиск был осмысленным, предположим, что в каждом узле хранится не какое-то одно значение, а ключ и ассоциированные с ним данные.

Почти всегда лучше использовать в качестве справочной таблицы хэш или даже таблицу во внешней базе данных. Но все равно приведем код:

 class Tree

  # Предполагается, что определения взяты из предыдущего примера...

  def search(x)
  if self.data == x
  return self
  elsif x < self.data
  return left ? left.search(x) : nil
  else
  return right ? right.search(x) : nil
  end
  end

 end

 keys = [50, 20, 80, 10, 30, 70, 90, 5, 14,
  28, 41, 66, 75, 88, 96]

 tree = Tree.new

 keys.each {|x| tree.insert(x)}

 s1 = tree.search(75) # Возвращает ссылку на узел, содержащий 75...

 s2 = tree.search(100) # Возвращает nil (не найдено).

9.3.4. Преобразование дерева в строку или массив

С помощью тех же приемов, которые применяются для обхода дерева, мы можем преобразовать его в строку или в массив. Ниже мы выполняем обход во внутреннем порядке, хотя подошел бы и любой другой способ:

 class Tree

  # Предполагается, что определения взяты из предыдущего примера...

  def to_s
  "[" +
  if left then left.to_s + "," else "" end +
  data.inspect +
  if right then "," + right.to_s else "" end + "]"
  end

  def to_a
  temp = []
  temp += left.to_a if left
  temp << data
  temp += right.to_a if right