Mastering data structures in Ruby — Binary Trees

Ale Miralles
Nov 10, 2018 · 6 min read
          13
/ \
/ \
/ \
8 17
/ \ / \
1 11 15 25
/\ /\ /\ /\
x x x x x x x x

Binary Trees Interface

The interface of a binary tree is tightly coupled with the way we are going to use it. For instance, an AVL Tree (binary search) will have methods to rotate and balance whereas a regular one will not.

      +          =
/ \ / \
1 * a b
/\
2 3

Implementation Details

Initialize

This is the tree’s constructor it sets the root node of the tree an initializes its size.

def initialize root
self.root = root
self.size = 1
end

Insert Left

This method inserts a new node rooted at the left child of the specified node.

def insert_left(node, data)
return unless node
raise "Can't override nodes :(" if node.left
self.size += 1
node.left = Node.new node, data
end

Insert Right

This method works like insert_left but uses the right child instead. The complexity of this method is O(1).

def insert_right(node, data)
return unless node
raise "Can't override nodes :(" if node.right
self.size += 1
node.right = Node.new node, data
end

Remove Left

This method removes the subtree that’s rooted at the left child of the given node.

def remove_left(node)
if node&.left
remove_left(node.left)
remove_right(node.left)
node.left = nil
self.size -= 1
end
end

Remove Right

This method removes the subtree that’s rooted at the left child of the given node.

def remove_right(node)
if node&.right
remove_left node.right
remove_right node.right
node.right = nil
self.size -= 1
end
end

Merge

This is a class method that creates a new binary tree by merging two existing ones.

  • Create an empty tree to hold the merge.
  • Take the merged tree and point the left child of its root node to the root node of the left tree.
  • Take the merged tree and point the right child of its root node to the root node of the right tree.
  • Adjust the size in the merged tree.
def self.merge left_tree, right_tree, data = nil
raise "Can't merge nil trees." unless left_tree && right_tree
root = Node.new(nil, data);
res = BTree.new root
res.root.left = left_tree.root
res.root.right = right_tree.root
res.size = left_tree.size + right_tree.size
res
end

Print

This method prints the contents of the current tree recursively applying a “pretty” format (actually, it’s just indentation, but still…)

def print
print_rec self.root
end
private
def print_rec node, indent=0
print_node node, indent
print_rec node.lhs, indent + 1 if node&.lhs
print_rec node.rhs, indent + 1 if node&.rhs
end
def print_node node, indent
data = node&.data&.to_s || "nil"
puts data.rjust indent * 4, " "
end

When to use trees

Trees are one of the most used data structure in CS. In the wild you can find trees in the source code of database systems, user interfaces, data compression algorithms, parsers, and schedules, just to name a few. So, they are pretty much everywhere.

Data Structures From Scratch — Ruby Edition.

amiralles

Concise programming articles for those who code

Ale Miralles

Written by

There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors.

amiralles

amiralles

Concise programming articles for those who code