Хэл Фултон - Программирование на языке Ruby

def insert(x)

list = []

if @data == nil

@data = x

elsif @left == nil

@left = Tree.new(x)

elsif @right == nil

@right = Tree.new(x)

else

list << @left

list << @right

loop do

node = list.shift

if node.left == nil

node.insert(x)

break

else

list << node.left

end

if node.right == nil

node.insert(x)

break

else

list << node.right

end

end

end

end

def traverse()

list = []

yield @data

list << @left if @left != nil

list << @right if @right != nil

loop do

break if list.empty?

node = list.shift

yield node.data

list << node.left if node.left != nil

list << node.right if node.right != nil

end

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

Пусть дерево уже отсортировано. Тогда оно может служить прекрасной справочной таблицей; например, для поиска в сбалансированном дереве, содержащем миллион узлов, понадобится не более 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 (не найдено).

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

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

temp

end

end

items = %w[bongo grimace monoid jewel plover nexus synergy]

tree = Tree.new

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

str = tree.to_a * ","

# str is now "bongo,grimace,jewel,monoid,nexus,plover,synergy"

arr = tree.to_a

# arr равно:

# ["bongo",["grimace",[["jewel"],"monoid",[["nexus"],"plover",

# ["synergy"]]]]]

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

Графом называется множество вершин, произвольным образом соединенных друг с другом. (Дерево — частный случай графа.) Не будем слишком углубляться в эту тему, поскольку теория и терминология весьма сложны. Очень скоро мы перешли бы от информатики в область чистой математики.

И все же у графов есть немало практических приложений. Возьмите обычную дорожную карту, на которой города соединены скоростными магистралями, или печатную плату. То и другое удобно представлять в виде графов. Компьютерную сеть тоже можно описать в терминах теории графов, будь то локальная сеть из нескольких десятков машин или весь Интернет, насчитывающий миллионы узлов.

Под графом мы обычно понимаем неориентированный граф . Попросту говоря, в нем не проставлены стрелки на соединительных линиях; две вершины либо соединены, либо нет. Между тем в ориентированном графе (орграфе) могут быть «улицы с односторонним движением»; из того, что вершина x соединена с вершиной у, не следует, что верно и обратное. Наконец, во взвешенном графе ребрам можно назначать веса. Например, вес может выражать «расстояние» между вершинами. Мы ограничимся только этими основными видами графов; интересующегося читателя отсылаем к многочисленным учебникам информатики и математики.

В Ruby, как и во многих других языках, граф можно представить разными способами, например в виде настоящей сети взаимосвязанных объектов или в виде матрицы, в которой хранятся ребра графа. Мы рассмотрим оба способа и на примерах покажем, как можно манипулировать графами.

Нижеприведенный пример основан на двух предыдущих. В листинге 9.3 неориентированный граф реализован в виде матрицы смежности с помощью класса ZArray(см. раздел 8.1.26). Это нужно для того, чтобы новые элементы по умолчанию получали значение 0. Также мы унаследовали классу TriMatrix(см. раздел 8.1.7), чтобы получить нижнетреугольную матрицу.