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_maxObject


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_minObject


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

#maxObject


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

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

#minObject


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

#sizeObject


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