binary_tree/binary_tree.rb at master · ViXP/binary_tree · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
moduleBinaryTree
classGenerator
# Binary tree generator class
# input (INTEGERS): the elements of tree
# output (HASH): the hash with human readable nodes
# FIXME method >> is not fully implemented
definitialize(*arr)
@tree=[]
@path=[]
handle_nodesarr
to_s
end

defsearch(val=nil)
@path=[]
returnnilunlessval && val.is_a?(Numeric)
search_parent@tree[0],val
end

defsearch_path(val=nil)
@path.joinifsearchval
end

defsearch_element(path=nil)
path=path.to_s.scan(/\d/)
returnnilifpath.empty?
el=@tree[0]
path.eachdo |r|
ifel && r == '1'
el=el.right
elsifel
el=el.left
else
returnnil
end
end
el
end

def <<(val=nil)
returnnilunlessval
@path=[]
search_parent(@tree[0],val,true)
inspect
end

def >>(val=nil)
returnnilunlessval
path=search_pathval
ifpath
el=search_element(path)
parent=search_element(path.slice(0,path.length - 1))
ifel.status == :leaf
ifparent.left == el
parent.left=nil
else
parent.right=nil
end
@tree.delete(el)
el
else
# MUST BE WRITTEN
end
else
nil
end
end

definspect
[*@tree.map(&:show)]
end

# Methods aliases
aliasfindsearch
alias [] search
aliasfind_pathsearch_path
aliasfind_elementsearch_element
aliaspush <<
aliasdelete >>
aliasshowinspect
aliasto_sinspect

private

defhandle_nodes(arr)
arr.each_with_indexdo |el,i|
nextunlessel.is_a?(Numeric)
@tree << Node.new(el)
(i + 1).upto(arr.length - 1)do |j|
position_nodearr[j]ifarr[j].is_a?(Numeric)
end
break
end
end

defposition_node(value)
search_parent(@tree[0],value,true)
end

defsearch_parent(parent,value,build=nil)
ifparent && parent.value <= value
returnparentif !build && parent.value == value# node found
@path << 1
ifparent.right.nil? && build
node=Node.new(value)
@tree << node
parent.right=node
parent.right
else
search_parentparent.right,value,build
end
elsifparent
@path << 0
ifparent.left.nil? && build
node=Node.new(value)
@tree << node
parent.left=node
parent.left
else
search_parentparent.left,value,build
end
else
@path=[]
parent
end
end
end

classNode
# Binary tree node class
# input (INTEGER): the value of element
# output (INTEGER): the value of element
attr_accessor:left,:right
attr_reader:value,:status

@quantity=0

defself.quantify
@quantity += 1
end

definitialize(val)
@value=val
@left=nil
@right=nil
@status=:leaf
end

defleft=(left)
@left=left
update_status
end

defright=(right)
@right=right
update_status
end

defshow
res={val: value,status: status}
res[:left]=left.valueifleft
res[:right]=right.valueifright
res
end

private

defupdate_status
@status=(left || right) ? :node : :leaf
end
end
end

# Creating the tree:
tree=BinaryTree::Generator.new(5,3,2,4,8,7,13,11,9,10,12,15)
ptree
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
moduleBinaryTree
classGenerator
# Binary tree generator class
# input (INTEGERS): the elements of tree
# output (HASH): the hash with human readable nodes
# FIXME method >> is not fully implemented
definitialize(*arr)
@tree=[]
@path=[]
handle_nodesarr
to_s
end

defsearch(val=nil)
@path=[]
returnnilunlessval && val.is_a?(Numeric)
search_parent@tree[0],val
end

defsearch_path(val=nil)
@path.joinifsearchval
end

defsearch_element(path=nil)
path=path.to_s.scan(/\d/)
returnnilifpath.empty?
el=@tree[0]
path.eachdo |r|
ifel && r == '1'
el=el.right
elsifel
el=el.left
else
returnnil
end
end
el
end

def <<(val=nil)
returnnilunlessval
@path=[]
search_parent(@tree[0],val,true)
inspect
end

def >>(val=nil)
returnnilunlessval
path=search_pathval
ifpath
el=search_element(path)
parent=search_element(path.slice(0,path.length - 1))
ifel.status == :leaf
ifparent.left == el
parent.left=nil
else
parent.right=nil
end
@tree.delete(el)
el
else
# MUST BE WRITTEN
end
else
nil
end
end

definspect
[*@tree.map(&:show)]
end

# Methods aliases
aliasfindsearch
alias [] search
aliasfind_pathsearch_path
aliasfind_elementsearch_element
aliaspush <<
aliasdelete >>
aliasshowinspect
aliasto_sinspect

private

defhandle_nodes(arr)
arr.each_with_indexdo |el,i|
nextunlessel.is_a?(Numeric)
@tree << Node.new(el)
(i + 1).upto(arr.length - 1)do |j|
position_nodearr[j]ifarr[j].is_a?(Numeric)
end
break
end
end

defposition_node(value)
search_parent(@tree[0],value,true)
end

defsearch_parent(parent,value,build=nil)
ifparent && parent.value <= value
returnparentif !build && parent.value == value# node found
@path << 1
ifparent.right.nil? && build
node=Node.new(value)
@tree << node
parent.right=node
parent.right
else
search_parentparent.right,value,build
end
elsifparent
@path << 0
ifparent.left.nil? && build
node=Node.new(value)
@tree << node
parent.left=node
parent.left
else
search_parentparent.left,value,build
end
else
@path=[]
parent
end
end
end

classNode
# Binary tree node class
# input (INTEGER): the value of element
# output (INTEGER): the value of element
attr_accessor:left,:right
attr_reader:value,:status

@quantity=0

defself.quantify
@quantity += 1
end

definitialize(val)
@value=val
@left=nil
@right=nil
@status=:leaf
end

defleft=(left)
@left=left
update_status
end

defright=(right)
@right=right
update_status
end

defshow
res={val: value,status: status}
res[:left]=left.valueifleft
res[:right]=right.valueifright
res
end

private

defupdate_status
@status=(left || right) ? :node : :leaf
end
end
end

# Creating the tree:
tree=BinaryTree::Generator.new(5,3,2,4,8,7,13,11,9,10,12,15)
ptree
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
moduleBinaryTree
classGenerator
# Binary tree generator class
# input (INTEGERS): the elements of tree
# output (HASH): the hash with human readable nodes
# FIXME method >> is not fully implemented
definitialize(*arr)
@tree=[]
@path=[]
handle_nodesarr
to_s
end

defsearch(val=nil)
@path=[]
returnnilunlessval && val.is_a?(Numeric)
search_parent@tree[0],val
end

defsearch_path(val=nil)
@path.joinifsearchval
end

defsearch_element(path=nil)
path=path.to_s.scan(/\d/)
returnnilifpath.empty?
el=@tree[0]
path.eachdo |r|
ifel && r == '1'
el=el.right
elsifel
el=el.left
else
returnnil
end
end
el
end

def <<(val=nil)
returnnilunlessval
@path=[]
search_parent(@tree[0],val,true)
inspect
end

def >>(val=nil)
returnnilunlessval
path=search_pathval
ifpath
el=search_element(path)
parent=search_element(path.slice(0,path.length - 1))
ifel.status == :leaf
ifparent.left == el
parent.left=nil
else
parent.right=nil
end
@tree.delete(el)
el
else
# MUST BE WRITTEN
end
else
nil
end
end

definspect
[*@tree.map(&:show)]
end

# Methods aliases
aliasfindsearch
alias [] search
aliasfind_pathsearch_path
aliasfind_elementsearch_element
aliaspush <<
aliasdelete >>
aliasshowinspect
aliasto_sinspect

private

defhandle_nodes(arr)
arr.each_with_indexdo |el,i|
nextunlessel.is_a?(Numeric)
@tree << Node.new(el)
(i + 1).upto(arr.length - 1)do |j|
position_nodearr[j]ifarr[j].is_a?(Numeric)
end
break
end
end

defposition_node(value)
search_parent(@tree[0],value,true)
end

defsearch_parent(parent,value,build=nil)
ifparent && parent.value <= value
returnparentif !build && parent.value == value# node found
@path << 1
ifparent.right.nil? && build
node=Node.new(value)
@tree << node
parent.right=node
parent.right
else
search_parentparent.right,value,build
end
elsifparent
@path << 0
ifparent.left.nil? && build
node=Node.new(value)
@tree << node
parent.left=node
parent.left
else
search_parentparent.left,value,build
end
else
@path=[]
parent
end
end
end

classNode
# Binary tree node class
# input (INTEGER): the value of element
# output (INTEGER): the value of element
attr_accessor:left,:right
attr_reader:value,:status

@quantity=0

defself.quantify
@quantity += 1
end

definitialize(val)
@value=val
@left=nil
@right=nil
@status=:leaf
end

defleft=(left)
@left=left
update_status
end

defright=(right)
@right=right
update_status
end

defshow
res={val: value,status: status}
res[:left]=left.valueifleft
res[:right]=right.valueifright
res
end

private

defupdate_status
@status=(left || right) ? :node : :leaf
end
end
end

# Creating the tree:
tree=BinaryTree::Generator.new(5,3,2,4,8,7,13,11,9,10,12,15)
ptree
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
moduleBinaryTree
classGenerator
# Binary tree generator class
# input (INTEGERS): the elements of tree
# output (HASH): the hash with human readable nodes
# FIXME method >> is not fully implemented
definitialize(*arr)
@tree=[]
@path=[]
handle_nodesarr
to_s
end

defsearch(val=nil)
@path=[]
returnnilunlessval && val.is_a?(Numeric)
search_parent@tree[0],val
end

defsearch_path(val=nil)
@path.joinifsearchval
end

defsearch_element(path=nil)
path=path.to_s.scan(/\d/)
returnnilifpath.empty?
el=@tree[0]
path.eachdo |r|
ifel && r == '1'
el=el.right
elsifel
el=el.left
else
returnnil
end
end
el
end

def <<(val=nil)
returnnilunlessval
@path=[]
search_parent(@tree[0],val,true)
inspect
end

def >>(val=nil)
returnnilunlessval
path=search_pathval
ifpath
el=search_element(path)
parent=search_element(path.slice(0,path.length - 1))
ifel.status == :leaf
ifparent.left == el
parent.left=nil
else
parent.right=nil
end
@tree.delete(el)
el
else
# MUST BE WRITTEN
end
else
nil
end
end

definspect
[*@tree.map(&:show)]
end

# Methods aliases
aliasfindsearch
alias [] search
aliasfind_pathsearch_path
aliasfind_elementsearch_element
aliaspush <<
aliasdelete >>
aliasshowinspect
aliasto_sinspect

private

defhandle_nodes(arr)
arr.each_with_indexdo |el,i|
nextunlessel.is_a?(Numeric)
@tree << Node.new(el)
(i + 1).upto(arr.length - 1)do |j|
position_nodearr[j]ifarr[j].is_a?(Numeric)
end
break
end
end

defposition_node(value)
search_parent(@tree[0],value,true)
end

defsearch_parent(parent,value,build=nil)
ifparent && parent.value <= value
returnparentif !build && parent.value == value# node found
@path << 1
ifparent.right.nil? && build
node=Node.new(value)
@tree << node
parent.right=node
parent.right
else
search_parentparent.right,value,build
end
elsifparent
@path << 0
ifparent.left.nil? && build
node=Node.new(value)
@tree << node
parent.left=node
parent.left
else
search_parentparent.left,value,build
end
else
@path=[]
parent
end
end
end

classNode
# Binary tree node class
# input (INTEGER): the value of element
# output (INTEGER): the value of element
attr_accessor:left,:right
attr_reader:value,:status

@quantity=0

defself.quantify
@quantity += 1
end

definitialize(val)
@value=val
@left=nil
@right=nil
@status=:leaf
end

defleft=(left)
@left=left
update_status
end

defright=(right)
@right=right
update_status
end

defshow
res={val: value,status: status}
res[:left]=left.valueifleft
res[:right]=right.valueifright
res
end

private

defupdate_status
@status=(left || right) ? :node : :leaf
end
end
end

# Creating the tree:
tree=BinaryTree::Generator.new(5,3,2,4,8,7,13,11,9,10,12,15)
ptree
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
moduleBinaryTree
classGenerator
# Binary tree generator class
# input (INTEGERS): the elements of tree
# output (HASH): the hash with human readable nodes
# FIXME method >> is not fully implemented
definitialize(*arr)
@tree=[]
@path=[]
handle_nodesarr
to_s
end

defsearch(val=nil)
@path=[]
returnnilunlessval && val.is_a?(Numeric)
search_parent@tree[0],val
end

defsearch_path(val=nil)
@path.joinifsearchval
end

defsearch_element(path=nil)
path=path.to_s.scan(/\d/)
returnnilifpath.empty?
el=@tree[0]
path.eachdo |r|
ifel && r == '1'
el=el.right
elsifel
el=el.left
else
returnnil
end
end
el
end

def <<(val=nil)
returnnilunlessval
@path=[]
search_parent(@tree[0],val,true)
inspect
end

def >>(val=nil)
returnnilunlessval
path=search_pathval
ifpath
el=search_element(path)
parent=search_element(path.slice(0,path.length - 1))
ifel.status == :leaf
ifparent.left == el
parent.left=nil
else
parent.right=nil
end
@tree.delete(el)
el
else
# MUST BE WRITTEN
end
else
nil
end
end

definspect
[*@tree.map(&:show)]
end

# Methods aliases
aliasfindsearch
alias [] search
aliasfind_pathsearch_path
aliasfind_elementsearch_element
aliaspush <<
aliasdelete >>
aliasshowinspect
aliasto_sinspect

private

defhandle_nodes(arr)
arr.each_with_indexdo |el,i|
nextunlessel.is_a?(Numeric)
@tree << Node.new(el)
(i + 1).upto(arr.length - 1)do |j|
position_nodearr[j]ifarr[j].is_a?(Numeric)
end
break
end
end

defposition_node(value)
search_parent(@tree[0],value,true)
end

defsearch_parent(parent,value,build=nil)
ifparent && parent.value <= value
returnparentif !build && parent.value == value# node found
@path << 1
ifparent.right.nil? && build
node=Node.new(value)
@tree << node
parent.right=node
parent.right
else
search_parentparent.right,value,build
end
elsifparent
@path << 0
ifparent.left.nil? && build
node=Node.new(value)
@tree << node
parent.left=node
parent.left
else
search_parentparent.left,value,build
end
else
@path=[]
parent
end
end
end

classNode
# Binary tree node class
# input (INTEGER): the value of element
# output (INTEGER): the value of element
attr_accessor:left,:right
attr_reader:value,:status

@quantity=0

defself.quantify
@quantity += 1
end

definitialize(val)
@value=val
@left=nil
@right=nil
@status=:leaf
end

defleft=(left)
@left=left
update_status
end

defright=(right)
@right=right
update_status
end

defshow
res={val: value,status: status}
res[:left]=left.valueifleft
res[:right]=right.valueifright
res
end

private

defupdate_status
@status=(left || right) ? :node : :leaf
end
end
end

# Creating the tree:
tree=BinaryTree::Generator.new(5,3,2,4,8,7,13,11,9,10,12,15)
ptree
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
moduleBinaryTree
classGenerator
# Binary tree generator class
# input (INTEGERS): the elements of tree
# output (HASH): the hash with human readable nodes
# FIXME method >> is not fully implemented
definitialize(*arr)
@tree=[]
@path=[]
handle_nodesarr
to_s
end

defsearch(val=nil)
@path=[]
returnnilunlessval && val.is_a?(Numeric)
search_parent@tree[0],val
end

defsearch_path(val=nil)
@path.joinifsearchval
end

defsearch_element(path=nil)
path=path.to_s.scan(/\d/)
returnnilifpath.empty?
el=@tree[0]
path.eachdo |r|
ifel && r == '1'
el=el.right
elsifel
el=el.left
else
returnnil
end
end
el
end

def <<(val=nil)
returnnilunlessval
@path=[]
search_parent(@tree[0],val,true)
inspect
end

def >>(val=nil)
returnnilunlessval
path=search_pathval
ifpath
el=search_element(path)
parent=search_element(path.slice(0,path.length - 1))
ifel.status == :leaf
ifparent.left == el
parent.left=nil
else
parent.right=nil
end
@tree.delete(el)
el
else
# MUST BE WRITTEN
end
else
nil
end
end

definspect
[*@tree.map(&:show)]
end

# Methods aliases
aliasfindsearch
alias [] search
aliasfind_pathsearch_path
aliasfind_elementsearch_element
aliaspush <<
aliasdelete >>
aliasshowinspect
aliasto_sinspect

private

defhandle_nodes(arr)
arr.each_with_indexdo |el,i|
nextunlessel.is_a?(Numeric)
@tree << Node.new(el)
(i + 1).upto(arr.length - 1)do |j|
position_nodearr[j]ifarr[j].is_a?(Numeric)
end
break
end
end

defposition_node(value)
search_parent(@tree[0],value,true)
end

defsearch_parent(parent,value,build=nil)
ifparent && parent.value <= value
returnparentif !build && parent.value == value# node found
@path << 1
ifparent.right.nil? && build
node=Node.new(value)
@tree << node
parent.right=node
parent.right
else
search_parentparent.right,value,build
end
elsifparent
@path << 0
ifparent.left.nil? && build
node=Node.new(value)
@tree << node
parent.left=node
parent.left
else
search_parentparent.left,value,build
end
else
@path=[]
parent
end
end
end

classNode
# Binary tree node class
# input (INTEGER): the value of element
# output (INTEGER): the value of element
attr_accessor:left,:right
attr_reader:value,:status

@quantity=0

defself.quantify
@quantity += 1
end

definitialize(val)
@value=val
@left=nil
@right=nil
@status=:leaf
end

defleft=(left)
@left=left
update_status
end

defright=(right)
@right=right
update_status
end

defshow
res={val: value,status: status}
res[:left]=left.valueifleft
res[:right]=right.valueifright
res
end

private

defupdate_status
@status=(left || right) ? :node : :leaf
end
end
end

# Creating the tree:
tree=BinaryTree::Generator.new(5,3,2,4,8,7,13,11,9,10,12,15)
ptree
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
moduleBinaryTree
classGenerator
# Binary tree generator class
# input (INTEGERS): the elements of tree
# output (HASH): the hash with human readable nodes
# FIXME method >> is not fully implemented
definitialize(*arr)
@tree=[]
@path=[]
handle_nodesarr
to_s
end

defsearch(val=nil)
@path=[]
returnnilunlessval && val.is_a?(Numeric)
search_parent@tree[0],val
end

defsearch_path(val=nil)
@path.joinifsearchval
end

defsearch_element(path=nil)
path=path.to_s.scan(/\d/)
returnnilifpath.empty?
el=@tree[0]
path.eachdo |r|
ifel && r == '1'
el=el.right
elsifel
el=el.left
else
returnnil
end
end
el
end

def <<(val=nil)
returnnilunlessval
@path=[]
search_parent(@tree[0],val,true)
inspect
end

def >>(val=nil)
returnnilunlessval
path=search_pathval
ifpath
el=search_element(path)
parent=search_element(path.slice(0,path.length - 1))
ifel.status == :leaf
ifparent.left == el
parent.left=nil
else
parent.right=nil
end
@tree.delete(el)
el
else
# MUST BE WRITTEN
end
else
nil
end
end

definspect
[*@tree.map(&:show)]
end

# Methods aliases
aliasfindsearch
alias [] search
aliasfind_pathsearch_path
aliasfind_elementsearch_element
aliaspush <<
aliasdelete >>
aliasshowinspect
aliasto_sinspect

private

defhandle_nodes(arr)
arr.each_with_indexdo |el,i|
nextunlessel.is_a?(Numeric)
@tree << Node.new(el)
(i + 1).upto(arr.length - 1)do |j|
position_nodearr[j]ifarr[j].is_a?(Numeric)
end
break
end
end

defposition_node(value)
search_parent(@tree[0],value,true)
end

defsearch_parent(parent,value,build=nil)
ifparent && parent.value <= value
returnparentif !build && parent.value == value# node found
@path << 1
ifparent.right.nil? && build
node=Node.new(value)
@tree << node
parent.right=node
parent.right
else
search_parentparent.right,value,build
end
elsifparent
@path << 0
ifparent.left.nil? && build
node=Node.new(value)
@tree << node
parent.left=node
parent.left
else
search_parentparent.left,value,build
end
else
@path=[]
parent
end
end
end

classNode
# Binary tree node class
# input (INTEGER): the value of element
# output (INTEGER): the value of element
attr_accessor:left,:right
attr_reader:value,:status

@quantity=0

defself.quantify
@quantity += 1
end

definitialize(val)
@value=val
@left=nil
@right=nil
@status=:leaf
end

defleft=(left)
@left=left
update_status
end

defright=(right)
@right=right
update_status
end

defshow
res={val: value,status: status}
res[:left]=left.valueifleft
res[:right]=right.valueifright
res
end

private

defupdate_status
@status=(left || right) ? :node : :leaf
end
end
end

# Creating the tree:
tree=BinaryTree::Generator.new(5,3,2,4,8,7,13,11,9,10,12,15)
ptree
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
moduleBinaryTree
classGenerator
# Binary tree generator class
# input (INTEGERS): the elements of tree
# output (HASH): the hash with human readable nodes
# FIXME method >> is not fully implemented
definitialize(*arr)
@tree=[]
@path=[]
handle_nodesarr
to_s
end

defsearch(val=nil)
@path=[]
returnnilunlessval && val.is_a?(Numeric)
search_parent@tree[0],val
end

defsearch_path(val=nil)
@path.joinifsearchval
end

defsearch_element(path=nil)
path=path.to_s.scan(/\d/)
returnnilifpath.empty?
el=@tree[0]
path.eachdo |r|
ifel && r == '1'
el=el.right
elsifel
el=el.left
else
returnnil
end
end
el
end

def <<(val=nil)
returnnilunlessval
@path=[]
search_parent(@tree[0],val,true)
inspect
end

def >>(val=nil)
returnnilunlessval
path=search_pathval
ifpath
el=search_element(path)
parent=search_element(path.slice(0,path.length - 1))
ifel.status == :leaf
ifparent.left == el
parent.left=nil
else
parent.right=nil
end
@tree.delete(el)
el
else
# MUST BE WRITTEN
end
else
nil
end
end

definspect
[*@tree.map(&:show)]
end

# Methods aliases
aliasfindsearch
alias [] search
aliasfind_pathsearch_path
aliasfind_elementsearch_element
aliaspush <<
aliasdelete >>
aliasshowinspect
aliasto_sinspect

private

defhandle_nodes(arr)
arr.each_with_indexdo |el,i|
nextunlessel.is_a?(Numeric)
@tree << Node.new(el)
(i + 1).upto(arr.length - 1)do |j|
position_nodearr[j]ifarr[j].is_a?(Numeric)
end
break
end
end

defposition_node(value)
search_parent(@tree[0],value,true)
end

defsearch_parent(parent,value,build=nil)
ifparent && parent.value <= value
returnparentif !build && parent.value == value# node found
@path << 1
ifparent.right.nil? && build
node=Node.new(value)
@tree << node
parent.right=node
parent.right
else
search_parentparent.right,value,build
end
elsifparent
@path << 0
ifparent.left.nil? && build
node=Node.new(value)
@tree << node
parent.left=node
parent.left
else
search_parentparent.left,value,build
end
else
@path=[]
parent
end
end
end

classNode
# Binary tree node class
# input (INTEGER): the value of element
# output (INTEGER): the value of element
attr_accessor:left,:right
attr_reader:value,:status

@quantity=0

defself.quantify
@quantity += 1
end

definitialize(val)
@value=val
@left=nil
@right=nil
@status=:leaf
end

defleft=(left)
@left=left
update_status
end

defright=(right)
@right=right
update_status
end

defshow
res={val: value,status: status}
res[:left]=left.valueifleft
res[:right]=right.valueifright
res
end

private

defupdate_status
@status=(left || right) ? :node : :leaf
end
end
end

# Creating the tree:
tree=BinaryTree::Generator.new(5,3,2,4,8,7,13,11,9,10,12,15)
ptree