9.3. Деревья. Глава 9. Более сложные структуры данных. Программирование на языке Ruby.

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

9.3. Деревья.

Я не увижу никогда, наверное, Поэму столь прекрасную как дерево. Джойс Килмер, «Деревья»[11]

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

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

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

Отметим, что во многих языках, например в С или Pascal, деревья реализуются с помощью адресных указателей. Но в Ruby (как и в Java) указателей нет, вместо них используются ссылки на объекты, что ничуть не хуже, а иногда даже лучше.

9.3.1. Реализация двоичного дерева.

Ruby позволяет реализовать двоичное дерево разными способами. Например, хранить значения узлов можно в массиве. Но мы применим более традиционный подход, характерный для кодирования на С, только указатели заменим ссылками на объекты.

Что нужно для описания двоичного дерева? Понятно, что в каждом узле должен быть атрибут для хранения данных. Кроме того, в каждом узле должны быть атрибуты для ссылки на левое и правое поддерево. Еще необходим способ вставить новый узел в дерево и получить хранящуюся в дереве информацию. Для этого нам потребуется два метода.

В первом дереве, которое мы рассмотрим, эти методы будут реализованы неортодоксальным способом. Позже мы расширим класс Tree.

В некотором смысле дерево определяется алгоритмом вставки и способом обхода. В нашем первом примере (листинг 9.1) метод insert будет осуществлять поиск в дереве «в ширину», то есть сверху вниз и слева направо. При этом глубина дерева растет относительно медленно, и оно всегда оказывается сбалансированием. Методу вставки соответствует итератор traverse, который обходит дерево в том же порядке.

Листинг 9.1. Вставка и обход дерева в ширину.

Class Tree.

attr_accessor :left.

attr_accessor :right.

attr_accessor :data.

def initialize(x=nil).

@left = nil.

@right = nil.

@data = x.

end.

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.

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.

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.

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.

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.

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.

Оглавление.