1+ namespace Algorithms.Tests.DataStructures
2+
3+ open Microsoft.VisualStudio .TestTools .UnitTesting
4+ open Algorithms.DataStructures .AVLTree
5+
6+ [<TestClass>]
7+ type AVLTreeTests () =
8+
9+ let rec verifyBalance ( maybeNode : Option < AVLNode >) =
10+ match maybeNode with
11+ | None -> ()
12+ | Some node ->
13+ let bf = AVLNode.balanceFactor node
14+ Assert.IsTrue( bf >= - 1 && bf <= 1 , $" Balance factor {bf} is out of range" )
15+ verifyBalance node.LeftChild
16+ verifyBalance node.RightChild
17+
18+ let rec verifyHeights ( maybeNode : Option < AVLNode >) =
19+ match maybeNode with
20+ | None -> ()
21+ | Some node ->
22+ let leftHeight = AVLNode.height node.LeftChild
23+ let rightHeight = AVLNode.height node.RightChild
24+ Assert.AreEqual( node.Height, 1 + max leftHeight rightHeight)
25+
26+ verifyHeights node.LeftChild
27+ verifyHeights node.RightChild
28+
29+ let rec verifyBST ( maybeNode : Option < AVLNode >) : Option < (* Min *) int * (* Max *) int > =
30+ match maybeNode with
31+ | None -> None
32+ | Some node ->
33+ let maybeLeftMinMax = verifyBST node.LeftChild
34+ let maybeRightMinMax = verifyBST node.RightChild
35+ maybeLeftMinMax
36+ |> Option.iter ( fun ( _ , leftMax ) ->
37+ Assert.IsTrue( leftMax < node.Value, $" Left child {leftMax} is greater than parent {node.Value}" )
38+ )
39+ maybeRightMinMax
40+ |> Option.iter ( fun ( rightMin , _ ) ->
41+ Assert.IsTrue( rightMin > node.Value, $" Right child {rightMin} is less than parent {node.Value}" )
42+ )
43+ let minValue =
44+ maybeLeftMinMax
45+ |> Option.map fst
46+ |> Option.defaultValue node.Value
47+ let maxValue =
48+ maybeRightMinMax
49+ |> Option.map snd
50+ |> Option.defaultValue node.Value
51+ Some ( minValue, maxValue)
52+
53+ let verifyProperties ( tree : AVLTree ) =
54+ verifyBalance tree.Root
55+ verifyHeights tree.Root
56+ verifyBST tree.Root |> ignore
57+ tree
58+
59+ [<TestMethod>]
60+ member _. ``Empty tree has no root`` () =
61+ let tree =
62+ empty
63+ |> verifyProperties
64+
65+ Assert.IsTrue( tree.Root.IsNone)
66+
67+ [<TestMethod>]
68+ member _. ``Insert maintains AVL properties`` () =
69+ let tree =
70+ empty
71+ |> verifyProperties
72+ |> insert 5
73+ |> verifyProperties
74+ |> insert 3
75+ |> verifyProperties
76+ |> insert 7
77+ |> verifyProperties
78+ |> insert 1
79+ |> verifyProperties
80+ |> insert 9
81+ |> verifyProperties
82+ |> insert 1
83+ |> verifyProperties
84+ ()
85+
86+ [<TestMethod>]
87+ member _. ``Right - heavy case triggers rotation`` () =
88+ let tree =
89+ empty
90+ |> verifyProperties
91+ |> insert 1
92+ |> verifyProperties
93+ |> insert 2
94+ |> verifyProperties
95+ |> insert 3
96+ |> verifyProperties
97+
98+ Assert.IsTrue( tree.Root.IsSome)
99+ let root = tree.Root.Value
100+ Assert.AreEqual( 2 , root.Value)
101+ Assert.AreEqual( Some 1 , root.LeftChild |> Option.map ( fun n -> n.Value))
102+ Assert.AreEqual( Some 3 , root.RightChild |> Option.map ( fun n -> n.Value))
103+
104+ [<TestMethod>]
105+ member _. ``Left - heavy case triggers rotation`` () =
106+ let tree =
107+ empty
108+ |> verifyProperties
109+ |> insert 3
110+ |> verifyProperties
111+ |> insert 2
112+ |> verifyProperties
113+ |> insert 1
114+ |> verifyProperties
115+
116+ Assert.IsTrue( tree.Root.IsSome)
117+ let root = tree.Root.Value
118+ Assert.AreEqual( 2 , root.Value)
119+ Assert.AreEqual( Some 1 , root.LeftChild |> Option.map ( fun n -> n.Value))
120+ Assert.AreEqual( Some 3 , root.RightChild |> Option.map ( fun n -> n.Value))
121+
122+ [<TestMethod>]
123+ member _. ``Double rotation for right - left case`` () =
124+ let tree =
125+ empty
126+ |> verifyProperties
127+ |> insert 1
128+ |> verifyProperties
129+ |> insert 3
130+ |> verifyProperties
131+ |> insert 2
132+ |> verifyProperties
133+
134+ Assert.IsTrue( tree.Root.IsSome)
135+ let root = tree.Root.Value
136+ Assert.AreEqual( 2 , root.Value)
137+ Assert.AreEqual( Some 1 , root.LeftChild |> Option.map ( fun n -> n.Value))
138+ Assert.AreEqual( Some 3 , root.RightChild |> Option.map ( fun n -> n.Value))
139+
140+ [<TestMethod>]
141+ member _. ``Double rotation for left - right case`` () =
142+ let tree =
143+ empty
144+ |> verifyProperties
145+ |> insert 3
146+ |> verifyProperties
147+ |> insert 1
148+ |> verifyProperties
149+ |> insert 2
150+ |> verifyProperties
151+
152+ Assert.IsTrue( tree.Root.IsSome)
153+ let root = tree.Root.Value
154+ Assert.AreEqual( 2 , root.Value)
155+ Assert.AreEqual( Some 1 , root.LeftChild |> Option.map ( fun n -> n.Value))
156+ Assert.AreEqual( Some 3 , root.RightChild |> Option.map ( fun n -> n.Value))
157+
158+ [<TestMethod>]
159+ member _. ``Duplicate insert is idempotent`` () =
160+ let tree1 =
161+ empty
162+ |> verifyProperties
163+ |> insert 1
164+ |> verifyProperties
165+ |> insert 2
166+ |> verifyProperties
167+
168+ let tree2 =
169+ insert 2 tree1
170+ |> verifyProperties
171+
172+ Assert.AreEqual( tree1.Root |> Option.map ( fun n -> n.Value),
173+ tree2.Root |> Option.map ( fun n -> n.Value))
174+ [<TestMethod>]
175+ member _. ``Delete maintains AVL properties`` () =
176+ let tree =
177+ empty
178+ |> insert 5
179+ |> verifyProperties
180+ |> insert 3
181+ |> verifyProperties
182+ |> insert 7
183+ |> verifyProperties
184+ |> insert 1
185+ |> verifyProperties
186+ |> insert 9
187+ |> verifyProperties
188+ |> insert 4
189+ |> verifyProperties
190+ |> insert 6
191+ |> verifyProperties
192+ |> insert 8
193+ |> verifyProperties
194+ |> insert 2
195+ |> verifyProperties
196+ |> delete 5 // Delete root
197+ |> verifyProperties
198+ |> delete 1 // Delete leaf
199+ |> verifyProperties
200+ |> delete 7 // Delete node with one child
201+ |> verifyProperties
202+ |> delete 3 // Delete node with two children
203+ |> verifyProperties
204+
205+ Assert.IsTrue( tree.Root.IsSome)
206+
207+ [<TestMethod>]
208+ member _. ``Delete from empty tree returns empty tree`` () =
209+ let tree =
210+ empty
211+ |> delete 1
212+ |> verifyProperties
213+
214+ Assert.IsTrue( tree.Root.IsNone)
215+
216+ [<TestMethod>]
217+ member _. ``Delete non - existent value maintains tree structure`` () =
218+ let tree1 =
219+ empty
220+ |> insert 2
221+ |> verifyProperties
222+ |> insert 1
223+ |> verifyProperties
224+ |> insert 3
225+ |> verifyProperties
226+
227+ let tree2 =
228+ tree1
229+ |> delete 4
230+ |> verifyProperties
231+
232+ Assert.AreEqual(
233+ tree1.Root |> Option.map ( fun n -> n.Value),
234+ tree2.Root |> Option.map ( fun n -> n.Value)
235+ )
236+
237+ [<TestMethod>]
238+ member _. ``Complex deletion cases maintain balance`` () =
239+ let tree =
240+ empty
241+ |> insert 50 // Create a more complex tree
242+ |> verifyProperties
243+ |> insert 25
244+ |> verifyProperties
245+ |> insert 75
246+ |> verifyProperties
247+ |> insert 10
248+ |> verifyProperties
249+ |> insert 35
250+ |> verifyProperties
251+ |> insert 60
252+ |> verifyProperties
253+ |> insert 90
254+ |> verifyProperties
255+ |> insert 5
256+ |> verifyProperties
257+ |> insert 15
258+ |> verifyProperties
259+ |> insert 30
260+ |> verifyProperties
261+ |> insert 40
262+ |> verifyProperties
263+ |> insert 55
264+ |> verifyProperties
265+ |> insert 65
266+ |> verifyProperties
267+ |> insert 80
268+ |> verifyProperties
269+ |> insert 95
270+ |> verifyProperties
271+
272+ // Test various deletion patterns
273+ |> delete 50 // Delete root with two children
274+ |> verifyProperties
275+ |> delete 25 // Delete inner node with two children
276+ |> verifyProperties
277+ |> delete 5 // Delete leaf
278+ |> verifyProperties
279+ |> delete 95 // Delete leaf on opposite side
280+ |> verifyProperties
281+ |> delete 35 // Delete node with one child
282+ |> verifyProperties
283+ |> delete 75 // Delete node requiring rebalancing
284+ |> verifyProperties
285+
286+ Assert.IsTrue( tree.Root.IsSome)
287+
288+ [<TestMethod>]
289+ member _. ``Sequential deletion maintains balance`` () =
290+ let mutable tree = empty
291+
292+ // Build tree with sequential inserts
293+ for i in 1 .. 10 do
294+ tree <- insert i tree
295+ tree <- verifyProperties tree
296+
297+ // Delete in reverse order
298+ for i in seq { 10 ..(- 1 ).. 1 } do
299+ tree <- delete i tree
300+ tree <- verifyProperties tree
301+
302+ Assert.IsTrue( tree.Root.IsNone)
303+
304+ [<TestMethod>]
305+ member _. ``Random operations maintain AVL properties`` () =
306+ let rng = System.Random( 42 )
307+ let mutable tree = empty
308+
309+ // Random inserts
310+ for _ in 1 .. 20 do
311+ let value = rng.Next( 1 , 100 )
312+ tree <- insert value tree
313+ tree <- verifyProperties tree
314+
315+ // Random deletes
316+ for _ in 1 .. 10 do
317+ let value = rng.Next( 1 , 100 )
318+ tree <- delete value tree
319+ tree <- verifyProperties tree
0 commit comments