Class: CompSci::CompleteBinaryTree

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

Overview

Heap still expects CompleteBinaryTree

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Methods inherited from CompleteNaryTree

#last_idx, #pop, #push, #size

Constructor Details

#initialize(store: []) ⇒ CompleteBinaryTree

Returns a new instance of CompleteBinaryTree.



201
202
203
 
# File 'lib/compsci/tree.rb', line 201

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

Instance Attribute Details

#store ⇒ Object (readonly)

Returns the value of attribute store.



199
200
201
 
# File 'lib/compsci/tree.rb', line 199

def store
  @store
end

Class Method Details

.children_idx(idx) ⇒ Object 



195
196
197
 
# File 'lib/compsci/tree.rb', line 195

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



191
192
193
 
# File 'lib/compsci/tree.rb', line 191

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

Instance Method Details

#to_s(node: nil, width: 80) ⇒ Object

TODO: generalize for N != 2



206
207
208
209
210
211
212
213
214
215
 
# File 'lib/compsci/tree.rb', line 206

def to_s(node: nil, width: 80)
  str = ''
  @store.each_with_index { |n, i|
    level = Math.log(i+1, 2).floor
    block_width = width / (2**level)
    str += "\n" if 2**level == i+1 and i > 0
    str += n.to_s.ljust(block_width / 2, ' ').rjust(block_width, ' ')
  }
  str
end