Class: CompSci::CompleteNaryTree

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.

Likewise, we should be able to use an array for N children

Direct Known Subclasses

CompleteBinaryTree

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(store: [], child_slots: 2) ⇒ CompleteNaryTree

Returns a new instance of CompleteNaryTree.



165
166
167
168
 
# File 'lib/compsci/tree.rb', line 165

def initialize(store: [], child_slots: 2)
  @store = store
  @child_slots = child_slots
end

Instance Attribute Details

#store ⇒ Object (readonly)

Returns the value of attribute store.



163
164
165
 
# File 'lib/compsci/tree.rb', line 163

def store
  @store
end

Class Method Details

.children_idx(idx, n) ⇒ Object 



159
160
161
 
# File 'lib/compsci/tree.rb', line 159

def self.children_idx(idx, n)
  Array.new(n) { |i| n*idx + i + 1 }
end

.parent_idx(idx, n) ⇒ Object 



155
156
157
 
# File 'lib/compsci/tree.rb', line 155

def self.parent_idx(idx, n)
  (idx-1) / n
end

Instance Method Details

#last_idx ⇒ Object 



182
183
184
 
# File 'lib/compsci/tree.rb', line 182

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

#pop ⇒ Object 



174
175
176
 
# File 'lib/compsci/tree.rb', line 174

def pop
  @store.pop
end

#push(node) ⇒ Object 



170
171
172
 
# File 'lib/compsci/tree.rb', line 170

def push node
  @store.push node
end

#size ⇒ Object 



178
179
180
 
# File 'lib/compsci/tree.rb', line 178

def size
  @store.size
end