четверг, 11 августа 2011 г.

Создание бинарного дерева

Когда я начал изучать 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: #{tree.to_s}" => "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 #{node.value.to_s}"
    if ignore_left
      #p "ignoring nodes to the left"
      ignore_left = false
    else	      
      if node.left != nil
        #p "moving to the left"
        stack << node
        node = node.left
        next
      end
    end

    yield node

    if node.right != nil
      #p "moving to the right"
      node = node.right
      next
    end

    break if stack.length == 0

    #p "popping from the stack"
    node = stack.pop
    ignore_left = true
  end

end

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

tree.walk { |node| puts "#{node.value}" }

В этом примере блок просто «выводит» значения, но мы увидим, более сложный пример, когда рассмотрим код для отрисовки двоичного дерева.

Как рисовать Двоичное дерево


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

Основной алгоритм заключается в следующем:
  • Нарисовать корневой узел с заданными координатами
  • Нарисовать левое поддерево с лева от корневого узла
  • Нарисовать правое поддерево с права от корневого узла
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 #{value} at (#{x}, #{y})"
})

=> 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 << "draw_circle(centerX + #{x}, offsetY + #{y}, 5);" 
  lines << "draw_line(centerX + #{x}, offsetY + #{y}, centerX + #{px}, offsetY + #{py});"
  labels << "draw_label(centerX + 7 + #{x}, offsetY+5+#{y}, \"#{value}\");"
  
})

Обратите внимание, что этот код просто создает три массива (круги, линии, ярлыки) с вызовами JavaScript методов. Эти массивы позднее, вставляются в веб-страницу и рисуют дерево на стороне клиента.

Исходный код и Демонстрация


Если вы хотите увидеть демо, вы можете посетить http://binarytree.heroku.com и генерировать несколько бинарных деревьев со случайными данными или нарисовать двоичного дерево с собственным набором данных.

Все исходники, для реализации двоичного дерева, а также демо-сайт, выложены на GitHub.

Комментариев нет:

Отправить комментарий