The move “Voronoi”. Part 2 - Binary Tree

Introduction

In this article, I would like to present the implementation of a binary search tree for the problem described in [ 1 ]. In the task described there, the “sweeping line” algorithm is used, for which a binary tree is needed with the ability to move not only from the root of the tree to the child nodes and leaves, but also along the leaves separately, starting from the outermost leaf (left or right). The task seemed simple enough, so I didn’t search for ready-made implementations for a long time and decided to do it myself. At the same time, he set an additional task - setting the procedure for adding a new leaf to the tree outside.

A bit of theory

There will be very little theory. The bulk of information can be obtained in Wikipedia [ 2 ]. In short, the narrative is a tree data structure in which each element can have two children. In my case, there will be two children, which is a consequence of the task set in [ 1 ]. Otherwise the node will be a sheet, i.e. no children at all. When a new element is added to the tree, the page is descended to the nearest by value sheet. The found sheet is replaced with a tree consisting of one parent and two children. The parent receives a value that is equal to the arithmetic mean of the values ​​of the new element and replaced by the leaf tree. Children are our new element and the replaced sheet, whose positions (on the left or on the right) depend on which element has a lower value. A node with a lower value is on the left. When adding a subtree, it is necessary to add / update links between the three elements indicated (parent-child links).
The descent, which was mentioned above, is also made according to the principle “more-less, left-right”. Compares the value of the node with the value of the new element. If the new value is less than the value of the node, then we go down to the left, and otherwise (> =) we move to the right. How this works is illustrated in the next section.
As a result, we get a sorted set of leaves and nodes connected to each other (“parent-child”, “left”, “right”). Next, you need to organize the transition from one sheet to another, a neighbor to the right or left. This logic had to be tricky the most. It is better to describe it in pictures (see the next section).

Logic tree in illustrations

Start by adding an item. If the tree is empty, then the new element becomes the root. Otherwise, create a subtree instead of one of the nodes. In fig. 1 depicts the addition of the first two elements.

Figure 1. Insert a new item
')
After the tree is filled, you can walk through the leaves, for example, from left to right. In fig. 2 shows an example of a tree. Black arrows indicate transitions from one sheet to another (the neighbor to the right).

Figure 2. Leaf transitions

Why do I need to move through the leaves? In the task of constructing a Voronoi diagram, the leaves of the tree correspond to the “arches”. For each sequence of three arches, a “circle event” may potentially arise. Therefore, you need to be able to move through the arches, over leaves in a tree, as in a linear doubly linked list. At first, I decided to implement this feature only through functional recursion. As can be seen from fig. 2, transitions of the form “7 -> 8” turned out to be the most difficult moment. When using only recursion, it fell into an eternal cycle between "7" and "6.75". I solved the problem by adding a cycle that was used for the transition to the first parent who is not a right-wing child (in this case, it is a transition from “7” to “6”). When moving from the rightmost sheet (“15”), the cycle will lead to the root of the whole tree, after which we will get “nil” in Ruby notation and the search for neighbors on the right will end.

Code

The node class is " 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 " - public properties; accordingly, the value of the node, the link to its parent, and also links to the left and right descendants.
" root?, leaf? " - return “true” if the node is a root of a tree or a leaf.
" left ?, right? " - return “true” if the node is a left or right descendant.
" to_s " - returns a string representation of the node and its descendants.
" Node.get_left_neighbour (node, up_dir) and Node.get_right_neighbour (node, up_dir) " - return the left or right neighbor for the current node. Because the function is called recurrently, then the " up_dir " parameter is present. The default value is “true”, which means moving up the tree. When calling for a sheet, this parameter should have a default value.
Tree class " 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 " - public properties; reference to the root of the tree and the procedure for inserting an element into the tree.
" insert (val) " is a wrapper function over the procedure of inserting a value into a binary tree.
" BTree.most_left (node); BTree.most_right (node) " are static functions that return the outermost leaves in the tree, the root of which is the node passed as a parameter.
" print_leafs " - prints all sheets from left to right on the console.
Use of wood.

 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 

In the last block of code, a tree is created and a procedure that inserts a new value into the tree. In the last two lines, values ​​are inserted into the tree and leaves are printed. It seems simple.

Conclusion

The code, of course, is raw, but it works. Created it on the .Net + DLR (IronRuby) platform to enable future tree rendering using WPF. I think this code can be easily transferred to both pure Ruby and Silverlight.
Such implementations are probably fully online, but in the continuation of the series about the Voronoi diagram, I decided to still present my implementation. In addition, the logic of the tree is adapted for a specific task. It is important for me to parse individual moments of the algorithm [ 1 ] in practice on my own, in order not to stumble upon other people's pitfalls.
Thanks for attention! Your comments…

Bibliography

1. The move “Voronoi”
2. Binary tree