Class: DS::CompleteBinaryTree

Inherits:
Object
  • Object
show all
Defined in:
lib/ds/trees/complete_binary_tree.rb

Direct Known Subclasses

BinaryHeap

Instance Method Summary collapse

Constructor Details

#initialize(*args) ⇒ CompleteBinaryTree

Returns a new instance of CompleteBinaryTree.



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

def initialize(*args)
  if args.empty? 
    @data = []
  else
    @data = args.to_a
  end
end

Instance Method Details

#<<(value) ⇒ Object 



12
13
14
 
# File 'lib/ds/trees/complete_binary_tree.rb', line 12

def << (value)
  @data.push value
end

#children(value) ⇒ Object 



20
21
22
23
 
# File 'lib/ds/trees/complete_binary_tree.rb', line 20

def children(value)
  i = @data.index(value) 
  return [@data[2*i+1], @data[2*i+2]]
end

#left(value) ⇒ Object 



29
30
31
 
# File 'lib/ds/trees/complete_binary_tree.rb', line 29

def left value
  children(value).first
end

#left_index(i) ⇒ Object 



33
34
35
 
# File 'lib/ds/trees/complete_binary_tree.rb', line 33

def left_index(i)
  2*i+1  
end

#parent(value) ⇒ Object 



45
46
47
48
 
# File 'lib/ds/trees/complete_binary_tree.rb', line 45

def parent value
  i = @data.index(value)
  @data[parent_index(i)]
end

#parent_index(i) ⇒ Object 



41
42
43
 
# File 'lib/ds/trees/complete_binary_tree.rb', line 41

def parent_index(i)
  (i+1)/2 - 1
end

#right(value) ⇒ Object 



25
26
27
 
# File 'lib/ds/trees/complete_binary_tree.rb', line 25

def right value
  children(value)[1]
end

#right_index(i) ⇒ Object 



37
38
39
 
# File 'lib/ds/trees/complete_binary_tree.rb', line 37

def right_index(i)
  2*i+2
end

#root ⇒ Object 



16
17
18
 
# File 'lib/ds/trees/complete_binary_tree.rb', line 16

def root
  @data.first
end