Skip to content

Commit 3df0acc

Browse files
justcoding121justcoding121
committed
add more tests
1 parent 084f4e3 commit 3df0acc

File tree

3 files changed

+116
-3
lines changed

3 files changed

+116
-3
lines changed

‎src/Advanced.Algorithms/DataStructures/Tree/AvlTree.cs

Lines changed: 5 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -34,13 +34,17 @@ public AVLTree(bool enableNodeLookUp = false)
3434
/// <param name="enableNodeLookUp">Enabling lookup will fasten deletion/insertion/exists operations
3535
/// at the cost of additional space.</param>
3636
public AVLTree(IEnumerable<T> sortedCollection, bool enableNodeLookUp = false)
37-
: this(enableNodeLookUp)
3837
{
3938
ValidateSortedCollection(sortedCollection);
4039
var nodes = sortedCollection.Select(x => new AVLTreeNode<T>(null, x)).ToArray();
4140
Root = (AVLTreeNode<T>)ToBST(nodes);
4241
recomputeHeight(Root);
4342
assignCount(Root);
43+
44+
if (enableNodeLookUp)
45+
{
46+
nodeLookUp = nodes.ToDictionary(x => x.Value, x => x as BSTNodeBase<T>);
47+
}
4448
}
4549

4650

‎src/Advanced.Algorithms/DataStructures/Tree/RedBlackTree.cs

Lines changed: 4 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -131,7 +131,9 @@ internal bool Exists(T value)
131131
{
132132
if (nodeLookUp != null)
133133
{
134-
return (nodeLookUp[value] as RedBlackTreeNode<T>, Root.Position(value));
134+
//since node look up is only used by Bentley-Ottmann algorithm internally
135+
//and it does'nt need the position we can return defualt(int).
136+
return (nodeLookUp[value] as RedBlackTreeNode<T>, default(int));
135137
}
136138

137139
var result = Root.Find(value);
@@ -831,6 +833,7 @@ public T NextHigher(T value)
831833
return next != null ? next.Value : default(T);
832834
}
833835

836+
///Special (internal only) method for Bentley-Ottmann sweep line algorithm.
834837
internal void Swap(T value1, T value2)
835838
{
836839
var node1 = find(value1).Item1;

‎tests/Advanced.Algorithms.Tests/DataStructures/Tree/AVLTree_Tests.cs

Lines changed: 107 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -98,6 +98,77 @@ public void AVLTree_Accuracy_Test()
9898
{
9999
var nodeCount = 1000;
100100

101+
var rnd = new Random();
102+
var sorted = Enumerable.Range(1, nodeCount).ToList();
103+
var randomNumbers = sorted
104+
.OrderBy(x => rnd.Next())
105+
.ToList();
106+
107+
var tree = new AVLTree<int>();
108+
109+
for (int i = 0; i < nodeCount; i++)
110+
{
111+
tree.Insert(randomNumbers[i]);
112+
113+
Assert.IsTrue(tree.HasItem(randomNumbers[i]));
114+
Assert.IsTrue(tree.Root.IsBinarySearchTree(int.MinValue, int.MaxValue));
115+
tree.Root.VerifyCount();
116+
117+
var actualHeight = tree.GetHeight();
118+
119+
//http://stackoverflow.com/questions/30769383/finding-the-minimum-and-maximum-height-in-a-avl-tree-given-a-number-of-nodes
120+
var maxHeight = 1.44 * Math.Log(nodeCount + 2, 2) - 0.328;
121+
122+
Assert.IsTrue(actualHeight < maxHeight);
123+
Assert.IsTrue(tree.Count == i + 1);
124+
}
125+
126+
for (int i = 0; i < sorted.Count; i++)
127+
{
128+
Assert.AreEqual(sorted[i], tree.ElementAt(i));
129+
Assert.AreEqual(i, tree.IndexOf(sorted[i]));
130+
}
131+
132+
randomNumbers = Enumerable.Range(1, nodeCount)
133+
.OrderBy(x => rnd.Next())
134+
.ToList();
135+
136+
//IEnumerable test using linq
137+
Assert.AreEqual(tree.Count, tree.Count());
138+
Assert.AreEqual(tree.Count, tree.AsEnumerableDesc().Count());
139+
140+
for (int i = 0; i < nodeCount; i++)
141+
{
142+
if (rnd.NextDouble() >= 0.5)
143+
{
144+
tree.Delete(randomNumbers[i]);
145+
}
146+
else
147+
{
148+
var index = tree.IndexOf(randomNumbers[i]);
149+
Assert.AreEqual(tree.ElementAt(index), randomNumbers[i]);
150+
tree.RemoveAt(index);
151+
}
152+
153+
Assert.IsTrue(tree.Root.IsBinarySearchTree(int.MinValue, int.MaxValue));
154+
tree.Root.VerifyCount();
155+
156+
var actualHeight = tree.GetHeight();
157+
158+
//http://stackoverflow.com/questions/30769383/finding-the-minimum-and-maximum-height-in-a-avl-tree-given-a-number-of-nodes
159+
var maxHeight = 1.44 * Math.Log(nodeCount + 2, 2) - 0.328;
160+
161+
Assert.IsTrue(actualHeight < maxHeight);
162+
}
163+
164+
Assert.IsTrue(tree.Count == 0);
165+
}
166+
167+
[TestMethod]
168+
public void AVLTree_Accuracy_Test_With_Node_LookUp()
169+
{
170+
var nodeCount = 1000;
171+
101172
var rnd = new Random();
102173
var sorted = Enumerable.Range(1, nodeCount).ToList();
103174
var randomNumbers = sorted
@@ -165,7 +236,7 @@ public void AVLTree_Accuracy_Test()
165236
}
166237

167238
[TestMethod]
168-
public void AVLTree_BulkInit_Test()
239+
public void AVLTree_BulkInit_Test_With_Node_LookUp()
169240
{
170241
var nodeCount = 1000;
171242

@@ -199,6 +270,41 @@ public void AVLTree_BulkInit_Test()
199270
Assert.IsTrue(tree.Count == 0);
200271
}
201272

273+
[TestMethod]
274+
public void AVLTree_BulkInit_Test()
275+
{
276+
var nodeCount = 1000;
277+
278+
var rnd = new Random();
279+
var randomNumbers = Enumerable.Range(1, nodeCount).ToList();
280+
281+
var tree = new AVLTree<int>(randomNumbers, true);
282+
283+
Assert.IsTrue(tree.Root.IsBinarySearchTree(int.MinValue, int.MaxValue));
284+
Assert.AreEqual(tree.Count, tree.Count());
285+
286+
tree.Root.VerifyCount();
287+
288+
for (int i = 0; i < nodeCount; i++)
289+
{
290+
tree.Delete(randomNumbers[i]);
291+
292+
tree.Root.VerifyCount();
293+
Assert.IsTrue(tree.Root.IsBinarySearchTree(int.MinValue, int.MaxValue));
294+
295+
var actualHeight = tree.GetHeight();
296+
297+
//http://stackoverflow.com/questions/30769383/finding-the-minimum-and-maximum-height-in-a-avl-tree-given-a-number-of-nodes
298+
var maxHeight = 1.44 * Math.Log(nodeCount + 2, 2) - 0.328;
299+
300+
Assert.IsTrue(actualHeight < maxHeight);
301+
302+
Assert.IsTrue(tree.Count == nodeCount - 1 - i);
303+
}
304+
305+
Assert.IsTrue(tree.Count == 0);
306+
}
307+
202308
[TestMethod]
203309
public void AVLTree_Stress_Test()
204310
{

0 commit comments

Comments
 (0)