Binary search algorithm

Today’s post is a follow-on from the original Part 1, an introduction to Binary Search Tree. For the sake of simplicity and coherency I will use the same values in the nodes. As a different means to writing out content in a blog post, I’ve chosen to use RSpec to communicate intent and elaborate on the code as a form of self-blog. 

So to kick off, I will present the actual code for the Binary Search Tree, supporting only two main sets of functionality, insertion and search. Thereafter, the spec file.

# Kudos to Phil McClure (rubyalgorithms.com)

module Trees
  class BinarySearchTree
    attr_reader :root

    class Node
      attr_reader :parent, :left, :right

      def initialize(value)
        @parent = value
        @left = nil
        @right = nil
      end

      def insert(value)
        if value <= @parent
          @left.nil? ? @left = Node.new(value) : @left.insert(value)
        elsif value > @parent
          @right.nil? ? @right = Node.new(value) : @right.insert(value)
        end
      end
    end

    def insert(value)
      if @root.nil?
        @root = Node.new(value)
      else
        @root.insert(value)
      end
    end

    def search(value, node=@root)
      return nil if node.nil?
      if value < node.parent
        search(value, node.left)
      elsif value > node.parent
        search(value, node.right)
      else
        return node
      end
    end

    def initialize
      @root = nil
    end
  end
end

And the spec file

describe Trees::BinarySearchTree do
  before :each do
    @bst = Trees::BinarySearchTree.new
  end

  context 'During initialization' do
    it 'should initialize with a nil root value' do
      expect(@bst.root).to eq nil
    end
  end

  context 'Interface' do
    it 'should allow a new value to be inserted as a node' do
      @bst.insert(15)
      @bst.insert(10)
      bottom_left_of_root = @bst.root.left
      expect(bottom_left_of_root.parent).to eq 10
      expect(bottom_left_of_root.left).to be nil
      expect(bottom_left_of_root.right).to be nil
    end

    it 'should add values less than parent to the left as nodes' do
      @bst.insert(15)
      @bst.insert(10)
      bottom_left_of_root = @bst.root.left
      expect(bottom_left_of_root.parent).to eq 10
      expect(bottom_left_of_root.left).to be nil
      expect(bottom_left_of_root.right).to be nil
    end

    it 'should add values greater than parent to the right as nodes' do
      @bst.insert(15)
      @bst.insert(20)
      bottom_right_of_root = @bst.root.right
      expect(bottom_right_of_root.parent).to eq 20
      expect(bottom_right_of_root.left).to be nil
      expect(bottom_right_of_root.right).to be nil
    end
  end

  context 'Inserting' do
    it 'should assign first value to root, if root is nil' do
      @bst.insert(1)
      expect(@bst.root.parent).to eq 1
    end

    it 'should build a binary search tree' do
      @bst.insert(15)
      @bst.insert(10)
      @bst.insert(8)
      @bst.insert(12)
      @bst.insert(20)
      @bst.insert(17)
      @bst.insert(25)
      expect(@bst.root.left.left.parent).to eq 8
      expect(@bst.root.left.right.parent).to eq 12
      expect(@bst.root.right.left.parent).to eq 17
      expect(@bst.root.right.right.parent).to eq 25
    end
  end

  context 'Search' do
    it 'should traverse the tree and find a matching leaf on the right' do
      @bst.insert(15)
      @bst.insert(10)
      @bst.insert(8)
      @bst.insert(12)
      @bst.insert(20)
      @bst.insert(17)
      @bst.insert(25)
      expect(@bst.search(17).parent).to eq 17
    end

    it 'should traverse the tree and find a matching leaf on the left' do
      @bst.insert(15)
      @bst.insert(10)
      @bst.insert(8)
      @bst.insert(12)
      @bst.insert(20)
      @bst.insert(17)
      @bst.insert(25)
      expect(@bst.search(12).parent).to eq 12
    end

    it 'should traverse the tree and find the root node if it is the search value' do
      @bst.insert(15)
      @bst.insert(10)
      @bst.insert(8)
      @bst.insert(12)
      @bst.insert(20)
      @bst.insert(17)
      @bst.insert(25)
      expect(@bst.search(15).parent).to eq 15
    end
  end
end

Binary search basics

 

What is a Binary Search Tree?

Stop. Before we even commence to look at understanding what this is, let’s build up a mental model first, so when the definition is presented we have some context and secondly we have a pool of terms that we can use and that makes sense. Above in the funky diagram above is a basic tree. It has a root node (parent node) and child nodes (A and F). Obviously based on context the role can change. So if we traversed the tree to Node A, it would be the parent node (not root node), with two child nodes, node B on the left and node C on the right. We can call A and F sub-trees if you will. Now that’s pretty basic. 

 

Binary search numeric

Now consider the same tree above, but instead of letters we insert numbers. Now what’s interesting to note, that the value of all nodes in the left subtree is lesser or equal than the value of all nodes in the right subtree

LEFT => Let’s check quickly, 10 (parent) + 8 (left child) + 12 (right child) = 20. 

RIGHT => 20 (parent) + 17 (left child) + 25 (right child) = 62.

Going back to what we said above, is that true? (value of all nodes in left subtree, less or equal to value of all nodes on the right?)

20 < 62 = TRUE. 

Excellent, we making progress! But, that principle should also apply to the subtrees.If we traverse left to node 10, it is parent to 8 and 12. 8 < 12 = TRUE. So there is no violation. When we traverse to the right to node 20, it is a parent to 17 and 25. 17 < 25 = TRUE. This principle is the important attribute that defines a Binary Search Tree. But there is one more! 

Binary search trees in using the binary search algorithm requires “ordering” and as such, each parent node will have a value, whose children on the left, are smaller than it. On the right, will have children whose values are greater. So if we traverse and visit node 10. It has a left-node of 8 (which is < 10) and a right-node of 12 (which is > 10). The same applies if we visit node 20 on the right. Being parent, it has a left-node of 17, which is less than itself (20). And it has a right child node of 25, which is greater than itself. Awesome!

These two principles applied, is a Binary Search Tree.

Now let’s take in Wikipedia’s definition:

“In computer science, binary search trees (BST), sometimes called ordered or sorted binary trees, are a particular type of containers: data structures that store “items” (such as numbers, names etc.) in memory. They allow fast lookup, addition and removal of items, and can be used to implement either dynamic sets of items, or lookup tables that allow finding an item by its key (e.g., finding the phone number of a person by name).

 

Binary search trees keep their keys in sorted order, so that lookup and other operations can use the principle of binary search: when looking for a key in a tree (or a place to insert a new key), they traverse the tree from root to leaf, making comparisons to keys stored in the nodes of the tree and deciding, based on the comparison, to continue searching in the left or right subtrees. On average, this means that each comparison allows the operations to skip about half of the tree, so that each lookup, insertion or deletion takes time proportional to the logarithm of the number of items stored in the tree. This is much better than the linear time required to find items by key in an (unsorted) array, but slower than the corresponding operations on hash tables.”


Before we leave off, binary search trees have a best running time of O(log n). That is really efficient algorithm, where at the growth of the input over time, the time of the algorithm wanes.

 

References: