Skip to content

Commit 088bf02

Browse files
justcoding121justcoding121
committed
Merge branch 'master' into beta
2 parents 891944c + 86ec237 commit 088bf02

File tree

2 files changed

+145
-15
lines changed

2 files changed

+145
-15
lines changed

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

Lines changed: 35 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -17,27 +17,40 @@ public class RedBlackTree<T> : BSTBase<T>, IEnumerable<T> where T : IComparable
1717

1818
public int Count => Root == null ? 0 : Root.Count;
1919

20+
/// <param name="enableNodeLookUp">Enabling lookup will fasten deletion/insertion/exists operations
21+
/// at the cost of additional space.</param>
22+
public RedBlackTree(bool enableNodeLookUp = false)
23+
{
24+
if (enableNodeLookUp)
25+
{
26+
nodeLookUp = new Dictionary<T, BSTNodeBase<T>>();
27+
}
28+
}
29+
2030
/// <summary>
2131
/// Initialize the BST with given sorted keys optionally.
2232
/// Time complexity: O(n).
2333
/// </summary>
2434
/// <param name="sortedCollection">The sorted initial collection.</param>
25-
public RedBlackTree(IEnumerable<T> sortedCollection = null)
35+
/// <param name="enableNodeLookUp">Enabling lookup will fasten deletion/insertion/exists operations
36+
/// at the cost of additional space.</param>
37+
public RedBlackTree(IEnumerable<T> sortedCollection, bool enableNodeLookUp = false)
2638
{
27-
if (sortedCollection != null)
39+
ValidateSortedCollection(sortedCollection);
40+
var nodes = sortedCollection.Select(x => new RedBlackTreeNode<T>(null, x)).ToArray();
41+
Root = (RedBlackTreeNode<T>)ToBST(nodes);
42+
assignColors(Root);
43+
assignCount(Root);
44+
45+
if (enableNodeLookUp)
2846
{
29-
ValidateSortedCollection(sortedCollection);
30-
var nodes = sortedCollection.Select(x => new RedBlackTreeNode<T>(null, x)).ToArray();
31-
Root = (RedBlackTreeNode<T>)ToBST(nodes);
32-
assignColors(Root);
33-
assignCount(Root);
47+
nodeLookUp = nodes.ToDictionary(x => x.Value, x => x as BSTNodeBase<T>);
3448
}
3549
}
3650

3751
///Special (internal only) constructor for Bentley-Ottmann sweep line algorithm for fast line swap.
3852
/// <param name="equalityComparer">Provide custom IEquality comparer for node lookup dictionary.</param>
3953
internal RedBlackTree(IEqualityComparer<T> equalityComparer)
40-
: this()
4154
{
4255
nodeLookUp = new Dictionary<T, BSTNodeBase<T>>(equalityComparer);
4356
}
@@ -131,9 +144,13 @@ internal bool Exists(T value)
131144
{
132145
if (nodeLookUp != null)
133146
{
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));
147+
if (nodeLookUp.ContainsKey(value))
148+
{
149+
var node = (nodeLookUp[value] as RedBlackTreeNode<T>);
150+
return (node, Root.Position(value));
151+
}
152+
153+
return (null, -1);
137154
}
138155

139156
var result = Root.Find(value);
@@ -391,11 +408,13 @@ public T RemoveAt(int index)
391408

392409
var node = Root.KthSmallest(index) as RedBlackTreeNode<T>;
393410

411+
var deletedValue = node.Value;
412+
394413
delete(node);
395414

396415
if (nodeLookUp != null)
397416
{
398-
nodeLookUp.Remove(node.Value);
417+
nodeLookUp.Remove(deletedValue);
399418
}
400419

401420
return node.Value;
@@ -439,13 +458,14 @@ private void delete(RedBlackTreeNode<T> node)
439458
{
440459
var maxLeftNode = findMax(node.Left);
441460

442-
node.Value = maxLeftNode.Value;
443-
444461
if (nodeLookUp != null)
445462
{
446-
nodeLookUp[node.Value] = node;
463+
nodeLookUp[node.Value] = maxLeftNode;
464+
nodeLookUp[maxLeftNode.Value] = node;
447465
}
448466

467+
node.Value = maxLeftNode.Value;
468+
449469
//delete left max node
450470
delete(maxLeftNode);
451471
return;

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

Lines changed: 110 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -125,6 +125,78 @@ public void RedBlackTree_Accuracy_Test()
125125
Assert.IsTrue(tree.Count == 0);
126126
}
127127

128+
[TestMethod]
129+
public void RedBlack_Accuracy_Test_With_Node_LookUp()
130+
{
131+
var nodeCount = 1000;
132+
133+
var rnd = new Random();
134+
var sorted = Enumerable.Range(1, nodeCount).ToList();
135+
var randomNumbers = sorted
136+
.OrderBy(x => rnd.Next())
137+
.ToList();
138+
139+
var tree = new RedBlackTree<int>(true);
140+
141+
for (int i = 0; i < nodeCount; i++)
142+
{
143+
var index = tree.Insert(randomNumbers[i]);
144+
Assert.AreEqual(index, tree.IndexOf(randomNumbers[i]));
145+
Assert.IsTrue(tree.HasItem(randomNumbers[i]));
146+
Assert.IsTrue(tree.Root.IsBinarySearchTree(int.MinValue, int.MaxValue));
147+
tree.Root.VerifyCount();
148+
var actualHeight = tree.Root.GetHeight();
149+
150+
//http://doctrina.org/maximum-height-of-red-black-tree.html
151+
var maxHeight = 2 * Math.Log(nodeCount + 1, 2);
152+
153+
Assert.IsTrue(actualHeight < maxHeight);
154+
Assert.IsTrue(tree.Count == i + 1);
155+
}
156+
157+
for (int i = 0; i < sorted.Count; i++)
158+
{
159+
Assert.AreEqual(sorted[i], tree.ElementAt(i));
160+
Assert.AreEqual(i, tree.IndexOf(sorted[i]));
161+
}
162+
163+
//shuffle again before deletion tests
164+
randomNumbers = Enumerable.Range(1, nodeCount)
165+
.OrderBy(x => rnd.Next())
166+
.ToList();
167+
168+
//IEnumerable test using linq
169+
Assert.AreEqual(tree.Count, tree.Count());
170+
Assert.AreEqual(tree.Count, tree.AsEnumerableDesc().Count());
171+
172+
for (int i = 0; i < nodeCount; i++)
173+
{
174+
if (rnd.NextDouble() >= 0.5)
175+
{
176+
var index = tree.IndexOf(randomNumbers[i]);
177+
Assert.AreEqual(index, tree.Delete(randomNumbers[i]));
178+
}
179+
else
180+
{
181+
var index = tree.IndexOf(randomNumbers[i]);
182+
Assert.AreEqual(tree.ElementAt(index), randomNumbers[i]);
183+
tree.RemoveAt(index);
184+
}
185+
186+
Assert.IsTrue(tree.Root.IsBinarySearchTree(int.MinValue, int.MaxValue));
187+
tree.Root.VerifyCount();
188+
var actualHeight = tree.Root.GetHeight();
189+
190+
//http://doctrina.org/maximum-height-of-red-black-tree.html
191+
var maxHeight = 2 * Math.Log(nodeCount + 1, 2);
192+
193+
Assert.IsTrue(actualHeight < maxHeight);
194+
Assert.IsTrue(tree.Count == nodeCount - 1 - i);
195+
}
196+
197+
Assert.IsTrue(tree.Count == 0);
198+
}
199+
128200
[TestMethod]
129201
public void RedBlackTree_BulkInit_Test()
130202
{
@@ -162,6 +234,44 @@ public void RedBlackTree_BulkInit_Test()
162234
Assert.IsTrue(tree.Count == 0);
163235
}
164236

237+
238+
[TestMethod]
239+
public void RedBlackTree_BulkInit_Test_With_Node_LookUp()
240+
{
241+
var nodeCount = 1000;
242+
243+
var rnd = new Random();
244+
var sortedNumbers = Enumerable.Range(1, nodeCount).ToList();
245+
246+
var tree = new RedBlackTree<int>(sortedNumbers, true);
247+
248+
Assert.IsTrue(tree.Root.IsBinarySearchTree(int.MinValue, int.MaxValue));
249+
250+
//IEnumerable test using linq
251+
Assert.AreEqual(tree.Count, tree.Count());
252+
Assert.AreEqual(tree.Count, tree.AsEnumerableDesc().Count());
253+
254+
tree.Root.VerifyCount();
255+
256+
for (int i = 0; i < nodeCount; i++)
257+
{
258+
tree.Delete(sortedNumbers[i]);
259+
260+
tree.Root.VerifyCount();
261+
Assert.IsTrue(tree.Root.IsBinarySearchTree(int.MinValue, int.MaxValue));
262+
263+
var actualHeight = tree.Root.GetHeight();
264+
265+
//http://doctrina.org/maximum-height-of-red-black-tree.html
266+
var maxHeight = 2 * Math.Log(nodeCount + 1, 2);
267+
268+
Assert.IsTrue(actualHeight < maxHeight);
269+
Assert.IsTrue(tree.Count == nodeCount - 1 - i);
270+
}
271+
272+
Assert.IsTrue(tree.Count == 0);
273+
}
274+
165275
[TestMethod]
166276
public void RedBlackTree_StressTest()
167277
{

0 commit comments

Comments
 (0)