Class: DS::BinarySearchTree

Inherits:
BinaryTree show all
Defined in:
lib/ds/trees/binary_search_tree.rb

Instance Attribute Summary

Attributes inherited from Tree

#children, #data

Class Method Summary collapse

Instance Method Summary collapse

Methods inherited from BinaryTree

#<<, #left, #left=, #right, #right=

Methods inherited from Tree

#<<, #each, #get_leaves, h, #height, #initialize, #izometric?, #leaf?, #leaf_count, #levels, #lowest_height, #mirror!, #to_a, #width

Constructor Details

This class inherits a constructor from DS::Tree

Class Method Details

.from_array(arr) ⇒ Object

Creates new search tree from array.



5
6
7
8
9
10
11
 
# File 'lib/ds/trees/binary_search_tree.rb', line 5

def self.from_array(arr)
  tree = BinarySearchTree.new(arr.shift)
  arr.each do |e|
    tree.insert e
  end
  tree
end

.valid?(other) ⇒ Boolean

Checks if tree is valid Binary Search Tree.



27
28
29
30
31
 
# File 'lib/ds/trees/binary_search_tree.rb', line 27

def BinarySearchTree.valid?(other)
  walker = TreeWalker.new(other)
  walker.traverse(:inorder)
  walker.visited.extend(ArrayX).sorted?
end

Instance Method Details

#insert(x) ⇒ Object

Inserts new element.



14
15
16
17
18
19
20
21
22
23
24
 
# File 'lib/ds/trees/binary_search_tree.rb', line 14

def insert x
  if x > @data and right.nil?
    self.right = BinarySearchTree.new(x)
  elsif x <= @data and left.nil?
    self.left = BinarySearchTree.new(x)
  elsif x > @data
    right.insert x
  else
    left.insert x
  end
end