Class: CollectionUtils::TreeUtils::BST

Inherits:
CollectionUtils::Tree
  • Object
show all
Defined in:
lib/collection_utils/tree_utils/bst.rb

Instance Method Summary collapse

Constructor Details

#initialize(arr = []) ⇒ BST

Returns a new instance of BST.



109
110
111
112
113
114
115
116
117
 
# File 'lib/collection_utils/tree_utils/bst.rb', line 109

def initialize(arr = [])
  @size = 0
  @root = nil
  @incomplete_set = CollectionUtils::Set.new()
  @leaf_set = CollectionUtils::Set.new()
  arr.each do |element|
    insert(element)
  end
end

Instance Method Details

#delete(element) ⇒ Object

Delete would delete the element in BST and balance the BST accordingly. The delete option uses the BST property that is every node has lesser value on the left side and larger value lies on the right side. This operation is in O(logn)

> @bst = CollectionUtils::TreeUtils::BST.new()

> # BST would look like this

> # 5

> # / \

> # 2 6

> # \

> # 3

> # \

> # 4

> @bst.insert(5)

> # Now BST would look like this

> # 6

> # /

> # 2

> # \

> # 3

> # \

> # 4

Examples:

if tree has values [5,2,3,4,6]

Parameters:

  • element —

    Element which needs to be deleted from BST



181
182
183
 
# File 'lib/collection_utils/tree_utils/bst.rb', line 181

def delete(element)
  delete_node(element, @root)
end

#insert(element) ⇒ Object

Insert would insert the next element in BST according to BST properties that is if element added is less than the parent_node then element will be at left side of the node else will be on the right side of the node. This operation is in O(logn)

> @bst = CollectionUtils::TreeUtils::BST.new()

> # BST would look like this

> # 5

> # /

> # 2

> # \

> # 3

> # \

> # 4

> @bst.insert(6)

> # Now BST would look like this

> # 5

> # / \

> # 2 6

> # \

> # 3

> # \

> # 4

Examples:

if tree has values [5,2,3,4]

Parameters:

  • element —

    Element which needs to be added to BST



144
145
146
147
148
149
150
151
152
153
154
155
 
# File 'lib/collection_utils/tree_utils/bst.rb', line 144

def insert(element)
  node = Node.new(element)
  if is_empty?
    @root = node
    @root.level = 1
    @level = 1
    @size += 1
    @leaf_set.insert(node)
    return
  end
  insert_node(node, @root)
end

#largest ⇒ Object

Rightmost value will be the largest value returned using this function This operation is in O(logn)

> @bst = CollectionUtils::TreeUtils::BST.new()

> # BST would look like this

> # 5

> # / \

> # 2 6

> # \

> # 3

> # \

> # 4

> value = @bst.largest

> value == 6

Examples:

if tree has values [5,2,3,4,6]

Returns:

  • element which is largest in the BST



219
220
221
 
# File 'lib/collection_utils/tree_utils/bst.rb', line 219

def largest
  find_largest(@root)
end

#smallest ⇒ Object

Leftmost value will be the smallest value returned using this function This operation is in O(logn)

> @bst = CollectionUtils::TreeUtils::BST.new()

> # BST would look like this

> # 5

> # / \

> # 2 6

> # \

> # 3

> # \

> # 4

> value = @bst.smallest

> value == 2

Examples:

if tree has values [5,2,3,4,6]

Returns:

  • element which is smallest in the BST



200
201
202
 
# File 'lib/collection_utils/tree_utils/bst.rb', line 200

def smallest
  find_smallest(@root)
end