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.