Введение
В этой статье хочется представить реализацию дерева бинарного поиска для задачи, изложенной в статье [1]. В описанной там задаче используется алгоритм «sweeping line», для которой нужно бинарное дерево с возможностью перемещения не только от корня дерева к дочерним узлам и листьям, но и по листьям в отдельности, начиная от крайнего листа (левого или правого). Задача показалась достаточно простой, потому не стал долго искать уже готовые реализации и решил сделать самостоятельно. При этом поставил дополнительную задачу — задание процедуры добавления нового листа в дерево снаружи.
Немного теории
Здесь будет совсем мало теории. Основная масса информации может быть получена в Википедии [2]. Коротко говоря, предмет повествования является древовидной структурой данных, в которой каждый элемент может иметь по два дочерних. В моем случае детей будет именно двое, что является следствием поставленной в [1] задачи. Иначе узел будет листом, т.е. детей у него не будт вообще. При добавлении нового элемента в дерево производится спуск до близжайщего по значению листа. Найденный лист заменяется на дерево, состоящее из одного родителя и двух детей. Родитель получает значение, которое равно среднеарифметическому от значений нового элемента и замененного деревом листа. Дети — это наш новый элемент и замененный лист, позиции которых (слева или справа) зависят от того, у какого элемента значение меньше. Узел с меньшим значением оказывается слева. При добавлении поддерева обязательно нужно добавить/обновить ссылки между указанными тремя элементами (связи «родитель-дитя»).
Спуск, о котором было сказано выше, производится также по принципу «больше-меньше, влево-вправо». Сравнивается значение узла со значением нового элемента. Если новое значение меньше значения узла, то спускаемся влево, а иначе (>=) движемся вправо. Как это работает наглядно показано в следующем разделе.
В итоге мы получим отсортированное множество листьев и узлов, связанных друг с другом («родитель-дитя», «левый», «правый»). Далее нужно организовать переход от одного листа к другому, соседу справа или слева. С этой логикой пришлось повозиться больше всего. Описывать ее лучше на картинках (см. следующий раздел).
Логика дерева в иллюстрациях
Начнем с добавления элемента. Если дерево пусто, то новый элемент становится корнем. Иначе создаем поддерево вместо одного из узлов. На рис. 1 изображено добавление первых двух элементов.
Рисунок 1. Вставка нового элемента
После того, как дерево будет заполнено, можно будет пройтись по листьям, например, слева направо. На рис. 2 изображен пример дерева. Черными стрелками обозначены переходы от одного листа к другому (соседу справа).
Рисунок 2. Переходы «по листьям»
Зачем нужна возможность перехода по листьям? В задаче построения диаграммы Вороного листья дерева соответствуют «аркам». Для каждой последовательности из трех арок потенциально может возникнуть «событие круга». Поэтому и нужно иметь возможность перемещаться по аркам, т.е. по листьям в дереве, как в линейном двусвязном списке. Сначала эту возможность решил реализовать только через функциональную рекуррсию. Как видно из рис. 2, самым сложным моментом при этом оказались переходы вида «7 -> 8». При использовании только рекурсии попал в вечный цикл между «7» и «6.75». Решил проблему добавлением цикла, по которому производился переход до первого родителя, не являющегося правым ребенком (в данном случае это переход от «7» к «6»). При переходе из самого правого листа («15») упомянутый цикл приведет к корню всего дерева, после чего мы получим «nil» в нотации Ruby и поиск соседей справа окончится.
Код
Класса узла "Node".
class Node
attr_accessor :val, :parent, :left, :right
def initialize( val, parent=nil, left=nil, right=nil)
@val = val
@parent, @left, @right = parent, left, right
end
def root?
return @parent.!
end
def leaf?
(@left || @right).!
end
def left?
return true unless @parent
if @parent.left
return self.equal?(@parent.left)
else
return false
end
end
def right?
return true unless @parent
if @parent.right
return self.equal?(@parent.right)
else
return false
end
end
def to_s
res = "l:"
if @left
res << "#{@left.val.to_s} s:#{@val.to_s} r:"
else
res << "nil s:#{@val.to_s} r:"
end
if @right
res << @right.val.to_s
else
res << "nil"
end
res
end
def Node.get_left_neighbour(node, up_dir = true)
return nil unless curr
if up_dir
node = curr.parent
if curr.right?
return Node.get_left_neighbour(curr.left, false) if curr.left
return Node.get_left_neighbour(node.left, false)
else
while node && node.left?
node = node.parent
end
return node ? Node.get_left_neighbour(node.parent.left, false) : nil
end
else
return curr if curr.leaf?
return Node.get_left_neighbour(curr.left, false) unless curr.right
return Node.get_left_neighbour(curr.right, false)
end
end
def Node.get_right_neighbour(curr, up_dir = true)
return nil unless curr
if up_dir
node = curr.parent
if curr.left?
return Node.get_right_neighbour(curr.right, false) if curr.right
return Node.get_right_neighbour(node.right, false)
else
while node && node.right?
node = node.parent
end
return node ? Node.get_right_neighbour(node.parent.right, false) : nil
end
else
return curr if curr.leaf?
return Node.get_right_neighbour(curr.right, false) unless curr.left
return Node.get_right_neighbour(curr.left, false)
end
end
end":val, :parent, :left, :right" — публичные свойства; соответственно, значение узла, ссылка на его родителя, а также ссылки на левого и правого потомков.
"root?, leaf?" — возвращают «true», если узел является корнем дерева или листом.
"left?, right?" — возвращают «true», если узел является левым или правым потомком.
"to_s" — возвращает строковое представление узла и его потомков.
"Node.get_left_neighbour(node, up_dir) и Node.get_right_neighbour(node, up_dir)" — возвращают левого или правого соседа для текущего узла. Т.к. функция вызывается рекуррентно, то присутствует параметр "up_dir". Значение по умолчанию «true», означает движение вверх по дереву. При вызове для листа этот параметр должен иметь значение по умолчанию.
Класс дерева "BTree".
class BTree
attr_accessor :root, :processor
def initialize(root=nil, &processor)
@root, @processor = nil, processor
end
def insert(val)
unless @root
@root = Node.new(val)
else
@processor.call(val, root)
end
self
end
def BTree.most_left(node)
return node unless node.left
return BTree.most_left(node.left)
end
def BTree.most_right(node)
return node unless node.right
return BTree.most_right(node.right)
end
def print_leafs
iterator = BTree.most_left(@root)
puts "Most left:", iterator.to_s
until iterator.!
iterator = Node.get_right_neighbour(iterator,true)
puts format("Right neigh: %s", iterator.to_s)
end
end
end":root, :processor" — публичные свойства; ссылка на корень дерева и на процедуру вставки элемента в дерево.
"insert(val)" — функция-обертка над процедурой вставки значения в бинарное дерево.
"BTree.most_left(node); BTree.most_right(node)" — статические функции, возвращающие крайние листы в дереве, корнем которого является переданный в качестве параметра узел.
"print_leafs" — выводит на консоль все листы слева-направо.
Использование дерева.
tree = BTree.new do |val, node|
iterator = node
until iterator.leaf?
iterator = (val < iterator.val) ? iterator.left : iterator.right
end
if val < iterator.val
iterator.left = Node.new(val)
iterator.right = Node.new(iterator.val)
else
iterator.right = Node.new(val)
iterator.left = Node.new(iterator.val)
end
iterator.val = (val + iterator.val)/2.0
iterator.left.parent, iterator.right.parent = iterator, iterator
puts iterator.to_s
end
tree.insert(10).insert(1).insert(8).insert(7).insert(7.5).insert(5).insert(3).insert(15).insert(12).insert(11)
tree.print_leafsВ последнем блоке кода создается дерево и процедура, осуществляющая вставку нового значения в дерево. В последних двух строках производится последовательная вставка значений в дерево и распечатка листьев. Вроде все просто.
Заключение
Код, конечно, сырой, но работает. Создавал его на платформе .Net + DLR (IronRuby) для возможности в будущем сделать отрисовку дерева с использованием WPF. Думаю этот код легко можно перенести как на чистый Ruby, так и на Silverlight.
Подобных реализаций наверняка полно в сети, но в продолжение серии про диаграмму Вороного решил все-таки представить свою реализацию. К тому же логика дерева адаптирована под конкретную задачу. Для меня важно разобрать отдельные моменты алгоритма [1] на практике самостоятельно, чтобы потом не натыкаться на чужие подводные камни.
Спасибо за внимание! Ваши комментарии…
Список литературы
1. Ход «Voronoi»
2. Двоичное дерево
