Skip to content

Commit f2796e2

Browse files
wootangmikelwootangmikel
authored
Add Red-Black Tree (TheAlgorithms#270)
1 parent 81ec274 commit f2796e2

File tree

4 files changed

+1313
-0
lines changed

4 files changed

+1313
-0
lines changed

‎DataStructures.Tests/RedBlackTreeTests.cs

Lines changed: 379 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,379 @@
1+
using System;
2+
using System.Collections.Generic;
3+
using System.Linq;
4+
using DataStructures.RedBlackTree;
5+
using FluentAssertions;
6+
using NUnit.Framework;
7+
8+
namespace DataStructures.Tests
9+
{
10+
internal class RedBlackTreeTests
11+
{
12+
[Test]
13+
public void Constructor_UseCustomComparer_FormsCorrect_Tree()
14+
{
15+
var tree = new RedBlackTree<int>(Comparer<int>.Create((x, y) => y.CompareTo(x)));
16+
tree.AddRange(new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 });
17+
tree.GetMin().Should().Be(10);
18+
tree.GetMax().Should().Be(1);
19+
tree.GetKeysInOrder().SequenceEqual(new[] { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 }).Should().BeTrue();
20+
}
21+
22+
[Test]
23+
public void Add_Case3_FormsCorrectTree()
24+
{
25+
var tree = new RedBlackTree<int>();
26+
tree.Add(5);
27+
tree.Count.Should().Be(1);
28+
}
29+
30+
[Test]
31+
public void Add_Case24_FormsCorrectTree()
32+
{
33+
var tree = new RedBlackTree<int>();
34+
tree.AddRange(new[] { 5, 4, 6, 3 });
35+
tree.GetKeysPreOrder().SequenceEqual(new[] { 5, 4, 3, 6 }).Should().BeTrue();
36+
}
37+
38+
[Test]
39+
public void Add_Case1_FormsCorrectTree()
40+
{
41+
var tree = new RedBlackTree<int>();
42+
tree.AddRange(new[] { 5, 4, 6, 3, 7 });
43+
tree.GetKeysPreOrder().SequenceEqual(new[] { 5, 4, 3, 6, 7 }).Should().BeTrue();
44+
}
45+
46+
[Test]
47+
public void Add_Case6_FormsCorrectTree()
48+
{
49+
// Right rotation
50+
var tree = new RedBlackTree<int>();
51+
tree.AddRange(new[] { 5, 4, 6, 3, 2 });
52+
tree.GetKeysPreOrder().SequenceEqual(new[] { 5, 3, 2, 4, 6 }).Should().BeTrue();
53+
54+
// Left rotation
55+
tree = new RedBlackTree<int>();
56+
tree.AddRange(new[] { 5, 4, 6, 7, 8 });
57+
tree.GetKeysPreOrder().SequenceEqual(new[] { 5, 4, 7, 6, 8 }).Should().BeTrue();
58+
}
59+
60+
[Test]
61+
public void Add_Case5_FormsCorrectTree()
62+
{
63+
// Left-right rotation
64+
var tree = new RedBlackTree<int>();
65+
tree.AddRange(new[] { 5, 4, 6, 2, 3 });
66+
tree.GetKeysPreOrder().SequenceEqual(new[] { 5, 3, 2, 4, 6 }).Should().BeTrue();
67+
68+
// Right-left rotation
69+
tree = new RedBlackTree<int>();
70+
tree.AddRange(new[] { 5, 4, 6, 8, 7 });
71+
tree.GetKeysPreOrder().SequenceEqual(new[] { 5, 4, 7, 6, 8 }).Should().BeTrue();
72+
}
73+
74+
[Test]
75+
public void Add_MultipleKeys_FormsCorrectTree()
76+
{
77+
var tree = new RedBlackTree<int>();
78+
79+
foreach (var value in new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 })
80+
{
81+
tree.Add(value);
82+
tree.Count.Should().Be(value);
83+
}
84+
85+
tree.GetKeysInOrder().SequenceEqual(new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }).Should().BeTrue();
86+
tree.GetKeysPreOrder().SequenceEqual(new[] { 4, 2, 1, 3, 6, 5, 8, 7, 9, 10 }).Should().BeTrue();
87+
}
88+
89+
[Test]
90+
public void Add_KeyAlreadyInTree_ThrowsException()
91+
{
92+
var tree = new RedBlackTree<int>();
93+
tree.AddRange(new[] { 1, 2, 3, 4, 5 });
94+
Assert.Throws<ArgumentException>(() => tree.Add(1));
95+
}
96+
97+
[Test]
98+
public void AddRange_MultipleKeys_FormsCorrectTree()
99+
{
100+
var tree = new RedBlackTree<int>();
101+
tree.AddRange(new[] { 9, 0, 1, 6, 7, 5, 2, 8, 4, 3 });
102+
tree.Count.Should().Be(10);
103+
tree.GetKeysInOrder().SequenceEqual(new[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }).Should().BeTrue();
104+
tree.GetKeysPreOrder().SequenceEqual(new[] { 5, 1, 0, 3, 2, 4, 7, 6, 9, 8 }).Should().BeTrue();
105+
}
106+
107+
[Test]
108+
public void Remove_SimpleCases_TreeStillValid()
109+
{
110+
var tree = new RedBlackTree<int>();
111+
tree.AddRange(new[] { 13, 8, 17, 1, 11, 15, 25, 6, 22, 27 });
112+
tree.Remove(6);
113+
tree.Count.Should().Be(9);
114+
tree.Contains(6).Should().BeFalse();
115+
tree.GetKeysInOrder().SequenceEqual(new[] { 1, 8, 11, 13, 15, 17, 22, 25, 27 }).Should().BeTrue();
116+
tree.GetKeysPreOrder().SequenceEqual(new[] { 13, 8, 1, 11, 17, 15, 25, 22, 27 }).Should().BeTrue();
117+
118+
tree = new RedBlackTree<int>();
119+
tree.AddRange(new[] { 13, 8, 17, 1, 11, 15, 25, 6, 22, 27 });
120+
tree.Remove(1);
121+
tree.Count.Should().Be(9);
122+
tree.Contains(1).Should().BeFalse();
123+
tree.GetKeysInOrder().SequenceEqual(new[] { 6, 8, 11, 13, 15, 17, 22, 25, 27 }).Should().BeTrue();
124+
tree.GetKeysPreOrder().SequenceEqual(new[] { 13, 8, 6, 11, 17, 15, 25, 22, 27 }).Should().BeTrue();
125+
126+
tree = new RedBlackTree<int>();
127+
tree.AddRange(new[] { 13, 8, 17, 1, 11, 15, 25, 6, 22, 27 });
128+
tree.Remove(17);
129+
tree.Count.Should().Be(9);
130+
tree.Contains(17).Should().BeFalse();
131+
tree.GetKeysInOrder().SequenceEqual(new[] { 1, 6, 8, 11, 13, 15, 22, 25, 27 }).Should().BeTrue();
132+
tree.GetKeysPreOrder().SequenceEqual(new[] { 13, 8, 1, 6, 11, 22, 15, 25, 27 }).Should().BeTrue();
133+
134+
tree = new RedBlackTree<int>();
135+
tree.AddRange(new[] { 13, 8, 17, 1, 11, 15, 25, 6, 22, 27 });
136+
tree.Remove(25);
137+
tree.Count.Should().Be(9);
138+
tree.Contains(25).Should().BeFalse();
139+
tree.GetKeysInOrder().SequenceEqual(new[] { 1, 6, 8, 11, 13, 15, 17, 22, 27 }).Should().BeTrue();
140+
tree.GetKeysPreOrder().SequenceEqual(new[] { 13, 8, 1, 6, 11, 17, 15, 27, 22 }).Should().BeTrue();
141+
142+
tree = new RedBlackTree<int>();
143+
tree.AddRange(new[] { 7, 3, 18, 10, 22, 8, 11, 26 });
144+
tree.Remove(18);
145+
tree.Count.Should().Be(7);
146+
tree.Contains(18).Should().BeFalse();
147+
tree.GetKeysInOrder().SequenceEqual(new[] { 3, 7, 8, 10, 11, 22, 26 }).Should().BeTrue();
148+
tree.GetKeysPreOrder().SequenceEqual(new[] { 7, 3, 22, 10, 8, 11, 26 }).Should().BeTrue();
149+
150+
tree = new RedBlackTree<int>();
151+
tree.Add(1);
152+
tree.Add(2);
153+
tree.Remove(1);
154+
tree.Count.Should().Be(1);
155+
tree.GetKeysInOrder().SequenceEqual(new[] { 2 }).Should().BeTrue();
156+
tree.GetKeysPreOrder().SequenceEqual(new[] { 2 }).Should().BeTrue();
157+
}
158+
159+
[Test]
160+
public void Remove_Case1_TreeStillValid()
161+
{
162+
var tree = new RedBlackTree<int>();
163+
tree.AddRange(new[] { 5, 2, 8, 1 });
164+
tree.Remove(1);
165+
tree.Remove(2);
166+
tree.Contains(2).Should().BeFalse();
167+
tree.GetKeysInOrder().SequenceEqual(new[] { 5, 8 }).Should().BeTrue();
168+
tree.GetKeysPreOrder().SequenceEqual(new[] { 5, 8 }).Should().BeTrue();
169+
}
170+
171+
[Test]
172+
public void Remove_Case3_TreeStillValid()
173+
{
174+
// Move to case 6
175+
var tree = new RedBlackTree<int>();
176+
tree.AddRange(new[] { 7, 3, 18, 1, 10, 22, 8, 11, 26 });
177+
tree.Remove(1);
178+
tree.Remove(3);
179+
tree.Count.Should().Be(7);
180+
tree.Contains(3).Should().BeFalse();
181+
tree.GetKeysInOrder().SequenceEqual(new[] { 7, 8, 10, 11, 18, 22, 26 }).Should().BeTrue();
182+
tree.GetKeysPreOrder().SequenceEqual(new[] { 18, 10, 7, 8, 11, 22, 26 }).Should().BeTrue();
183+
184+
// Move to case 5
185+
tree = new RedBlackTree<int>();
186+
tree.AddRange(new[] { 8, 3, 2, 0, 9, 4, 7, 6, 1, 5 });
187+
tree.Remove(8);
188+
tree.Remove(6);
189+
tree.Remove(9);
190+
tree.Count.Should().Be(7);
191+
tree.GetKeysInOrder().SequenceEqual(new[] { 0, 1, 2, 3, 4, 5, 7 }).Should().BeTrue();
192+
tree.GetKeysPreOrder().SequenceEqual(new[] { 3, 1, 0, 2, 5, 4, 7 }).Should().BeTrue();
193+
194+
// Move to case 4
195+
tree = new RedBlackTree<int>();
196+
tree.AddRange(new[] { 7, 5, 8, 4, 6, 3, 2, 9, 0, 1 });
197+
tree.Remove(9);
198+
tree.Remove(6);
199+
tree.Remove(5);
200+
tree.Remove(8);
201+
tree.Count.Should().Be(6);
202+
tree.GetKeysInOrder().SequenceEqual(new[] { 0, 1, 2, 3, 4, 7 }).Should().BeTrue();
203+
tree.GetKeysPreOrder().SequenceEqual(new[] { 3, 1, 0, 2, 7, 4 }).Should().BeTrue();
204+
}
205+
206+
[Test]
207+
public void Remove_Case4_TreeStillValid()
208+
{
209+
var tree = new RedBlackTree<int>();
210+
tree.AddRange(new[] { 5, 2, 8, 1, 4, 7, 9, 0, 3 });
211+
tree.Remove(0);
212+
tree.Remove(3);
213+
tree.Remove(2);
214+
tree.Count.Should().Be(6);
215+
tree.Contains(2).Should().BeFalse();
216+
tree.GetKeysInOrder().SequenceEqual(new[] { 1, 4, 5, 7, 8, 9 }).Should().BeTrue();
217+
tree.GetKeysPreOrder().SequenceEqual(new[] { 5, 4, 1, 8, 7, 9 }).Should().BeTrue();
218+
}
219+
220+
[Test]
221+
public void Remove_Case5_TreeStillValid()
222+
{
223+
var tree = new RedBlackTree<int>();
224+
tree.AddRange(new[] { 13, 8, 17, 1, 11, 15, 25, 6, 22, 27 });
225+
tree.Remove(8);
226+
tree.Count.Should().Be(9);
227+
tree.Contains(8).Should().BeFalse();
228+
tree.GetKeysInOrder().SequenceEqual(new[] { 1, 6, 11, 13, 15, 17, 22, 25, 27 }).Should().BeTrue();
229+
tree.GetKeysPreOrder().SequenceEqual(new[] { 13, 6, 1, 11, 17, 15, 25, 22, 27 }).Should().BeTrue();
230+
231+
tree = new RedBlackTree<int>();
232+
tree.AddRange(new[] { 13, 8, 17, 1, 11, 15, 25, 0, 6, 22 });
233+
tree.Remove(13);
234+
tree.Count.Should().Be(9);
235+
tree.Contains(13).Should().BeFalse();
236+
tree.GetKeysInOrder().SequenceEqual(new[] { 0, 1, 6, 8, 11, 15, 17, 22, 25 }).Should().BeTrue();
237+
tree.GetKeysPreOrder().SequenceEqual(new[] { 15, 8, 1, 0, 6, 11, 22, 17, 25 }).Should().BeTrue();
238+
239+
tree = new RedBlackTree<int>();
240+
tree.AddRange(new[] { 7, 0, 1, 4, 8, 2, 3, 6, 5, 9 });
241+
tree.Remove(7);
242+
tree.Remove(0);
243+
tree.Remove(1);
244+
tree.Remove(4);
245+
tree.Remove(8);
246+
tree.GetKeysInOrder().SequenceEqual(new[] { 2, 3, 5, 6, 9 }).Should().BeTrue();
247+
tree.GetKeysPreOrder().SequenceEqual(new[] { 3, 2, 6, 5, 9 }).Should().BeTrue();
248+
}
249+
250+
[Test]
251+
public void Remove_Case6_TreeStillValid()
252+
{
253+
var tree = new RedBlackTree<int>();
254+
tree.AddRange(new[] { 13, 8, 17, 1, 11, 15, 25, 6, 22, 27 });
255+
tree.Remove(13);
256+
tree.Count.Should().Be(9);
257+
tree.Contains(13).Should().BeFalse();
258+
tree.GetKeysInOrder().SequenceEqual(new[] { 1, 6, 8, 11, 15, 17, 22, 25, 27 }).Should().BeTrue();
259+
tree.GetKeysPreOrder().SequenceEqual(new[] { 15, 8, 1, 6, 11, 25, 17, 22, 27 }).Should().BeTrue();
260+
261+
tree = new RedBlackTree<int>();
262+
tree.AddRange(new[] { 13, 8, 17, 1, 11, 15, 25, 0, 6, 22 });
263+
tree.Remove(8);
264+
tree.Count.Should().Be(9);
265+
tree.Contains(8).Should().BeFalse();
266+
tree.GetKeysInOrder().SequenceEqual(new[] { 0, 1, 6, 11, 13, 15, 17, 22, 25 }).Should().BeTrue();
267+
tree.GetKeysPreOrder().SequenceEqual(new[] { 13, 1, 0, 11, 6, 17, 15, 25, 22 }).Should().BeTrue();
268+
}
269+
270+
[Test]
271+
public void Remove_EmptyTree_ThrowsException()
272+
{
273+
var tree = new RedBlackTree<int>();
274+
Assert.Throws<InvalidOperationException>(() => tree.Remove(1));
275+
}
276+
277+
[Test]
278+
public void Remove_KeyNotInTree_ThrowsException()
279+
{
280+
var tree = new RedBlackTree<int>();
281+
tree.AddRange(new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 });
282+
Assert.Throws<KeyNotFoundException>(() => tree.Remove(24));
283+
}
284+
285+
[Test]
286+
public void Contains_CorrectReturn()
287+
{
288+
var tree = new RedBlackTree<int>();
289+
tree.AddRange(new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 });
290+
tree.Contains(3).Should().BeTrue();
291+
tree.Contains(7).Should().BeTrue();
292+
tree.Contains(24).Should().BeFalse();
293+
tree.Contains(-1).Should().BeFalse();
294+
}
295+
296+
[Test]
297+
public void Contains_EmptyTree_ReturnsFalse()
298+
{
299+
var tree = new RedBlackTree<int>();
300+
tree.Contains(5).Should().BeFalse();
301+
tree.Contains(-12).Should().BeFalse();
302+
}
303+
304+
[Test]
305+
public void GetMin_CorrectReturn()
306+
{
307+
var tree = new RedBlackTree<int>();
308+
tree.AddRange(new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 });
309+
tree.GetMin().Should().Be(1);
310+
}
311+
312+
[Test]
313+
public void GetMin_EmptyTree_ThrowsException()
314+
{
315+
var tree = new RedBlackTree<int>();
316+
Assert.Throws<InvalidOperationException>(() => tree.GetMin());
317+
}
318+
319+
[Test]
320+
public void GetMax_CorrectReturn()
321+
{
322+
var tree = new RedBlackTree<int>();
323+
tree.AddRange(new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 });
324+
tree.GetMax().Should().Be(10);
325+
}
326+
327+
[Test]
328+
public void GetMax_EmptyTree_ThrowsException()
329+
{
330+
var tree = new RedBlackTree<int>();
331+
Assert.Throws<InvalidOperationException>(() => tree.GetMax());
332+
}
333+
334+
[Test]
335+
public void GetKeysInOrder_CorrectReturn()
336+
{
337+
var tree = new RedBlackTree<int>();
338+
tree.AddRange(new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 });
339+
tree.GetKeysInOrder().SequenceEqual(new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }).Should().BeTrue();
340+
}
341+
342+
[Test]
343+
public void GetKeysInOrder_EmptyTree_CorrectReturn()
344+
{
345+
var tree = new RedBlackTree<int>();
346+
tree.GetKeysInOrder().SequenceEqual(Array.Empty<int>()).Should().BeTrue();
347+
}
348+
349+
[Test]
350+
public void GetKeysPreOrder_CorrectReturn()
351+
{
352+
var tree = new RedBlackTree<int>();
353+
tree.AddRange(new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 });
354+
tree.GetKeysPreOrder().SequenceEqual(new[] { 4, 2, 1, 3, 6, 5, 8, 7, 9, 10 }).Should().BeTrue();
355+
}
356+
357+
[Test]
358+
public void GetKeysPreOrder_EmptyTree_CorrectReturn()
359+
{
360+
var tree = new RedBlackTree<int>();
361+
tree.GetKeysPreOrder().SequenceEqual(Array.Empty<int>()).Should().BeTrue();
362+
}
363+
364+
[Test]
365+
public void GetKeysPostOrder_CorrectReturn()
366+
{
367+
var tree = new RedBlackTree<int>();
368+
tree.AddRange(new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 });
369+
tree.GetKeysPostOrder().SequenceEqual(new[] { 1, 3, 2, 5, 7, 10, 9, 8, 6, 4 }).Should().BeTrue();
370+
}
371+
372+
[Test]
373+
public void GetKeysPostOrder_EmptyTree_CorrectReturn()
374+
{
375+
var tree = new RedBlackTree<int>();
376+
tree.GetKeysPostOrder().SequenceEqual(Array.Empty<int>()).Should().BeTrue();
377+
}
378+
}
379+
}

0 commit comments

Comments
 (0)