Class: BinarySearchTree

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

Direct Known Subclasses

DataStruct::BinarySearchTree

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(value) ⇒ BinarySearchTree

Returns a new instance of BinarySearchTree.



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

def initialize(value)
  @value = value
  @parent = EmptyNode.new
  @left = EmptyNode.new
  @right = EmptyNode.new
  @depth = 0
  @balance = 0
end

Instance Attribute Details

#balance ⇒ Object

Returns the value of attribute balance.



2
3
4
 
# File 'lib/binary_search_tree.rb', line 2

def balance
  @balance
end

#depth ⇒ Object

Returns the value of attribute depth.



2
3
4
 
# File 'lib/binary_search_tree.rb', line 2

def depth
  @depth
end

#left ⇒ Object

Returns the value of attribute left.



2
3
4
 
# File 'lib/binary_search_tree.rb', line 2

def left
  @left
end

#parent ⇒ Object

Returns the value of attribute parent.



2
3
4
 
# File 'lib/binary_search_tree.rb', line 2

def parent
  @parent
end

#right ⇒ Object

Returns the value of attribute right.



2
3
4
 
# File 'lib/binary_search_tree.rb', line 2

def right
  @right
end

#value ⇒ Object

Returns the value of attribute value.



2
3
4
 
# File 'lib/binary_search_tree.rb', line 2

def value
  @value
end

Class Method Details

.from_array(array) ⇒ Object 



13
14
15
16
17
 
# File 'lib/binary_search_tree.rb', line 13

def self.from_array(array)
  BinarySearchTree.new(array.first).tap do |tree|
    array.each { |val| tree.insert(val) }
  end
end

Instance Method Details

#include?(val) ⇒ Boolean

Returns:

  • (Boolean) 


65
66
67
68
69
70
71
 
# File 'lib/binary_search_tree.rb', line 65

def include?(val)
  case val <=> value
  when -1 then left.include?(val)
  when 1 then right.include?(val)
  when 0 then true
  end
end

#insert(val) ⇒ Object 



51
52
53
54
55
56
57
58
59
 
# File 'lib/binary_search_tree.rb', line 51

def insert(val)
  case val <=> value
  when -1 then insert_at(val, left, -1)
  when 1 then insert_at(val, right, 1)
  when 0 then false
  end

  self
end

#inspect ⇒ Object 



61
62
63
 
# File 'lib/binary_search_tree.rb', line 61

def inspect
  " { #{value} : #{left.inspect} | #{right.inspect} } "
end

#left_rotate ⇒ Object 



19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
 
# File 'lib/binary_search_tree.rb', line 19

def left_rotate
  #
  #      A                B
  #     / \              / \
  #    D   B     <=>    A   C
  #       / \          / \
  #      E   C        D   E
  #

  new_left = BinarySearchTree.new(value)                        # A'

  new_left.left, left.parent = left, new_left                   # A' <-> D
  new_left.right, right.left.parent = right.left, new_left      # A' <-> E
  new_left.parent = self                                        # A' <- A

  new_right, new_right.parent = right.right, self               # C <-> A

  @value, @left, @right = right.value, new_left, new_right
end

#recalculate_depth_and_balance ⇒ Object 



77
78
79
80
 
# File 'lib/binary_search_tree.rb', line 77

def recalculate_depth_and_balance
  @depth = ([left.depth, right.depth].max + 1)
  @balance = right.depth - left.depth
end

#right_rotate ⇒ Object 



39
40
41
42
43
44
45
46
47
48
49
 
# File 'lib/binary_search_tree.rb', line 39

def right_rotate
  new_right = BinarySearchTree.new(value)

  new_right.right, right.parent = right, new_right
  new_right.left, left.right.parent = left.right, new_right
  new_right.parent = self

  new_left, new_left.parent = left.left, self

  @value, @left, @right = left.value, new_left, new_right
end

#to_a ⇒ Object 



73
74
75
 
# File 'lib/binary_search_tree.rb', line 73

def to_a
  left.to_a + [value] + right.to_a
end

#update_depth_and_balance ⇒ Object 



82
83
84
85
86
87
 
# File 'lib/binary_search_tree.rb', line 82

def update_depth_and_balance
  # recursively update depth and balance, rebalances if needed and crawls up the tree
  recalculate_depth_and_balance
  rebalance if ([-2, 2].include?(@balance))
  parent.update_depth_and_balance
end