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 



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

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

.valid?(other) ⇒ Boolean

Returns:

  • (Boolean) 


25
26
27
28
29
 
# File 'lib/ds/trees/binary_search_tree.rb', line 25

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

Instance Method Details

#insert(x) ⇒ Object 



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

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