Программирование на языке Ruby
Программирование на языке Ruby читать книгу онлайн
Внимание! Книга может содержать контент только для совершеннолетних. Для несовершеннолетних чтение данного контента СТРОГО ЗАПРЕЩЕНО! Если в книге присутствует наличие пропаганды ЛГБТ и другого, запрещенного контента - просьба написать на почту [email protected] для удаления материала
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 endenditems = [1, 2, 3, 4, 5, 6, 7]tree = Tree.newitems.each {|x| tree.insert(x)}tree.traverse {|x| print "#{x} "}print "n"# Печатается "1 2 3 4 5 6 7 "Такое дерево не слишком интересно. Но оно годится в качестве введения и фундамента, на котором можно возводить здание.
9.3.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 endenditems = [50, 20, 80, 10, 30, 70, 90, 5, 14, 28, 41, 66, 75, 88, 96]tree = Tree.newitems.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 509.3.3. Использование двоичного дерева как справочной таблицы
Пусть дерево уже отсортировано. Тогда оно может служить прекрасной справочной таблицей; например, для поиска в сбалансированном дереве, содержащем миллион узлов, понадобится не более 20 сравнений (глубина дерева равна логарифму числа узлов по основанию 2). Чтобы поиск был осмысленным, предположим, что в каждом узле хранится не какое-то одно значение, а ключ и ассоциированные с ним данные.
