Class: CompSci::CompleteBinaryTree

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

Overview

A CompleteBinaryTree can very efficiently use an array for storage using simple arithmetic to determine parent child relationships.

Direct Known Subclasses

Heap

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(store: []) ⇒ CompleteBinaryTree

Returns a new instance of CompleteBinaryTree.



127
128
129
130
 
# File 'lib/compsci/tree.rb', line 127

def initialize(store: [])
  @store = store
  # yield self if block_given?
end

Instance Attribute Details

#store ⇒ Object (readonly)

Returns the value of attribute store.



125
126
127
 
# File 'lib/compsci/tree.rb', line 125

def store
  @store
end

Class Method Details

.children_idx(idx) ⇒ Object 



121
122
123
 
# File 'lib/compsci/tree.rb', line 121

def self.children_idx(idx)
  [2*idx + 1, 2*idx + 2]
end

.parent_idx(idx) ⇒ Object

integer math says idx 2 and idx 1 both have parent at idx 0



117
118
119
 
# File 'lib/compsci/tree.rb', line 117

def self.parent_idx(idx)
  (idx-1) / 2
end

Instance Method Details

#last_idx ⇒ Object 



136
137
138
 
# File 'lib/compsci/tree.rb', line 136

def last_idx
  @store.size - 1 unless @store.empty?
end

#size ⇒ Object 



132
133
134
 
# File 'lib/compsci/tree.rb', line 132

def size
  @store.size
end