-
Notifications
You must be signed in to change notification settings - Fork 0
/
tree_collection.f90
235 lines (200 loc) · 11.2 KB
/
tree_collection.f90
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
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
! functions and subroutines to use binary tree: insert, rotate, traversal !
module tree_collection
use node_def
use word_collection
use GLOBAL
implicit none
public :: create_node, insert_in_tree, rotate_left, rotate_right, &
rebalance_tree, record, traverse
contains
! This procedure creates a node from given data with a pointers to children set to null.
! Then it calls the procedure insert_in_tree.
subroutine create_node()
character(len= :), allocatable :: new_word
new_word = to_lower(read_one()) ! The next value to be inserted.
if(new_word == '') then ! The end of the file encountered.
Seen_EOF = .true.
return
end if
allocate(Current) ! Create a node.
Current%word = new_word
Current%color = Red ! New nodes are always Red.
nullify(Current%left)
nullify(Current%right)
call insert_in_tree(Current) ! Insert the new node in the tree.
end subroutine create_node
! This procedure receives pointer to an isolated new node, in which all pointers are null, and which
! contains a value, ready for insertion in the tree.
! The procedure causes the tree to be searched from the root, along a path determined by
! the new node's value, until the path terminates in a null pointer. The node is then
! inserted in that position, and is colored red. The pointer to it's parent is then
! initialized as W. The pointer V indicates the position of the current node in the tree as the
! search progresses along a branch.
subroutine insert_in_tree(new)
type (Node), pointer :: new
type (Node), pointer :: V, W
integer :: res
V => Root ! The initial position of the search.
nullify (W) ! A pointer to the parent of V.
! Find the place in the tree to graft the new node - travel from the root to a node
! containing a null pointer.
do
if (.not. associated (V) ) then
exit
end if
W => V
res = compare(new%word, V%word)
if(res < 0) then ! Take the left branch.
V => V%left
else if(res > 0) then ! Take the right branch.
V => V%Right
else ! If same word add count.
V%iword = V%iword + 1
return
end if
end do
!! We have found a node W whose left or right pointer field is null.
new%parent => W ! Make the new node point at its parent.
if ( .not. associated(W) ) then ! There's only one node in the tree.
Root => new
else if (new%word < W%word) then ! Make the parent point at the new node.
W%left => new ! The new node is in the left branch.
else
W%Right => new ! The new node is in the right branch.
end if
end subroutine insert_in_tree
! This procedure rebalances and re-colors the nodes of a tree following an insertion.
! INCOMING: Dummy_Current = a pointer to a (red) node that has been inserted in the tree.
subroutine rebalance_tree(dummy_current)
type (Node), pointer :: dummy_current
type (Node), pointer :: X, Y
logical :: red_uncle
logical :: iterating
X => dummy_current
do ! This loop is exexuted if...
iterating = .not. associated(X, Root) ! ..we are not at root and ...
if(iterating) then ! ..parent is also red and ...
iterating = X%parent%color .eqv. Red
end if
if(iterating) then ! ..there is a grandparent.
iterating = associated(X%parent%parent)
end if
if(.not. iterating) then
exit
end if
if(associated(X%parent, X%parent%parent%left) ) then
Y => X%parent%parent%right ! The parent is a left node of X's grandparent
red_uncle = associated(Y) ! and the uncle is right node of grandparent
if (red_uncle) then
red_uncle = Y%color .eqv. Red
end if
! CASE 1 !
if (red_uncle) then ! If uncle, parent and X are all red
X%parent%color = Black ! The parent must be black.
Y%color = Black ! The uncle must be black.
X%parent%parent%color = Red ! The grandparent must be red.
X => X%parent%parent ! Move 2 places up the tree, to the grandparent.
! CASE 2 !
else ! The uncle is black, or is non-existent.
if (associated (X, X%parent%right) ) then
X => X%parent ! Move up the tree.
call rotate_left(X)
end if
! CASE 3 !
X%parent%color = Black
X%parent%parent%color = Red
call rotate_right(X%parent%parent)
end if
! This segment is the mirror image of the code for the "then" part,
! with the words Right and left interchanged
else ! The parent is a right node of X's grandparent.
Y => X%parent%parent%left ! Get the address of the uncle.
red_uncle = associated(Y)
if (red_uncle) then
red_uncle = Y%color .eqv. Red
end if
! CASE 1 !
if (red_uncle) then ! If uncle, parent and X are all red
X%parent%color = Black ! The parent must be black.
Y%color = Black ! The uncle must be black.
X%parent%parent%color = Red ! The grandparent must be red.
X => X%parent%parent ! Move 2 places up the tree, to the grandparent.
! CASE 2 !
else ! The uncle is black, or is non-existent.
if (associated (X, X%parent%left) ) then
X => X%parent ! Move up the tree.
call rotate_right(X)
end if
! CASE 3 !
X%parent%color = Black
X%parent%parent%color = Red
call rotate_left(X%parent%parent)
end if
end if
end do
Root%color = Black ! Ensure that the root is black.
end subroutine rebalance_tree
! This procedure performs a left rotation of a branch of a Red-Black tree, with node <Pivot>
! as the pivot.
! INCOMING: Pivot = a pointer to the node about which a branch of the tree is to be rotated.
subroutine rotate_left(pivot)
type (Node), pointer :: pivot
type (Node), pointer :: Y, X
X => pivot ! Can't use Pivot directly. Must use a temporary.
Y => X%right ! Y is the right child of X.
X%right => Y%left ! Change the left subtree of Y into X's right
! subtree.
if(associated(Y%left) ) then
Y%left%parent => X ! The left sub-node of Y points back at X --
! that is, X is now the parent of Y's left subtree.
end if
Y%parent => X%parent ! X's parent now becomes the parent of Y.
if(.not. associated (X%parent) ) then ! We are at the root node.
Root => Y
else if(associated (X, X%parent%left) ) then ! X is on the left of its parent.
X%parent%left => Y ! The left pointer of X's parent points at Y.
else ! X is on the right subtree of its parent.
X%parent%right => Y ! The right pointer of X's parent points at Y.
end if
Y%left => X ! Make X a left child of node Y. (X's left sub-
! tree comes with X).
X%parent => Y ! X's parent is now Y.
end subroutine rotate_left
! This procedure performs a right rotation of a branch of a Red-Black tree, with node <Pivot>
! as the pivot. This procedure is the mirror image of ROTATE_left, with the words Left
! and Right interchanged.
! INCOMING: Pivot = a pointer to the node about which a branch of the tree is to be rotated.
subroutine rotate_right(pivot)
type (Node), pointer :: pivot
type (Node), pointer :: Y, X
X => pivot ! Can't use Pivot directly. Must use a temporary.
Y => X%left ! Y is the left child of X.
X%left => Y%right ! Change the right subtree of Y into X's left
! subtree.
if(associated(Y%right) ) then
Y%right%parent => X ! The right sub-node of Y points back at X --
end if ! that is, X is now the parent of Y's right subtree
Y%parent => X%parent ! X's parent now becomes the parent of Y.
if (.not. associated(X%parent) ) then ! We are at the root node.
Root => Y
else if(associated(X, X%parent%right)) then ! X is on the right of its parent.
X%parent%right => Y ! The right pointer of X's parent points at Y.
else ! X is on the left of its parent.
X%parent%left => Y ! The left pointer of X's parent points at Y.
end if
Y%right => X ! Put X on the left of Y.
X%parent => Y ! X's parent is now Y.
end subroutine rotate_right
! This recursive subroutine retrieves and prints the values from the tree in ascending order.
recursive subroutine traverse(Current)
type (Node), pointer :: Current
if(associated(Current%left) ) then ! Take the left subtree.
call traverse(Current%left)
end if
call record(Current) ! Retrieve value from tree and record it
wordcount = wordcount + 1
if(associated(Current%right) ) then ! Take the right subtree.
call traverse(Current%right)
end if
end subroutine traverse
end module tree_collection