Last active
July 27, 2016 23:04
-
-
Save seanhandley/ec673df7dd75b38d04129fd01f6ae870 to your computer and use it in GitHub Desktop.
A simple binary tree structure
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
module BinaryTree | |
class Node | |
attr_reader :element | |
attr_accessor :left, :right | |
def initialize(e=nil) | |
@element = e | |
end | |
def traverse | |
@traversal = [] | |
traverse_node(self) | |
@traversal | |
end | |
def insert(e) | |
insert_element(self, e) | |
end | |
private | |
def traverse_node(node) | |
return unless node | |
traverse_node(node.left) | |
@traversal << node.element | |
traverse_node(node.right) | |
end | |
def insert_element(node, e) | |
(node.element = e and return) unless node.element | |
n = node.element > e ? node.left : node.right | |
n ? insert_element(node.left, e) : node.left = BinaryTree::Node.new(e) | |
end | |
end | |
end | |
def input | |
(1..1000).to_a.shuffle | |
end | |
def tree | |
input = input.shuffle | |
tree = BinaryTree::Node.new | |
input.each do |i| | |
tree.insert(i) | |
end | |
tree.traverse | |
end | |
def test | |
s = Time.now | |
iterations = 20_000 | |
iterations.times { raise "Fail!" unless tree = input.sort } | |
d = Time.now - s | |
average = "%8f" % (d / iterations.to_f) | |
puts "Binary tree has correctly ordered elements #{iterations} times in #{d} seconds. Average time per sort: #{average} seconds." | |
end | |
test |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment