*Created by Stan on 08-04-2023*

A binary search tree (BST) is a binary tree data structure where each node has at most two child nodes, arranged in a way that the value of the node to the left is less than or equal to the parent node, and the value of the node to the right is greater than or equal to the parent node. This property ensures that a binary search can be run on the tree, providing an efficient way to search, insert, and delete elements.

Here's a simple implementation of a binary search tree in Ruby:

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 def insert(value) @root = insert_node(@root, value) end def search(value) search_node(@root, value) end private def insert_node(node, value) return Node.new(value) if node.nil? if value <= node.value node.left = insert_node(node.left, value) else node.right = insert_node(node.right, value) end node end def search_node(node, value) return false if node.nil? if value == node.value true elsif value < node.value search_node(node.left, value) else search_node(node.right, value) end end end # Usage bst = BinarySearchTree.new bst.insert(50) bst.insert(30) bst.insert(70) bst.insert(20) bst.insert(40) bst.insert(60) bst.insert(80) puts bst.search(40) # Output: true puts bst.search(25) # Output: false

In this example, we define two classes: `Node`

and `BinarySearchTree`

. The `Node`

class represents a node in the binary search tree and has attributes for its value and its left and right children. The `BinarySearchTree`

class manages the tree and provides methods for inserting and searching elements in the tree.

The `insert`

method of the `BinarySearchTree`

class inserts a new value into the tree by calling the `insert_node`

private method, which takes a node and a value as its arguments. If the node is `nil`

, it creates a new node with the given value. Otherwise, it compares the value to the current node's value and inserts it either into the left subtree if the value is less than or equal to the current node's value or into the right subtree if the value is greater than the current node's value.

The `search`

method of the `BinarySearchTree`

class searches for a value in the tree by calling the `search_node`

private method. This method recursively traverses the tree, checking whether the value matches the current node's value, or whether it should search in the left subtree (if the value is less than the current node's value) or the right subtree (if the value is greater than the current node's value). If the value is not found in the tree, it returns `false`

.

Architecture