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

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

на обложку

Фултон Хэл

Шрифт:

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

Отметим, что во многих языках, например в С или 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

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