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

http://hectorcorrea.com/Blog/Drawing-a-Binary-Tree-in-Ruby
  • Перевод
Когда я начал изучать 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.
Поделиться публикацией
Похожие публикации
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама
Комментарии 16
  • 0
    Спасибо за статью. Очень интересно

    На сайте-демонстрации при попытке нарисовать свое дерево оставьте поле со значениями пустое и просто кликните Draw it! -> Вы получите Internal Server Error
    • 0
      ну это же демонстрация, зачем ее ломать, не думаю что сайт на heroku вообще выдержит нагрузку…
      • 0
        Не знаю — не знаю
        Да я, собственно, и не собирался ломать. Если честно, было лень вводить какие-либо значения и для быстроты просто нажал на кнопку :)
        Возможно во мне сыграло профессиональное чувство тестировщика :)
        Вы уж извините, если что не так

        • +2
          да ничего, вы еще обратите внимание, что это перевод…
    • 0
      Вот так будет более в стиле Ruby:

      if node.right != nil #=> unless node.right.nil?
      while(true) #=> loop do block
      • +3
        if node.right != nil => if node.right
      • +1
        Картинка нарисована случаем не в iTeXmacs?
        • +1
          оййй, ступил-ступил, с помощью руби рисование >_<
        • 0
          while true => while node, а break убрать
          • 0
            По-моему вместо «walk» используют термин «traverse» в случае графов.

            А так больше всего паример рисование порадовал :p
            • –3
              > потдерево
              пофиксите, плз…
              • +1
                Нехорошее же дерево, не балансирующееся. И плюс, строить сложносвязанные структуры на языках типа Руби крайне неразумно — оверхед огромный и по памяти, и по скорости работы.
                • +4
                  Фотматирование пляшет. Код на гитхабе невозможно читать.

                  Ещё ооочень много неидеоматического руби-кода. Как уже выше говорили `if node.left != nil` => `unless node.left`, `if node.left == nil` => `if node.left`. Код метода has_one_child_only? можно сократить более чем в два раза, используя xor: `has_left_children? ^ has_right_children?`.

                  Именования родом из жавы: `heightRight`, `heightLeft`. Также, обычно не пишут методы is_xxx?.. Принято писать xxx?..

                  Вместе с методом add для добавления в коллекцию новых элементов в руби почти всегда делают метод << (можно как алиас метода add).

                  Ещё жабьи уши видны в while-условиях со скобочками: `while(true)`.

                  По дизайну.

                  Поля root и total_nodes должны быть объявлены через attr_reader, не attr_accessor. Зачем давать пользователю библиотеки менять эти значения?

                  Опциональный первый параметр в конструкторе дерева не нужен. Странное решение вообще какое-то. Почему одно значение в дерево можно передавать при создании, а не два или не десять? Я не вижу причины.

                  Методы add и add2 — какая между ними разница? Зачем их два? Неочевидно.

                  Дерево не балансируется — это тоже верно замечено. Вообще говоря, такие деревья не нужны.

                  Ещё всякие методы-итераторы (вроде walk) сейчас делают адаптивными в зависимости от того передан ли блок в метод. Если блок передаётся — происходит просто обход дерева, если нет — возвращается Enumerator. Чтобы понятней было о чём я говорю, взгляните на Enumerable.map.

                  Ну и вообще, то, что walk_* методы возвращают строки — это по меньшей мере странно. На больших объёмах данных это будет вызывать ненужную нагрузку на память, GC и процессор. И потом: неочевидно, что делать, если элементы дерева строки, которые сами содержат запятые. Как потом парсить аутпут walk_* методов?

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

                    Это относится не только к руби, так как может быть реализовано не только с помощью блоков, но и лямбд и даже объектов. А вообще этот подход называется visitor pattern.

                    Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.