-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathRedBlackTreeTest.py
191 lines (168 loc) · 5.72 KB
/
RedBlackTreeTest.py
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
from RedBlackTree import *
def simple_setup():
"""
Constructs a configuration foa red black tree to be used in unit tests
"""
def test_tree():
print("test tree initialization")
rb = RedBlackTree(0)
assert rb.getValue() == 0
left = RedBlackTree(1)
left.getValue() == 1
rb.addLeftTree(left)
assert left.getParent() == rb
assert rb.getValue() == 0
assert rb.leftTree == left
right = RedBlackTree(-1)
right.getValue() == -1
rb.addRightTree(right)
assert rb.rightTree == right
assert rb.getValue() == 0
assert right.getParent() == rb
right.getValue() == -1
left.getValue() == 1
rb = RedBlackTree(10)
rb.binaryInsert(7)
assert rb.getLeftTree().getValue() == 7
rb.binaryInsert(12)
assert rb.getRightTree().getValue() == 12
rb.binaryInsert(14)
assert rb.getRightTree().getRightTree().getValue() == 14
print("pass tree initialization")
def test_left_rotate():
print("Test left rotate")
rb = RedBlackTree(5)
left = RedBlackTree(3)
right = RedBlackTree(7)
rb.addLeftTree(left)
rb.addRightTree(right)
left_left = RedBlackTree(2)
left_right = RedBlackTree(4)
left.addLeftTree(left_left)
left.addRightTree(left_right)
rb.left_rotate()
assert rb.getParent() == left
assert rb.getRightTree() == right
assert rb.getLeftTree() == left_right
assert rb.getParent().getLeftTree() == left_left
assert rb.getParent().getParent() == None
assert rb.getRightTree().getLeftTree() == None
assert rb.getRightTree().getRightTree() == None
assert rb.getLeftTree().getRightTree() == None
assert rb.getLeftTree().getLeftTree() == None
assert rb.getParent().getLeftTree().getRightTree() == None
assert rb.getParent().getLeftTree().getLeftTree() == None
rb1 = RedBlackTree(5)
right = RedBlackTree(7)
rb1.addRightTree(right)
rb1.left_rotate()
assert rb1.getParent() == None
assert rb1.getRightTree() == right
assert rb1.getLeftTree() == None
parent = RedBlackTree(10)
parent.binaryInsert(24)
parent.binaryInsert(3)
parent.binaryInsert(29)
parent.binaryInsert(16)
parent.binaryInsert(12)
parent.binaryInsert(17)
other_center = parent.getLeftTree()
central = parent.getRightTree()
left = central.getLeftTree()
right = central.getRightTree()
left_right = left.getRightTree()
left_left = left.getLeftTree()
assert parent.getValue() == 10
assert other_center.getValue() == 3
assert central.getValue() == 24
assert left.getValue() == 16
assert right.getValue() == 29
assert left_right.getValue() == 17
assert left_left.getValue() == 12
central.left_rotate()
assert central.getRightTree() == right
assert central.getLeftTree() == left_right
assert central.getParent() == left
assert left.getLeftTree() == left_left
assert left.getParent() == parent
assert parent.getRightTree() == left
assert left.getRightTree() == central
assert right.getParent() == central
assert left_right.getParent() == central
assert left_left.getParent() == left
assert parent.getParent() == None
assert parent.getLeftTree() == other_center
assert other_center.getParent() == parent
print("pass left rotate")
def test_right_rotate():
print("Test right rotate")
rb = RedBlackTree(5)
left = RedBlackTree(3)
right = RedBlackTree(7)
rb.addLeftTree(left)
rb.addRightTree(right)
right_left = RedBlackTree(6)
right_right = RedBlackTree(10)
right.addLeftTree(right_left)
right.addRightTree(right_right)
rb.right_rotate()
assert rb.getParent() == right
assert rb.getRightTree() == right_left
assert rb.getLeftTree() == left
assert rb.getParent().getRightTree() == right_right
assert rb.getParent().getParent() == None
assert rb.getRightTree().getLeftTree() == None
assert rb.getRightTree().getRightTree() == None
assert rb.getLeftTree().getRightTree() == None
assert rb.getLeftTree().getLeftTree() == None
assert rb.getParent().getRightTree().getRightTree() == None
assert rb.getParent().getRightTree().getLeftTree() == None
rb1 = RedBlackTree(5)
left = RedBlackTree(2)
rb1.addLeftTree(left)
rb1.right_rotate()
assert rb1.getParent() == None
assert rb1.getRightTree() == None
assert rb1.getLeftTree() == left
parent = RedBlackTree(10)
parent.binaryInsert(24)
parent.binaryInsert(3)
parent.binaryInsert(29)
parent.binaryInsert(16)
parent.binaryInsert(26)
parent.binaryInsert(32)
other_center = parent.getLeftTree()
central = parent.getRightTree()
left = central.getLeftTree()
right = central.getRightTree()
right_right = right.getRightTree()
right_left = right.getLeftTree()
assert parent.getValue() == 10
assert other_center.getValue() == 3
assert central.getValue() == 24
assert left.getValue() == 16
assert right.getValue() == 29
assert right_right.getValue() == 32
assert right_left.getValue() == 26
central.right_rotate()
assert central.getRightTree() == right_left
assert central.getLeftTree() == left
assert central.getParent() == right
assert right.getRightTree() == right_right
assert right.getParent() == parent
assert parent.getRightTree() == right
assert right.getLeftTree() == central
assert left.getParent() == central
assert right_right.getParent() == right
assert right_left.getParent() == central
assert parent.getParent() == None
assert parent.getLeftTree() == other_center
assert other_center.getParent() == parent
print("pass right rotate")
def test_add():
print("testing add")
print("pass add")
test_tree()
test_left_rotate()
test_right_rotate()
test_add()