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

#children ⇒ Object 



19
20
21
22
23
24
25
 
# File 'lib/binary_search_tree.rb', line 19

def children
  count = 0
  count += 1 if left.class == BinarySearchTree
  count += 1 if right.class == BinarySearchTree

  count
end

#include?(val) ⇒ Boolean

Returns:

  • (Boolean) 


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

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 



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

def insert(val)
  case val <=> value
  when -1 then insert_left(val)
  when 1 then insert_right(val)
  when 0 then false
  end

  self
end

#inspect ⇒ Object 



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

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

#left_rotate ⇒ Object 



27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
 
# File 'lib/binary_search_tree.rb', line 27

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

  # KW: still need to refactor this, unnecessary creation of new node
  # reassign parent
  new_left = BinarySearchTree.new(value)   # A'

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

  new_right = right.right         # C
  new_right.parent = self         # C <- A
  
  @value, @left, @right = right.value, new_left, new_right
end

#recalculate_depth_and_balance ⇒ Object 



92
93
94
95
96
 
# File 'lib/binary_search_tree.rb', line 92

def recalculate_depth_and_balance
  @depth = ([left.depth, right.depth].max + 1)
  @balance = right.depth - left.depth
  # p "RECALULATED DEPTH = #{depth}: BALANCE = #{balance}"
end

#right_rotate ⇒ Object 



51
52
53
54
55
56
57
58
59
60
61
62
63
64
 
# File 'lib/binary_search_tree.rb', line 51

def right_rotate
  new_right = BinarySearchTree.new(value)

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

  new_left = left.left
  new_left.parent = self

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

#to_a ⇒ Object 



88
89
90
 
# File 'lib/binary_search_tree.rb', line 88

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

#update_depth_and_balance ⇒ Object 



98
99
100
101
102
103
104
 
# File 'lib/binary_search_tree.rb', line 98

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))
  # p "RECALULATED #{self.inspect} DEPTH = #{depth}: BALANCE = #{balance}"
  parent.update_depth_and_balance
end