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

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 " "

tree.preorder {|x| print x, " "}

print " "

tree.postorder {|x| print x, " "}

print " "

# Печатается:

# 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