Class: BinaryTree

Inherits:
Object
  • Object
show all
Defined in:
lib/binary-tree-access.rb

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ BinaryTree

Initialize the tree creating it’s root



5
6
7
 
# File 'lib/binary-tree-access.rb', line 5

def initialize
  @root = nil
end

Instance Attribute Details

#root ⇒ Object (readonly)

Returns the value of attribute root.



2
3
4
 
# File 'lib/binary-tree-access.rb', line 2

def root
  @root
end

Instance Method Details

#balance ⇒ Object

Balance the tree



116
117
118
119
120
121
122
 
# File 'lib/binary-tree-access.rb', line 116

def balance
  unless balanced?
    nodes = get_nodes([])
    @root = nil
    new_balance_nodes(nodes, @root)
  end
end

#balanced? ⇒ Boolean

Return true if tree is balanced, in other word, if the number of branchs is smaller than 2 raised to the tree’s depth

Returns:

  • (Boolean) 


136
137
138
 
# File 'lib/binary-tree-access.rb', line 136

def balanced?
  number_nodes.between?(2**(get_depth - 1), 2**get_depth)
end

#delete_node(x) ⇒ Object

Delete a selected node from the tree



61
62
63
64
65
66
67
 
# File 'lib/binary-tree-access.rb', line 61

def delete_node(x)
  nodes = get_nodes([])
  node = search_node(x)
  nodes.delete(node) if nodes.include? node
  @root = nil
  new_balance_nodes(nodes, @root)
end

#edit_node(x, *args) ⇒ Object

Edit an existing node



35
36
37
38
39
 
# File 'lib/binary-tree-access.rb', line 35

def edit_node(x, *args)
  node = search_node(x)
  return if node.nil?
  node.args = args
end

#get_depth(node = @root, depth = 1, maxdepth = 0) ⇒ Object

Return the max depth of the tree



141
142
143
144
145
146
147
 
# File 'lib/binary-tree-access.rb', line 141

def get_depth(node = @root, depth = 1, maxdepth = 0)
  maxdepth = get_depth(node.west, depth + 1, maxdepth) unless node.west.nil?
  maxdepth = get_depth(node.east, depth + 1, maxdepth) unless node.east.nil?
  maxdepth = depth if node.west.nil? && node.east.nil? && depth > maxdepth

  maxdepth
end

#get_nodes(nodes, node = @root) ⇒ Object

Return all the nodes in crescent order



108
109
110
111
112
113
 
# File 'lib/binary-tree-access.rb', line 108

def get_nodes(nodes, node = @root)
  nodes = get_nodes(nodes, node.west) unless node.west.nil?
  nodes << node
  nodes = get_nodes(nodes, node.east) unless node.east.nil?
  nodes
end

#load_file(file) ⇒ Object

Load a file and create a (sub)tree with its data



42
43
44
45
46
47
48
 
# File 'lib/binary-tree-access.rb', line 42

def load_file(file)
  data = File.open(file).readlines.map(&:chomp)
  data.each do |d|
    d = d.split(',')
    new_node(@root, *d[0], *d[1..-1]) unless d.nil?
  end
end

#new_balance_nodes(nodes, newroot = @root) ⇒ Object 



124
125
126
127
128
129
130
131
 
# File 'lib/binary-tree-access.rb', line 124

def new_balance_nodes(nodes, newroot = @root)
  # p nodes
  return if nodes.empty?
  new_node(newroot, nodes[nodes.length / 2].x, *nodes[nodes.length / 2].args)
  return if nodes.length == 1
  new_balance_nodes(nodes[0..(nodes.length / 2) - 1], @root)
  new_balance_nodes(nodes[(nodes.length / 2) + 1..-1], @root)
end

#new_node(node, x, *args) ⇒ Object

Create a new branch after locating it’s place



10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
 
# File 'lib/binary-tree-access.rb', line 10

def new_node(node, x, *args)
  return @root = Node.new(x, *args) if @root.nil?
  return Node.new(x, *args) if node.nil?
  return node if node.x == x

  if x < node.x
    if node.west.nil?
      node.west = new_node(node.west, x, *args)
    else
      new_node(node.west, x, *args)
    end
  elsif node.east.nil?
    node.east = new_node(node.east, x, *args)
  else
    new_node(node.east, x, *args)
  end
end

#new_node_balanced(node, x, *args) ⇒ Object

Create a new node and balance the tree



29
30
31
32
 
# File 'lib/binary-tree-access.rb', line 29

def new_node_balanced(node, x, *args)
  new_node(node, x, *args)
  balance unless balanced?
end

#number_nodes(node = @root) ⇒ Object

Return the number of branchs



150
151
152
 
# File 'lib/binary-tree-access.rb', line 150

def number_nodes(node = @root)
  node.nil? ? 0 : 1 + number_nodes(node.west) + number_nodes(node.east)
end

#print_tree(node = @root) ⇒ Object

Print all the branchs



100
101
102
103
104
105
 
# File 'lib/binary-tree-access.rb', line 100

def print_tree(node = @root)
  return if node.nil?
  print_tree(node.west) unless node.west.nil?
  puts "#{node.x} #{node.args}"
  print_tree(node.east) unless node.east.nil?
end

#save_file ⇒ Object

Save the current tree in a file



51
52
53
54
55
56
57
58
 
# File 'lib/binary-tree-access.rb', line 51

def save_file
  nodes = get_nodes([])
  file = File.open('search_tree', 'w')
  nodes.each do |node|
    file.puts("#{node.x} #{node.args}")
  end
  file.close
end

#search(x, node = @root) ⇒ Object

Locate a branch, if it exists



70
71
72
73
74
75
76
77
78
79
80
81
82
 
# File 'lib/binary-tree-access.rb', line 70

def search(x, node = @root)
  return false if node.nil?

  if x == node.x
    return true
  elsif x < node.x && !node.west.nil?
    search(x, node.west)
  elsif x > node.x && !node.east.nil?
    search(x, node.east)
  else
    return false
  end
end

#search_node(x, node = @root) ⇒ Object

Locate a branch, if it exists



85
86
87
88
89
90
91
92
93
94
95
96
97
 
# File 'lib/binary-tree-access.rb', line 85

def search_node(x, node = @root)
  return nil if node.nil?

  if x == node.x
    return node
  elsif x < node.x && !node.west.nil?
    search_node(x, node.west)
  elsif x > node.x && !node.east.nil?
    search_node(x, node.east)
  else
    return nil
  end
end