A binary search tree is an ordered tree which nodes contain at most two child nodes, with the left child node smaller than parent node and the right child node larger than parent node.
A balanced binary search tree is a binary search tree where the difference between heights of left subtree and right subtree of every node is not more than 1.
This project contains a Ruby implementation of balanced binary search tree.