Class: DSA::BinarySearchTree

Inherits:
Object
  • Object
show all
Defined in:
lib/dsa-ruby/binary_search_tree.rb

Overview

DSA::BinarySearchTree - A binary search tree data structure.

Supports insertion, deletion, search, and tree traversals. Duplicate values are not inserted.

Examples:

bst = DSA::BinarySearchTree.new
bst.insert(5).insert(3).insert(7).insert(1).insert(4)
bst.search(3)       # => true
bst.min             # => 1
bst.max             # => 7
bst.inorder         # => [1, 3, 4, 5, 7]
bst.preorder        # => [5, 3, 1, 4, 7]
bst.postorder       # => [1, 4, 3, 7, 5]
bst.delete(3)

Defined Under Namespace

Classes: Node

Instance Method Summary collapse

Constructor Details

#initialize ⇒ DSA::BinarySearchTree

Initialize a new empty binary search tree.



30
31
32
33
 
# File 'lib/dsa-ruby/binary_search_tree.rb', line 30

def initialize
  @root = nil
  @size = 0
end

Instance Method Details

#delete(val) ⇒ Boolean

Deletes a value from the tree if it exists.

Examples:

bst.insert(5).insert(3)
bst.delete(3)  # => true
bst.delete(8)  # => false

Parameters:

  • val (Comparable) —

    the value to delete

Returns:

  • (Boolean) —

    true if the value was deleted, false if not found



67
68
69
70
71
 
# File 'lib/dsa-ruby/binary_search_tree.rb', line 67

def delete(val)
  @root, deleted = delete_recursive(@root, val)
  @size -= 1 if deleted
  deleted
end

#empty? ⇒ Boolean

Checks if the tree is empty.

Examples:

bst = DSA::BinarySearchTree.new
bst.empty?  # => true

Returns:

  • (Boolean) —

    true if the tree contains no elements



152
153
154
 
# File 'lib/dsa-ruby/binary_search_tree.rb', line 152

def empty?
  @size == 0
end

#inorder ⇒ Array<Comparable>

Returns an array of values in inorder traversal (left, root, right).

Examples:

bst.insert(5).insert(3).insert(7)
bst.inorder  # => [3, 5, 7]

Returns:

  • (Array<Comparable>) —

    values in inorder sequence (sorted order)



103
104
105
106
107
108
 
# File 'lib/dsa-ruby/binary_search_tree.rb', line 103

def inorder
  return [] if empty?
  result = []
  traverse_inorder(@root, result)
  result
end

#insert(val) ⇒ DSA::BinarySearchTree

Inserts a value into the tree. Duplicates are ignored.

Examples:

bst.insert(5).insert(3).insert(7)

Parameters:

  • val (Comparable) —

    the value to insert

Returns:



41
42
43
44
45
 
# File 'lib/dsa-ruby/binary_search_tree.rb', line 41

def insert(val)
  @root, added = insert_recursive(@root, val)
  @size += 1 if added
  self
end

#max ⇒ Comparable

Returns the maximum value in the tree.

Examples:

bst.insert(5).insert(3).insert(7)
bst.max  # => 7

Returns:

  • (Comparable) —

    the maximum value

Raises:

  • (IndexError) —

    if the tree is empty



92
93
94
95
 
# File 'lib/dsa-ruby/binary_search_tree.rb', line 92

def max
  raise IndexError, "tree is empty" if empty?
  find_max(@root).val
end

#min ⇒ Comparable

Returns the minimum value in the tree.

Examples:

bst.insert(5).insert(3).insert(1)
bst.min  # => 1

Returns:

  • (Comparable) —

    the minimum value

Raises:

  • (IndexError) —

    if the tree is empty



80
81
82
83
 
# File 'lib/dsa-ruby/binary_search_tree.rb', line 80

def min
  raise IndexError, "tree is empty" if empty?
  find_min(@root).val
end

#postorder ⇒ Array<Comparable>

Returns an array of values in postorder traversal (left, right, root).

Examples:

bst.insert(5).insert(3).insert(7)
bst.postorder  # => [3, 7, 5]

Returns:

  • (Array<Comparable>) —

    values in postorder sequence



129
130
131
132
133
134
 
# File 'lib/dsa-ruby/binary_search_tree.rb', line 129

def postorder
  return [] if empty?
  result = []
  traverse_postorder(@root, result)
  result
end

#preorder ⇒ Array<Comparable>

Returns an array of values in preorder traversal (root, left, right).

Examples:

bst.insert(5).insert(3).insert(7)
bst.preorder  # => [5, 3, 7]

Returns:

  • (Array<Comparable>) —

    values in preorder sequence



116
117
118
119
120
121
 
# File 'lib/dsa-ruby/binary_search_tree.rb', line 116

def preorder
  return [] if empty?
  result = []
  traverse_preorder(@root, result)
  result
end

#search(val) ⇒ Boolean

Searches for a value in the tree.

Examples:

bst.insert(5)
bst.search(5)  # => true
bst.search(3)  # => false

Parameters:

  • val (Comparable) —

    the value to search for

Returns:

  • (Boolean) —

    true if the value exists in the tree



55
56
57
 
# File 'lib/dsa-ruby/binary_search_tree.rb', line 55

def search(val)
  !!find_node(@root, val)
end

#size ⇒ Integer

Returns the number of elements in the tree.

Examples:

bst.insert(5).insert(3)
bst.size  # => 2

Returns:

  • (Integer) —

    the number of elements



142
143
144
 
# File 'lib/dsa-ruby/binary_search_tree.rb', line 142

def size
  @size
end

#to_a ⇒ Array<Comparable>

Returns a defensive copy of the tree as an array (inorder traversal).

Examples:

bst.insert(5).insert(3).insert(7)
bst.to_a  # => [3, 5, 7]

Returns:

  • (Array<Comparable>) —

    an array of values in sorted order



162
163
164
 
# File 'lib/dsa-ruby/binary_search_tree.rb', line 162

def to_a
  inorder
end