Excerpt
My previous post introduced the singly-linked list. The linked list is a widely used data structure due to its performance in inserting and deleting an element. However, if there’s an order in your dataset and you want to search for a particular item very frequently, the linked list isn’t the best choice due to it’s linear searching time. What we’re looking for is a simple data structure whose average running time for most operations is sublinear. The data structure that we are referring to is the binary search tree(BST).
## Properties of BST
The binary search tree is one type of tree data structure. It shares the same structures with the tree. But having its own properties:
- In a binary search tree, each node only contains a left child and right child;
- Each of the nodes in the left subtree has data value that is less than the node’s data value;
- Each of the nodes in the right subtree has data value th
My previous post introduced the singly-linked list. The linked list is a widely used data structure due to its performance in inserting and deleting an element. However, if there’s an order in your dataset and you want to search for a particular item very frequently, the linked list isn’t the best choice due to it’s linear searching time. What we’re looking for is a simple data structure whose average running time for most operations is sublinear. The data structure that we are referring to is the binary search tree(BST).
## Properties of BST
The binary search tree is one type of tree data structure. It shares the same structures with the tree. But having its own properties:
- In a binary search tree, each node only contains a left child and right child;
- Each of the nodes in the left subtree has data value that is less than the node’s data value;
- Each of the nodes in the right subtree has data value that is greater than (or equal to) the node’s data value
a binary search tree
You can play with it using this website to see how’s BST is structured!
# Code with me to build a BST in Ruby!
## Step 1: Create a class for the node and the BST
BST is composed of nodes. Each node has a value, and two pointers point to the left and the right child. We can implement a node class first:
```plain text
class TreeNode
attr_accessor :value, :left, :right #node is initialized with a value, and two children are nil
def initialize(value)
@value = value
@left = nil
@right = nil
end
end
```
That’s it for node class! Super simple, right?
Now let's write a BST class:
```plain text
class BST
attr_accessor :root, :size def initialize()
@root = nil
@size = 0;
end
end
```
I set two variables for the BST here: root and size because of: 1). BST must have a root. It’s the starting point of the tree. 2): For the simplicity of calculations, we can easily add or minis one to the class variable @size when we insert or delete a node.
## Step 2: Instance method: insert(value)
Recall the properties of BST: the value of the left child is less than the value itself, the value of the right child is greater than the value itself. That’s the pattern of inserting a new value. When we see a new value, we wanna compare it with root’s value, if the new value is greater than the root’s value, we go right. Otherwise, we go left.
```plain text
def insert(value)
if @root == nil
@root = TreeNode.new(value)
else
curr_node = @root
previous_node = @root #while loop helps finding the position of insertion
while curr_node != nil
previous_node = curr_node
if value < curr_node.value
curr_node = curr_node.left
else
curr_node = curr_node.right
end
end
if value < previous_node.value
previous_node.left = TreeNode.new(value)
else
previous_node.right = TreeNode.new(value)
end
end
@size += 1
end
```
## Step 3: Instance method: find_min() and find_max()
Obviously, the minimum value node is the most left child. And the maximum value node is the most right child.
```ruby
def find_max(node = self.root)
if node == nil
return nil
elsif node.right == nil
return node
end
return find_max(node.right)
end
def find_min(node = self.root)
if node == nil
return nil
elsif node.left == nil
return node
end
return find_min(node.left)
end
```
## Step 4: Instance method: contains(value)?
This is a boolean function, and it’ll return true when the BST has the value we passed in.
```ruby
def contains?(value, node = self.root)
if node == nil
return false
elsif value < node.value
return contains?(value, node.left)
elsif value > node.value
return contains?(value, node.right)
else
return true
end
end
```
The algorithm behind the code is that we recursively find the left subtree and right subtree, to see whether the value of the node matches the value we want to find.
## Step 5: Instance method: print()
For BST, there are four common traversals:
- In-order: Recursively process the left nodes first, then this node, then processes the right nodes recursively. This will result in “normal order”
- Pre-order: Process this node first, then process the left node recursively, then the right nodes recursively
- Post-order: Recursively process the left nodes, then right nodes, then this node
- Level-order: Process the nodes based on depth: the nodes closest to the root first, then successively lower nodes.
Here, I’ll implement my print() using in-order traversal:
```plain text
def print_in_order(node = self.root)
if node != nil
print "("
print_in_order(node.left)
print ", #{node.value}, "
print_in_order(node.right)
print ")"
end
end
```
## Step 6: Instance method: remove(value)
When we want to remove a node from BST, there’re three cases we need to consider:
- If the node has zero children: it’s the ‘leaf’ node, we can simply remove from the tree;
- If the node has one child(left or right child): after we remove this node, we need to promote its child to the position;
- If the node has two children: we need to find a candidate to promote. The candidates could be the smallest data of the right subtree or the largest data of the left subtree.
I draw some graphs to illustrate the cases:
```plain text
def remove(value, node = self.root)
removeHelper(value, node = self.root)
@size -= 1
node
endprivate
#this helper method will avoid the multiple size decreses in recursion
def removeHelper(value, node = self.root)
if node == nil
return nil
end
if node.value > value
node.left = removeHelper(value, node.left)
elsif node.value < value
node.right = removeHelper(value, node.right)
else
if node.left != nil && node.right != nil
temp = node
min_of_right_subtree = find_min(node.right)
node.value = min_of_right_subtree.value
node.right = removeHelper(min_of_right_subtree.value, node.right)
elsif node.left != nil
node = node.left
elsif node.right != nil
node = node.right
else
node = nil
end
end
return node
end
```
## Step 7: Instance method: clear()
clear() is a straightforward method: we set the root to nil and reset the size to zero!
```plain text
def clear()
self.root = nil
self.size = 0
end
```
## Step 8: Instance method: size()
This is the easiest method! Since we already have a class variable @size that representing the size of the tree, here, we can simply return this value:
```plain text
def size()
@size
end
```