Encapsulation is a vital characteristic for proper object oriented implementation. In order to accomplish meaningful tasks with a given class, instances variables may need to be exposed given certain design constraints. The exposure of these instances variables are done through "getters" and "setters" which are responsible for assigning or retrieving a value to/from a particular variable (respectively). If we use the Binary Node Class from my previous post an example, the member variables "contents", "left", and "right" have been exposed by overriding the "=" operator (getter) and self-named functions.

For defining access to instance variables, Ruby provides a nice short cut through the use of the "attr_accessor" directive.

The Binary Node Class can be re-written as follows (15 lines vs. 38 lines):

class BinaryNode
   attr_accessor :contents, :left, :right
 
   @contents = nil
   @left = nil
   @right = nil
 
   public
      def initialize(data, leftChild, rightChild)
         @contents = data
         @left = leftChild
         @right = rightChild
      end
 
end

In fact, there are a few variations to access instance variables, which can be configured according to "read" and "write" privileges.

• attr_reader :variable - read only access to "variable"
• attr_writer :variable - write only access to "variable"
• attr_accessor :variable - read and write access to "variable"

The Binary Search Tree (BST) data structure is a classic computer science example of a simple, yet effective construct for managing and access information.

A BST is characterized by the following physical facts:

• Each node holds a value, and can only have upto two children
• For every node in the tree, the left subtree consists of smaller values, while the right tree consists of greater values

Binary Node Class
Below is a basic Ruby definition of our node class. It contains the standard constructor method "initialize", and variable access methods. You will also notice that the "=" operator has been overridden for the member variables.

class BinaryNode
 
   @contents = nil
   @left = nil
   @right = nil
 
   public
      def initialize(data, leftChild, rightChild)
         @contents = data
         @left = leftChild
         @right = rightChild
      end
 
      def contents
         @contents
      end
 
      def left
         @left
      end
 
      def right
         @right
      end
 
      def contents=(data)
         @contents = data
      end
 
      def left=(leaf)
         @left = leaf
      end
 
      def right=(leaf)
         @right = leaf
      end
 
end

Binary Node Unit Test
Considering we're moving onto more complex code examples now, I decided to leverage the Ruby unit test framework to create structured test cases. As you step through the code, please note the subtleties which may be easily missed -- it tests all aspects of the class definition above, including the "=" override, and the variable access methods (e.g. n.contents). A more thorough test may also include additional assertions for the "initialize" method, to verify the "left" and "right" children.

 require 'BinaryNode'
require 'test/unit'
 
class TestBinaryNode < Test::Unit::TestCase
 
   def the_test
      n = BinaryNode.new("1", nil, nil)
      assert_equal("1", n.contents)
 
      n.right = BinaryNode.new("2", nil, nil)
      assert_equal("2", n.right.contents)
 
      n.left = BinaryNode.new("0", nil, nil)
      assert_equal("0", n.left.contents)
   end
 
end

Binary Search Tree Class
Ok, so we've covered the basic data structure involved in a BST, the binary node, which we will often refer to as "leaf" as well. The BST class contains all of the fun meaty stuff that defines all of the tree operations available to a developer. Although the BinaryNode is the basic building block of a BST, it should remain invisible to the end user.

The operations we will make available via our public API will be:

• initialize: general constructor
• clear: resets the tree to empty
• empty?: boolean operator that returns true/false respectively
• find: locates the requested value in the tree
• findMin: finds the minimum value stored in the tree
• findMax: finds the maximum value stored in the tree
• insert: puts the requested value into the tree
• remove: removes the requested value from the tree
• print: simply prints out the contents of the tree, in order

Additionally, private helper functions which operate recursively, have been created to assist the public operations. A more efficient implementation could consist of loops rather than recursion, which incurs processing and storage overhead relative to traversal depth.

For the most part, if you read over the code, it is evident which helper functions support their respective public counterparts. Please note that Ruby does not allow method definitions with the same name, regardless of their signatures (i found this out through trial-and-error, so if i'm wrong, please let me know). I consider this to be a very bad weakness, and hope things change down the road.

I expect if you're reading this post, then you have a basic understanding of a BST, and I will not cover its behavior in heavy detail. However, there are three functions ([] Operator, delete, and deleteMin) which are reviewed below the following section which defines our BST class.

 require 'BinaryNode'
 
class BinarySearchTree
 
   @root = nil
 
   #begin: public members
   public 
 
      def initialize()
      end
 
      def clear()
         @root = nil
      end
 
      def empty?()
         @root.nil?
      end
 
      def find(target)
         self[locate(target, @root)]
      end
 
      def findMin()
         self[locateMin(@root)]
      end
 
      def findMax()
         self[locateMax(@root)]
      end
 
      def insert(element)
         @root = put(element, @root)
      end
 
      def remove(element)
         @root = delete(element, @root)
      end
 
      def print()
         if empty? then
            puts "Empty Tree"
         else output(@root)
         end
      end
 
   #end: public members
 
   private
   #begin: private members
 
      def [](leaf)
         return leaf.contents unless leaf.nil?
         nil
      end
 
      def locate(target, leaf)
         if leaf.nil? then return nil
         elsif leaf.contents < target then return locate(target, leaf.right)
         elsif leaf.contents > target then return locate(target, leaf.left)
         elsif leaf.contents == target then return leaf
         end
      end
 
      def locateMin(leaf)
         return nil if leaf.nil?
         return leaf if leaf.left.nil?
         return locateMin(leaf.left)
      end
 
      def locateMax(leaf)
         return nil if leaf.nil?
         return leaf if leaf.right.nil?
         return locateMax(leaf.right)
      end    
 
      def put(element, leaf)
         if leaf.nil? then leaf = BinaryNode.new(element, nil, nil)
         elsif leaf.contents < element then leaf.right = put(element, leaf.right)
         elsif leaf.contents > element then leaf.left  = put(element, leaf.left)
         end
         return leaf
      end
 
      def delete(element, leaf)
         if leaf.nil? then
            return nil
         elsif leaf.contents < element then
            leaf.right = delete(element, leaf.right)
         elsif leaf.contents > element then
            leaf.left = delete(element, leaf.left)
         elsif ( !leaf.left.nil? && !leaf.right.nil?) then
            leaf.contents = deleteMin(leaf)
         else
            leaf = (!leaf.left.nil?) ? leaf.left : leaf.right
         end
         return leaf
      end
 
      def deleteMin(tree)
         parent = tree.right
         minChild = parent.left
 
         if minChild.nil?
            tree.right = parent.right
            return parent.contents
         end
 
         while (! minChild.left.nil?)
            parent = minChild
            minChild = minChild.left
         end
 
         parent.left = minChild.right
         return minChild.contents
      end
 
      def output(leaf)
         if (!leaf.nil?) then
            output(leaf.left)
            puts leaf.contents
            output(leaf.right)
         end
      end   
 
   #end: private members
 
end

Code Review

After reviewing the BST and BinaryNode class definitions, you will notice variables beginning with the "@" symbol. If you're not familiar with Ruby, I suggest you become knowledgeable with basic class rules. In Ruby, there are local, instance, and class variables; in the same respect there are instance and class methods.

To briefly describe these concepts:

• Local variable: a variable who's scope is limited to the function or code block in which they were introduced
• Instance variable: an instance variable is denoted with the "@" character, and by default has a private class scope. Its scope is global to the instance, and therefore accessible to any of its methods
• Class variable: a class variable is denoted with the "@@" symbol, and by default has a private class scope. Unlike an instance variable, a class variable is shared across all instances of a class (read: static variable)
• Instance method: a method which is associated to a particular instance of a class
• Class method: similar to a class variable, a class method is a shared definition across all instances of a class. Moreover, a class method is universally available and does not require an instance for it to be executed (read: static method)

To illustrate the power of Ruby, I decided to override the [] operator. The implementation simply returns the contents of the given leaf node, and it's used by the public methods (e.g. self[...]). It is important to note that in Ruby, the last evaluated line of code produces the return value of a method, hence the last line in this method as "nil".

def [](leaf)
   return leaf.contents unless leaf.nil?
   nil
end

For the most part, all BST operations are fairly straightforward, except for the "delete" method which possess some complexity. The deletion operation requires a strategy which addresses three cases.

The target node to be delete is a leaf node with:

• no children: delete the given node
• 1 child: move the child into the given node's position
• 2 children - complex case, whose strategy could call for the replacement of the target node with the smallest leaf node in it's right subtree.

def delete(element, leaf)
         if leaf.nil? then
            return nil
         elsif leaf.contents < element then
            leaf.right = delete(element, leaf.right)
         elsif leaf.contents > element then
            leaf.left = delete(element, leaf.left)
         elsif ( !leaf.left.nil? && !leaf.right.nil?) then
            leaf.contents = deleteMin(leaf)
         else
            leaf = (!leaf.left.nil?) ? leaf.left : leaf.right
         end
         return leaf
      end

In order to make the "delete" operation more efficient, we can write a "deleteMin" method which searches the right subtree for the smallest value, and deletes it in one step. The inefficient implementation would require two steps within the "delete" method: one to find the minimum leaf by re-using the "findMin" method, followed by a recursive call to the "remove" method to physically delete the minimum node.

The code below illustrates the efficient approach, which utilizes a "while" loop to traverse down the "right" subtree.

def deleteMin(tree)
         parent = tree.right
         minChild = parent.left
 
         if minChild.nil?
            tree.right = nil
            return parent.contents
         end
 
         while (! minChild.left.nil?)
            parent = minChild
            minChild = minChild.left
         end
 
         parent.left = nil
         return minChild.contents
      end

The BST implementation provided in this tutorial is simply an illustration of Ruby concepts. There are many alternate approaches which could yield faster performance, or require less memory (e.g. an array implementation where traversal is calculated based on indices, loops vs. recursion, etc..).

Additionally, it should be noted that over time a BST can easily become too heavy (biased) to a certain direction (left vs. right), because there is no balancing mechanism implemented. If this were to happen, the O(log n) operations offered by a BST would fade away as the tree becomes, in the worst-case, linear.

For a more efficient BST, a balancing algorithm can be created; Adelson-Velski and Landis (AVL) trees are a perfect example of such a data structure.

I hope this has provided you with some value!

This algorithm expands on concepts derived from Insertion Sort, and effectively uses those strategies by optimizing and consolidating swap operations per scan. Wikipedia offers some great background information for Shell Sort.

The example below is coded to the "poor" implementation of Shell Sort which operates in O(N²) time₁, and room for improvements exist by optimizing the gap sequence; N/2 is the gap strategy used here. An effective gap strategy can lend a O(N^3/2) down to O(N^4/3) runtime.

def shell_sort (list)
   gap = list.length/2
   while(gap > 0)
      list[gap..list.length-1].each_with_index do |element, index|
         j = (index += gap)
         index.step(gap-1, -gap) do |j|
            if ( j > 0 && j >= gap && element < list[j-gap] ) then
               list[j] = list[j-gap]
            else
               break
            end
         end
         list[j] = element
      end
      gap /= 2
   end
   list
end

Elements that are a "gap" apart, are compared and sorted; as the gap diminishes over each repitition, elements which are closest together are eventually compared.

Code Review
Start with a gap of N/2, and iterate until adjacent elements have been processed

def shell_sort (list)
   gap = list.length/2
      while(gap > 0)

Currently Ruby does not support an iterator which starts at a given index, so we will use the standard array API to obtain a sub-list which starts from "gap" and ends at the last element. We then iterate over that sub-list, and obtain each element and index.

list[gap..list.length-1].each_with_index do |element, index|

The sublist is returned as a seperate object, and therefore it's index starts at "0"; we must compensate for this by adjusting "index" to "index + gap". Additionally, we introduce "j" here so that we can use it outside of the upcoming loop; note, it's value at this point in the sequence is arbitrary and has no meaning.

j = (index += gap)

We then take advantage of Ruby's "step" construct for integers, to loop using a custom step sequence of "-gap", starting at "gap-1". As we scan down the list, we essentially compare and swap elements, in a similar fashion to Insertion Sort.

index.step(gap-1, -gap) do |j|
   if ( j > 0 && j >= gap && element < list[j-gap] ) then
      list[j] = list[j-gap]
   else
      break
   end
end
list[j] = element

I offer the same caveat as with the Insertion Sort tutorial; I attempted rubify the code, and therefore this implementation may not be as efficient as possible (e.g. use of "step" versus other loop tactics, the use of Ruby's sub-array functionality, having to re-adjust the index, etc..). However, I hope this provides some valuable insight into both Shell Sort and Ruby.

Ruby, which is progressively gaining popularity in the industry, has struck an interest with me, and I've decided to take up the task of learning the language. Although I was first introduced to Ruby back in 2002, I never took the time to really get to know it.

Fast forward 6yrs later, and I've decided to get serious about it, and what better way to learn than to get in there and code up some common algorithms. As I venture on this journey, I will document my experience in efforts to help out others who are learning as well.

For this first example, I've coded up the simple "Insertion Sort" algorithm. Please note that in my attempts to "rubify" the algorithm, it is highly likely I may not have written it efficiently.

def insertion_sort (list)
   list.each_with_index do |element, index|
      index.downto(0) do |j|
         if (j > 0 && element < list[j-1]) then
            list[j] = list[j-1]
         else
            list[j] = element
            break
         end
      end
   end
end

Insertion sort operates on the basis that elements are sorted progressively as the code scans the list, and therefore after each scan S, elements 0 through S-1 are assumed to be in order, and element S is moved towards the left until it is in order.

Code Walkthrough
The following lines uses the standard list iterator API to obtain both the element and it's index, starting at the beginning of the list.

list.each_with_index do |element, index|

The inner loop uses the "downto" construct to start at the current index (from the outer loop), and counts backward to "0". Note that "downto" does not alter the value of "index". This loop does the work of comparing and swaping the current element with it's predecessors, and will appropriately shift "greater" ones up the list.

index.downto(0) do |j|

The following code segment defines the comparison logic in order to shift the element down the list, by moving all "greater" elements up the list. Once an appropriate location has been determined, the current element is inserted back into the list.

if (j > 0 && element < list[j-1]) then
   list[j] = list[j-1]
else
   list[j] = element
   break
end

One very important point to note is that array boundaries are somewhat loose in Ruby, and therefore an index of "-1" is considered legitimate and will not produce an array/list access violation -- it would point to the last element in the list. Therefore, in the core logic presented above, we account for that by detecting when "j" is no longer greater than "0" in our conditional statement. Regardless, in order to properly implement "insertion sort", strict boundaries are needed.


Additionally, due to Ruby's OO nature, the code presented above will work with any list of classes that support the "<" comparison operator. With that being said, Ruby also makes it possible to have lists that contain a heterogeneous set of classes since there is a lack of type-safety -- this can be both an advantage or disadvantage depending on how you intend to use this algorithm. If you're using a mixed set of classes, you would have to ensure that there is some logical ordering defined within your classes to satisfy the comparison methods.


I hope this tutorial has been helpful!