Skip to content

Instantly share code, notes, and snippets.

@JoshCheek
Created July 22, 2015 17:06
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save JoshCheek/7c947ab348b9411b1343 to your computer and use it in GitHub Desktop.
Save JoshCheek/7c947ab348b9411b1343 to your computer and use it in GitHub Desktop.
A balanced BST
class BalancedBst
module Empty
extend self
def <<(data)
BalancedBst.new data
end
def >>(data)
self
end
def each
self
end
def inspect
""
end
end
def initialize(data, left=Empty, right=Empty)
@data, @left, @right, @current = data, left, right, [:left, :right]
end
def <<(data)
@current.first == :left ?
insert_left(data) :
insert_right(data)
@current.rotate!
self
end
def each(&block)
@left.each &block
block.call @data
@right.each &block
end
def inspect
llines = @left.inspect.lines.map(&:chomp)
rlines = @right.inspect.lines.map(&:chomp)
num_lines = [llines.length, rlines.length].max
(num_lines - llines.length).times { llines << "" }
(num_lines - rlines.length).times { rlines << "" }
line_length = [*llines, *rlines, ""].map(&:length).max
lines = llines.zip(rlines).map { |lline, rline|
lline.chomp.rjust(line_length, ' ') << ' ' << rline.chomp.ljust(line_length, ' ') << "\n"
}
[ @data.inspect.center(line_length*2+1, ' ') << "\n",
*lines
].join
end
private
def insert_left(data)
if data < @data
@left <<= data
else
@left <<= @data
@data = data
end
end
def insert_right(data)
if data < @data
@right <<= @data
@data = data
else
@right <<= data
end
end
end
tree = BalancedBst::Empty
15.times { |i|
tree <<= i
# => 0
#
# , 1
# 0
#
# , 1
# 0 2
#
# , 3
# 1 2
# 0
#
# , 3
# 1 4
# 0 2
#
# , 5
# 1 4
# 0 3 2
#
# , 5
# 1 4
# 0 3 2 6
#
# , 7
# 5 4
# 1 3 2 6
# 0
#
# , 7
# 5 8
# 1 3 4 6
# 0 2
#
# , 9
# 5 8
# 1 7 4 6
# 0 3 2
#
# , 9
# 5 8
# 1 7 4 10
# 0 3 2 6
#
# , 11
# 9 8
# 1 7 4 10
# 0 5 3 2 6
#
# , 11
# 9 12
# 1 7 4 10
# 0 5 3 2 8 6
#
# , 13
# 9 12
# 1 7 4 10
# 0 5 3 11 2 8 6
#
# , 13
# 9 12
# 1 7 4 10
# 0 5 3 11 2 8 6 14
}
tree
# =>   13
# 9 12
# 1 7 4 10
# 0 5 3 11 2 8 6 14
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment