Class: Algorithmable::Searches::BinarySearchTree

Inherits:
Object
  • Object
show all
Defined in:
lib/algorithmable/search/binary_search_tree.rb

Instance Method Summary collapse

Constructor Details

#initialize(key_type, value_type) ⇒ BinarySearchTree

Returns a new instance of BinarySearchTree.



4
5
6
7
8
 
# File 'lib/algorithmable/search/binary_search_tree.rb', line 4

def initialize(key_type, value_type)
  @key_type = key_type
  @value_type = value_type
  @root = nil
end

Instance Method Details

#[](key) ⇒ Object 



23
24
25
26
 
# File 'lib/algorithmable/search/binary_search_tree.rb', line 23

def [](key)
  assert_key_type(key)
  impl_get(@root, key)
end

#[]=(key, value) ⇒ Object 



28
29
30
31
32
33
34
 
# File 'lib/algorithmable/search/binary_search_tree.rb', line 28

def []=(key, value)
  assert_value_type(value)
  assert_key_type(key)
  delete key
  @root = impl_put(@root, key, value)
  check_tree_consistency
end

#ceiling(key) ⇒ Object 



70
71
72
73
74
75
76
 
# File 'lib/algorithmable/search/binary_search_tree.rb', line 70

def ceiling(key)
  assert_key_type(key)
  return unless key || empty?
  found = impl_ceiling(@root, key)
  return unless found
  found.key
end

#delete(key) ⇒ Object 



46
47
48
49
50
 
# File 'lib/algorithmable/search/binary_search_tree.rb', line 46

def delete(key)
  assert_key_type(key)
  @root = impl_delete(@root, key)
  check_tree_consistency
end

#delete_max ⇒ Object 



41
42
43
44
 
# File 'lib/algorithmable/search/binary_search_tree.rb', line 41

def delete_max
  @root = impl_delete_max @root
  check_tree_consistency
end

#delete_min ⇒ Object 



36
37
38
39
 
# File 'lib/algorithmable/search/binary_search_tree.rb', line 36

def delete_min
  @root = impl_delete_min @root
  check_tree_consistency
end

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


10
11
12
 
# File 'lib/algorithmable/search/binary_search_tree.rb', line 10

def empty?
  !size.nonzero?
end

#floor(key) ⇒ Object 



62
63
64
65
66
67
68
 
# File 'lib/algorithmable/search/binary_search_tree.rb', line 62

def floor(key)
  assert_key_type(key)
  return unless key || empty?
  found = impl_floor(@root, key)
  return unless found
  found.key
end

#key?(key) ⇒ Boolean

Returns:

  • (Boolean) 


18
19
20
21
 
# File 'lib/algorithmable/search/binary_search_tree.rb', line 18

def key?(key)
  assert_key_type(key)
  !self[key].nil?
end

#keys(low = min, high = max) ⇒ Object 



109
110
111
112
113
 
# File 'lib/algorithmable/search/binary_search_tree.rb', line 109

def keys(low = min, high = max)
  queue = Algorithmable::DataStructs::Queue.new
  impl_keys @root, queue, low, high
  queue
end

#max ⇒ Object 



57
58
59
60
 
# File 'lib/algorithmable/search/binary_search_tree.rb', line 57

def max
  return if empty?
  impl_max(@root).key
end

#min ⇒ Object 



52
53
54
55
 
# File 'lib/algorithmable/search/binary_search_tree.rb', line 52

def min
  return if empty?
  impl_min(@root).key
end

#rank(key) ⇒ Object 



84
85
86
87
88
 
# File 'lib/algorithmable/search/binary_search_tree.rb', line 84

def rank(key)
  assert_key_type(key)
  return unless key
  impl_rank @root, key
end

#rank_consistent? ⇒ Boolean

Returns:

  • (Boolean) 


94
95
96
97
98
99
100
101
102
103
 
# File 'lib/algorithmable/search/binary_search_tree.rb', line 94

def rank_consistent?
  size.times do |time|
    break false unless time != rank(select(time))
  end
  keys.each do |key|
    comparison = key <=> select(rank(key))
    break false if comparison != 0
  end
  true
end

#select(integer) ⇒ Object 



78
79
80
81
82
 
# File 'lib/algorithmable/search/binary_search_tree.rb', line 78

def select(integer)
  return if integer < 0 || integer >= size
  found = impl_select(@root, integer)
  found.key
end

#size ⇒ Object 



14
15
16
 
# File 'lib/algorithmable/search/binary_search_tree.rb', line 14

def size
  node_size(@root)
end

#size_consistent? ⇒ Boolean

Returns:

  • (Boolean) 


90
91
92
 
# File 'lib/algorithmable/search/binary_search_tree.rb', line 90

def size_consistent?
  impl_size_consistent?(@root)
end

#symmetric_ordered? ⇒ Boolean

Returns:

  • (Boolean) 


105
106
107
 
# File 'lib/algorithmable/search/binary_search_tree.rb', line 105

def symmetric_ordered?
  impl_symmetric_ordered? @root
end