Создание бинарного дерева
Когда я начал изучать ruby, я решил реализовать бинарное дерево и некоторые из его основных операций (insert, delete, walk, и search), для того, что бы лучше вникнуть в язык. Бинарные деревья, это хорошее упражнение, что бы понять особенности языка, такие как: условные операторы, циклы, классы. В то же время, это возможность решить интересную задачу. Алгоритм бинарного дерева хорошо описан во многих книгах и в интернете.
Для усложнения задачи, я так же реализовал отрисовку бинарного дерева средствами html5 и Canvas. Это позволяет более наглядно понять работу бинарного дерева. Вы можете посмотреть демонстрацию на веб сайте.
Далее я кратко опишу реализацию основных методов построения бинарного дерева.
Бинарное дерево или дерево двоичного поиска
Собственно код, представленный ниже, реализует Дерево двоичного поиска (BST), которое является более конкретной версией бинарных деревьев. В двоичном дереве, каждый узел имеет не более 2 детей, один из них называется «левое поддерево», а другой «правое поддерево», сортировка отсутствует. В двоичном дереве поиска, все узлы хранятся в порядке, отраженном в следующем правиле:
Допустим x это узел в двоичном дереве поиска, если y является «левым поддеревом» для x, то y.key ≤ x.key. Если y является «правым поддеревом» для x, то y.key ≥ x.key.
Реализация бинарного дерева поиска
Класс, для работы с деревом, который я реализовал можно использовать следующим образом:
require "binarytree" tree = BinaryTree.new(40) tree.add(30) tree.add(100) tree.add(20) tree.add(35) tree.add(25) tree.add(34) puts "Tree nodes: #" => "20, 25, 30, 34, 35, 40, 100"Этот клас мы можем использовать с числами, строками или любыми собственными типами ruby, поддерживающими сопоставление (т.е. )
Добавление узлов в бинарном дереве
Код для добавления узлов в бинарном дереве показан ниже. Этот код сначала проверяет, есть ли у нас уже корневой узел, если нет, то создаем корневой узел с новым значением. Если у нас уже есть корневой узел, сканируем узлы дерева (с помощью правила указанного выше) пока не дойдем до конечного узла. Как только мы достигли конечного узла мы обновляем его, чтобы указать на новый узел.
def add(new_value) if @root == nil @root = Node.new(new_value) @total_nodes = 1 return end current = @root while(true) if new_value >= current.value if current.right == nil current.right = Node.new(new_value) break else current = current.right end else if current.left == nil current.left = Node.new(new_value) break else current = current.left end end end @total_nodes += 1 end Ходьба по дереву
Одним из преимуществ двоичного дерева поиска в том, что очень легко получить значения, хранящиеся в нем. Этот процесс называется «ходьба по отсортированному дереву». Например, если у нас есть дерево со следующими значениями: 100, 50, 200 и 150, то отсортированное дерево даст нам значения: 50, 100, 150 и 200. Хождение по дереву можно реализовать с помощью рекурсивной функции. Однако рекурсивный метод, хотя и элегантный, но не очень эффективен, если дерево большого размера. Код, который я реализовал не использует рекурсию, но вместо этого использует массив, как стек для отслеживания узлов, которые он посещает. Это решение не такое элегантное, как рекурсия, но оно хорошо работает, даже если в дереве тысячи узлов.
def walk return nil if @root == nil node = @root stack = [] ignore_left = false while(true) #p "processing #" if ignore_left #p "ignoring nodes to the left" ignore_left = false else if node.left != nil #p "moving to the left" stack Пока я реализовывал этот метод, я понял красоту и простоту одной из самых лучших возможностей ruby: блоки. Когда алгоритм находит следующий узел для обработки, он просто отдает его вызывающей программе. Это позволяет ходить по дереву и быть полностью независимым от действий, которые мы хотим выполнить на каждом узле. Например вы можете сделать для каждого узла такой код:
В этом примере блок просто «выводит» значения, но мы увидим, более сложный пример, когда рассмотрим код для отрисовки двоичного дерева.
Как рисовать Двоичное дерево
Алгоритм отрисовки двоичного дерева, в значительной степени похож, на алгоритма хождения по дереву с тем исключением, что нам нужно вычислить координаты, где каждый узел должен быть размещен и как мы пересекаем узлы. Расчет координат оказалась интересной задачей.
- Нарисовать корневой узел с заданными координатами
- Нарисовать левое поддерево с лева от корневого узла
- Нарисовать правое поддерево с права от корневого узла
def draw_node(root, x, y, block) return if root == nil block.call(root, x, y, x, y) draw_left(root.left, x, y, block) if root.left != nil draw_right(root.right, x, y, block) if root.right != nil end Для вычисления координат левого поддерева, рассчитываем сколько детей с правой стороны левого поддерева. Полученное число, мы используем для отрицательного смещения по оси x. Дальше мы рекурсивно вызываем этот метод для левого и правого поддерева.
def draw_left(node, parent_x, parent_y, block) if node.right != nil count = 1 + children_count(node.right) else count = 0 end x = parent_x - @x_distance - (count*@x_distance) y = parent_y + @y_distance block.call(node.value, x, y, parent_x, parent_y) draw_left(node.left, x, y, block) if node.left != nil draw_right(node.right, x, y, block) if node.right != nil end Для правого поддерева, делаем все тоже самое, но наоборот.
def draw_right(node, parent_x, parent_y, block) if node.left != nil count = 1 + children_count(node.left) else count = 0 end x = parent_x + @x_distance + (count*@x_distance) y = parent_y + @y_distance block.call(node.value,x,y, parent_x, parent_y) draw_left(node.left, x, y, block) if node.left != nil draw_right(node.right, x, y, block) if node.right != nil end Как и метод walk, метода отрисовки по факту ничего не рисуют, а лишь указываю координаты отображения объекта. Следующий пример показывает построение дерева с координатами в консоли:
require "binarytree" require "binarytreedrawer" tree = BinaryTree.new tree.add(100) tree.add(50) tree.add(150) tree.add(25) tree.add(75) tree.add(125) tree.add(175) drawer = BinaryTreeDrawer.new(tree) drawer.draw(0,0, Proc.new < |value, x, y, px, py| puts "Value #at (#, #)" >) => Value 100 at (0, 0) => Value 50 at (-40, 30) => Value 25 at (-60, 60) => Value 75 at (-20, 60) => Value 150 at (40, 30) => Value 125 at (20, 60) => Value 175 at (60, 60) Реальный пример отрисовки Бинарного дерева на веб-странице
Имея координаты мы можем использовать любую графическую программу для отрисовки дерева. В этом веб-приложение я буду использовать HTML 5 Сanvas как поверхность для рисования, и несколько JS методов. Ниже представлен простой пример, как я генерирую JS вызовы для отрисовки дерева:
drawer = BinaryTreeDrawer.new(@tree) drawer.draw(0, 0, Proc.new < |value, x, y, px, py| circles , offsetY + #, 5);" lines , offsetY + #, centerX + #, offsetY + #);" labels , offsetY+5+#, \"#\");" >) Обратите внимание, что этот код просто создает три массива (круги, линии, ярлыки) с вызовами JavaScript методов. Эти массивы позднее, вставляются в веб-страницу и рисуют дерево на стороне клиента.
Исходный код и Демонстрация
Если вы хотите увидеть демо, вы можете посетить http://binarytree.heroku.com и генерировать несколько бинарных деревьев со случайными данными или нарисовать двоичного дерево с собственным набором данных.
Все исходники, для реализации двоичного дерева, а также демо-сайт, выложены на GitHub.
Источник