Binary Search Tree Implementation in Ruby

1. Introduction

A Binary Search Tree (BST) is a binary tree where each node has a comparable value, and the left subtree of a node contains only nodes with values less than the node's value, while the right subtree only nodes with values greater than the node's value. This provides an efficient way of inserting, looking up, and deleting items, as each decision cuts down the possibilities in half (similar to binary search).

2. Implementation Steps

1. Define a Node class with attributes value, left, and right.

2. Initialize a BinarySearchTree class with a root node.

3. Implement the insert method to add nodes in accordance with BST properties.

4. Implement a search method to find a value in the BST.

5. Implement the delete method to remove nodes from the BST.

6. Implement a display method to print the tree in an in-order traversal.

3. Implementation in Ruby Programming

class Node
    attr_accessor :value, :left, :right
    def initialize(value)
        @value = value
        @left = nil
        @right = nil
    end
end
class BinarySearchTree
    def initialize
        @root = nil
    end
    # Insert value into the BST
    def insert(value)
        @root = insert_recursive(@root, value)
    end
    # Search for a value in the BST
    def search(value)
        search_recursive(@root, value)
    end
    # Delete a value from the BST
    def delete(value)
        @root = delete_recursive(@root, value)
    end
    # Display BST in in-order traversal
    def display
        display_recursive(@root)
    end
    private
    def insert_recursive(node, value)
        return Node.new(value) if node.nil?
        if value < node.value
            node.left = insert_recursive(node.left, value)
        elsif value > node.value
            node.right = insert_recursive(node.right, value)
        end
        node
    end
    def search_recursive(node, value)
        return false if node.nil?
        return true if node.value == value
        value < node.value ? search_recursive(node.left, value) : search_recursive(node.right, value)
    end
    def delete_recursive(node, value)
        return nil if node.nil?
        if value < node.value
            node.left = delete_recursive(node.left, value)
        elsif value > node.value
            node.right = delete_recursive(node.right, value)
        else
            return node.right if node.left.nil?
            return node.left if node.right.nil?
            min_larger_node = find_min(node.right)
            node.value = min_larger_node.value
            node.right = delete_recursive(node.right, min_larger_node.value)
        end
        node
    end
    def find_min(node)
        current = node
        current = current.left while current.left
        current
    end
    def display_recursive(node)
        return if node.nil?
        display_recursive(node.left)
        puts node.value
        display_recursive(node.right)
    end
end
# Client code
bst = BinarySearchTree.new
[50, 30, 70, 20, 40, 60, 80].each { |i| bst.insert(i) }
puts "In-order traversal of BST:"
bst.display
puts "Searching for 25 in BST: #{bst.search(25)}"
puts "Searching for 70 in BST: #{bst.search(70)}"
bst.delete(70)
puts "After deleting 70, in-order traversal:"
bst.display

Output:

In-order traversal of BST:
20
30
40
50
60
70
80
Searching for 25 in BST: false
Searching for 70 in BST: true
After deleting 70, in-order traversal:
20
30
40
50
60
80

Explanation:

1. The Node class represents each element in the BST. Each node has a value, a left child, and a right child.

2. The BinarySearchTree class initializes with a root node set to nil.

3. The insert method adds a value to the tree according to BST properties.

4. The search method looks for a value in the BST and returns a boolean.

5. The delete method removes a node with a given value from the BST.

6. The private helper functions facilitate various BST operations, including insert_recursive, search_recursive, delete_recursive, and display_recursive. The find_min function retrieves the smallest node from the right subtree, used during node deletion.

7. The client code demonstrates insertion, display, search, and deletion operations on the BST.