Class: TreeHandler::Tree

Inherits:
Object
  • Object
show all
Includes:
Comparable
Defined in:
lib/tree_handler.rb

Instance Attribute Summary collapse

Instance Method Summary collapse

Methods included from Comparable

#compare

Constructor Details

#initialize(array) ⇒ Tree

Returns a new instance of Tree.



8
9
10
11
 
# File 'lib/tree_handler.rb', line 8

def initialize(array)
  @data = array.uniq
  @root = build_tree
end

Instance Attribute Details

#data ⇒ Object

Returns the value of attribute data.



5
6
7
 
# File 'lib/tree_handler.rb', line 5

def data
  @data
end

#root ⇒ Object

Returns the value of attribute root.



5
6
7
 
# File 'lib/tree_handler.rb', line 5

def root
  @root
end

Instance Method Details

#balanced?(root = @root) ⇒ Boolean

Returns:

  • (Boolean) 


136
137
138
139
140
 
# File 'lib/tree_handler.rb', line 136

def balanced?(root = @root)
  left_height = depth(root.left_child)
  right_height = depth(root.right_child)
  (-1..1).include?(left_height - right_height)
end

#build_tree(array = @data.dup) ⇒ Object 



13
14
15
16
17
18
19
20
 
# File 'lib/tree_handler.rb', line 13

def build_tree(array = @data.dup)
  root = Node.new(array.shift)
  array.each do |value|
    node = Node.new(value)
    compare(root, node)
  end
  root
end

#delete(value, parent_pointer = @root) ⇒ Object 



32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
 
# File 'lib/tree_handler.rb', line 32

def delete(value, parent_pointer = @root)
  @data.delete(value)
  node = find(value)
  return nil if node.nil?

  unless node == @root
    parent = find_parent(value)
    parent_pointer =
      value < parent.value ? parent.left_child : parent.right_child
  end

  if node.left_child.nil?
    return parent_pointer = node.right_child
  elsif node.right_child.nil?
    return parent_pointer = node.left_child
  else
    parent_pointer = node.left_child
    compare(parent_pointer, node.right_child)
  end
end

#depth(node) ⇒ Object 



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

def depth(node)
  node.nil? ? 0 : level_order([node]).size
end

#find(value, node = @root) ⇒ Object 



53
54
55
56
57
58
59
60
61
62
63
 
# File 'lib/tree_handler.rb', line 53

def find(value, node = @root)
  if value == node.value
    return node
  elsif value < node.value
    return nil if node.left_child.nil?
    find(value, node.left_child)
  elsif value > node.value
    return nil if node.right_child.nil?
    find(value, node.right_child)
  end
end

#find_parent(value) ⇒ Object 



65
66
67
 
# File 'lib/tree_handler.rb', line 65

def find_parent(value)
  value == @root.value ? nil : find_parent_rec(value)
end

#find_parent_rec(value, node = @root) ⇒ Object 



69
70
71
72
73
74
75
76
77
78
79
80
 
# File 'lib/tree_handler.rb', line 69

def find_parent_rec(value, node = @root)
  value_left_child = node.left_child.nil? ? nil : node.left_child.value
  value_right_child = node.right_child.nil? ? nil : node.right_child.value

  if value == value_left_child || value == value_right_child
    return node
  elsif value < node.value
    value_left_child.nil? ? nil : find_parent_rec(value, node.left_child)
  elsif value > node.value
    value_right_child.nil? ? nil : find_parent_rec(value, node.right_child)
  end
end

#insert(value) ⇒ Object 



22
23
24
25
26
27
28
29
30
 
# File 'lib/tree_handler.rb', line 22

def insert(value)
  unless @data.include? value
    @data.push(value)
    node = Node.new(value)
    compare(root, node)
  else
    raise "The same value can't be inserted twice"
  end
end

#level_order(queue = [@root], no_block = []) ⇒ Object 



82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
 
# File 'lib/tree_handler.rb', line 82

def level_order(queue = [@root], no_block = [])
  until queue.empty?
    if block_given?
      yield(queue.map(&:value))
    else
      no_block.push(queue.map(&:value))
    end
    (0...queue.count).each do
      next_node = queue.shift
      queue.push(next_node.left_child) unless next_node.left_child.nil?
      queue.push(next_node.right_child) unless next_node.right_child.nil?
    end
  end
  no_block
end

#level_order_rec(queue = [@root], no_block = [], &block) ⇒ Object 



98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
 
# File 'lib/tree_handler.rb', line 98

def level_order_rec(queue = [@root], no_block = [], &block)
  queue_child = []
  if block_given?
    block.call(queue.map(&:value))
  else
    no_block.push(queue.map(&:value))
  end

  queue.each do |node|
    queue_child.push(node.left_child) unless node.left_child.nil?
    queue_child.push(node.right_child) unless node.right_child.nil?
  end
  level_order_rec(queue_child, no_block, &block) unless queue_child.empty?
  no_block
end

#rebalance! ⇒ Object 



142
143
144
145
 
# File 'lib/tree_handler.rb', line 142

def rebalance!
  result = rebalance_ordering(@data.dup.sort)
  @root = build_tree(result)
end

#rebalance_ordering(tree, result = []) ⇒ Object 



147
148
149
150
151
152
153
154
 
# File 'lib/tree_handler.rb', line 147

def rebalance_ordering(tree, result = [])
  return if tree.size == 0
  middle = tree.size / 2
  result.push tree.slice!(middle)
  rebalance_ordering(tree[0...middle], result)
  rebalance_ordering(tree[(middle)..-1], result)
  result
end