Введение

В этой статье хочется представить реализацию дерева бинарного поиска для задачи, изложенной в статье [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. Двоичное дерево

Ход «Voronoi». Часть 2 — Бинарное дерево