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

Creates new tree (stored in array).



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

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

Instance Method Details

#<<(value) ⇒ Object

Inserts new element.



14
15
16
 
# File 'lib/ds/trees/complete_binary_tree.rb', line 14

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

#children(i) ⇒ Object

Returns children of node i.



39
40
41
 
# File 'lib/ds/trees/complete_binary_tree.rb', line 39

def children(i)
  [@data[left_index(i)], @data[right_index(i)]]
end

#left(i) ⇒ Object

Returns left child of node i.



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

def left(i)
  @data[left_index(i)]
end

#left_index(i) ⇒ Object

Returns index of left child.



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

def left_index(i)
  2*i+1  
end

#parent(i) ⇒ Object

Returns parent of node i.



54
55
56
 
# File 'lib/ds/trees/complete_binary_tree.rb', line 54

def parent(i)
  @data[parent_index(i)]
end

#parent_index(i) ⇒ Object

Returns index of parent.



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

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

#right(i) ⇒ Object

Returns left child of node i.



49
50
51
 
# File 'lib/ds/trees/complete_binary_tree.rb', line 49

def right(i)
  @data[right_index(i)]
end

#right_index(i) ⇒ Object

Returns index of right child.



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

def right_index(i)
  2*i+2
end

#root ⇒ Object

Returns root element.



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

def root
  @data.first
end