Skip to content

Commit 1fc8dfc

Browse files
justcoding121justcoding121
committed
Fix r-b tree constructor
1 parent 71cdfcc commit 1fc8dfc

File tree

5 files changed

+61
-71
lines changed

5 files changed

+61
-71
lines changed

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

Lines changed: 0 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -411,7 +411,6 @@ public bool Contains(T value)
411411

412412
//find the node with the given identifier among descendants of parent and parent
413413
//uses pre-order traversal
414-
//O(log(n)) worst O(n) for unbalanced tree
415414
private AVLTreeNode<T> find(T value)
416415
{
417416
if (nodeLookUp != null)
@@ -424,7 +423,6 @@ private AVLTreeNode<T> find(T value)
424423

425424
//find the node with the given identifier among descendants of parent and parent
426425
//uses pre-order traversal
427-
//O(log(n)) worst O(n) for unbalanced tree
428426
private AVLTreeNode<T> find(AVLTreeNode<T> parent, T value)
429427
{
430428
if (parent == null)

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

Lines changed: 41 additions & 59 deletions
Original file line numberDiff line numberDiff line change
@@ -2,6 +2,7 @@
22
using System.Collections;
33
using System.Collections.Generic;
44
using System.Linq;
5+
using System.Reflection;
56

67
namespace Advanced.Algorithms.DataStructures
78
{
@@ -10,20 +11,26 @@ namespace Advanced.Algorithms.DataStructures
1011
/// </summary>
1112
public class RedBlackTree<T> : IEnumerable<T> where T : IComparable
1213
{
13-
//if enabled, lookup will fasten deletion/insertion/exists operations.
14-
private readonly Dictionary<T, BSTNodeBase<T>> nodeLookUp;
15-
1614
internal RedBlackTreeNode<T> Root { get; set; }
1715

16+
//if enabled, lookup will fasten deletion/insertion/exists operations.
17+
internal readonly Dictionary<T, BSTNodeBase<T>> NodeLookUp;
18+
1819
public int Count => Root == null ? 0 : Root.Count;
1920

2021
/// <param name="enableNodeLookUp">Enabling lookup will fasten deletion/insertion/exists operations
2122
/// at the cost of additional space.</param>
22-
public RedBlackTree(bool enableNodeLookUp = false)
23+
/// <param name="equalityComparer">Provide equality comparer for node lookup if enabled (required when T is not a value type).</param>
24+
public RedBlackTree(bool enableNodeLookUp = false, IEqualityComparer<T> equalityComparer = null)
2325
{
2426
if (enableNodeLookUp)
2527
{
26-
nodeLookUp = new Dictionary<T, BSTNodeBase<T>>();
28+
if (!typeof(T).GetTypeInfo().IsValueType && equalityComparer == null)
29+
{
30+
throw new ArgumentException("equalityComparer parameter is required when node lookup us enabled and T is not a value type.");
31+
}
32+
33+
NodeLookUp = new Dictionary<T, BSTNodeBase<T>>(equalityComparer);
2734
}
2835
}
2936

@@ -34,7 +41,9 @@ public RedBlackTree(bool enableNodeLookUp = false)
3441
/// <param name="sortedCollection">The sorted initial collection.</param>
3542
/// <param name="enableNodeLookUp">Enabling lookup will fasten deletion/insertion/exists operations
3643
/// at the cost of additional space.</param>
37-
public RedBlackTree(IEnumerable<T> sortedCollection, bool enableNodeLookUp = false)
44+
/// <param name="equalityComparer">Provide equality comparer for node lookup if enabled (required when T is not a value type).</param>
45+
public RedBlackTree(IEnumerable<T> sortedCollection, bool enableNodeLookUp = false,
46+
IEqualityComparer<T> equalityComparer = null)
3847
{
3948
BSTHelpers.ValidateSortedCollection(sortedCollection);
4049
var nodes = sortedCollection.Select(x => new RedBlackTreeNode<T>(null, x)).ToArray();
@@ -44,15 +53,13 @@ public RedBlackTree(IEnumerable<T> sortedCollection, bool enableNodeLookUp = fal
4453

4554
if (enableNodeLookUp)
4655
{
47-
nodeLookUp = nodes.ToDictionary(x => x.Value, x => x as BSTNodeBase<T>);
48-
}
49-
}
56+
if (!typeof(T).GetTypeInfo().IsValueType && equalityComparer == null)
57+
{
58+
throw new ArgumentException("equalityComparer parameter is required when node lookup us enabled and T is not a value type.");
59+
}
5060

51-
///Special (internal only) constructor for Bentley-Ottmann sweep line algorithm for fast line swap.
52-
/// <param name="equalityComparer">Provide custom IEquality comparer for node lookup dictionary.</param>
53-
internal RedBlackTree(IEqualityComparer<T> equalityComparer)
54-
{
55-
nodeLookUp = new Dictionary<T, BSTNodeBase<T>>(equalityComparer);
61+
NodeLookUp = nodes.ToDictionary(x => x.Value, x => x as BSTNodeBase<T>);
62+
}
5663
}
5764

5865
/// <summary>
@@ -65,12 +72,12 @@ public bool HasItem(T value)
6572
return false;
6673
}
6774

68-
if (nodeLookUp != null)
75+
if (NodeLookUp != null)
6976
{
70-
return nodeLookUp.ContainsKey(value);
77+
return NodeLookUp.ContainsKey(value);
7178
}
7279

73-
return find(value).Item1 != null;
80+
return Find(value).Item1 != null;
7481
}
7582

7683
/// <summary>
@@ -125,28 +132,25 @@ public T ElementAt(int index)
125132
return Root.KthSmallest(index).Value;
126133
}
127134

128-
//O(log(n)) worst O(n) for unbalanced tree
129135
internal RedBlackTreeNode<T> FindNode(T value)
130136
{
131-
return Root == null ? null : find(value).Item1;
137+
return Root == null ? null : Find(value).Item1;
132138
}
133139

134-
//O(log(n)) worst O(n) for unbalanced tree
135140
internal bool Exists(T value)
136141
{
137142
return FindNode(value) != null;
138143
}
139144

140145
//find the node with the given identifier among descendants of parent and parent
141146
//uses pre-order traversal
142-
//O(log(n)) worst O(n) for unbalanced tree
143-
private (RedBlackTreeNode<T>, int) find(T value)
147+
internal (RedBlackTreeNode<T>, int) Find(T value)
144148
{
145-
if (nodeLookUp != null)
149+
if (NodeLookUp != null)
146150
{
147-
if (nodeLookUp.ContainsKey(value))
151+
if (NodeLookUp.ContainsKey(value))
148152
{
149-
var node = (nodeLookUp[value] as RedBlackTreeNode<T>);
153+
var node = (NodeLookUp[value] as RedBlackTreeNode<T>);
150154
return (node, Root.Position(value));
151155
}
152156

@@ -176,19 +180,19 @@ public int Insert(T value)
176180
if (Root == null)
177181
{
178182
Root = new RedBlackTreeNode<T>(null, value) { NodeColor = RedBlackTreeNodeColor.Black };
179-
if (nodeLookUp != null)
183+
if (NodeLookUp != null)
180184
{
181-
nodeLookUp[value] = Root;
185+
NodeLookUp[value] = Root;
182186
}
183187

184188
return (Root, 0);
185189
}
186190

187191
var newNode = insert(Root, value);
188192

189-
if (nodeLookUp != null)
193+
if (NodeLookUp != null)
190194
{
191-
nodeLookUp[value] = newNode.Item1;
195+
NodeLookUp[value] = newNode.Item1;
192196
}
193197

194198
return newNode;
@@ -376,7 +380,7 @@ public int Delete(T value)
376380
return -1;
377381
}
378382

379-
var node = find(value);
383+
var node = Find(value);
380384

381385
if (node.Item1 == null)
382386
{
@@ -387,9 +391,9 @@ public int Delete(T value)
387391

388392
delete(node.Item1);
389393

390-
if (nodeLookUp != null)
394+
if (NodeLookUp != null)
391395
{
392-
nodeLookUp.Remove(value);
396+
NodeLookUp.Remove(value);
393397
}
394398

395399
return position;
@@ -412,9 +416,9 @@ public T RemoveAt(int index)
412416

413417
delete(node);
414418

415-
if (nodeLookUp != null)
419+
if (NodeLookUp != null)
416420
{
417-
nodeLookUp.Remove(deletedValue);
421+
NodeLookUp.Remove(deletedValue);
418422
}
419423

420424
return node.Value;
@@ -458,10 +462,10 @@ private void delete(RedBlackTreeNode<T> node)
458462
{
459463
var maxLeftNode = findMax(node.Left);
460464

461-
if (nodeLookUp != null)
465+
if (NodeLookUp != null)
462466
{
463-
nodeLookUp[node.Value] = maxLeftNode;
464-
nodeLookUp[maxLeftNode.Value] = node;
467+
NodeLookUp[node.Value] = maxLeftNode;
468+
NodeLookUp[maxLeftNode.Value] = node;
465469
}
466470

467471
node.Value = maxLeftNode.Value;
@@ -853,28 +857,6 @@ public T NextHigher(T value)
853857
return next != null ? next.Value : default(T);
854858
}
855859

856-
///Special (internal only) method for Bentley-Ottmann sweep line algorithm.
857-
internal void Swap(T value1, T value2)
858-
{
859-
var node1 = find(value1).Item1;
860-
var node2 = find(value2).Item1;
861-
862-
if (node1 == null || node2 == null)
863-
{
864-
throw new Exception("Value1, Value2 or both was not found in this BST.");
865-
}
866-
867-
var tmp = node1.Value;
868-
node1.Value = node2.Value;
869-
node2.Value = tmp;
870-
871-
if (nodeLookUp != null)
872-
{
873-
nodeLookUp[node1.Value] = node1;
874-
nodeLookUp[node2.Value] = node2;
875-
}
876-
}
877-
878860
/// <summary>
879861
/// Descending enumerable.
880862
/// </summary>

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

Lines changed: 0 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -48,7 +48,6 @@ internal int GetHeight()
4848
return GetHeight(Root);
4949
}
5050

51-
//O(log(n)) worst O(n) for unbalanced tree
5251
private int GetHeight(SplayTreeNode<T> node)
5352
{
5453
if (node == null)
@@ -164,7 +163,6 @@ public T RemoveAt(int index)
164163
return nodeToDelete.Value;
165164
}
166165

167-
//O(log(n)) worst O(n) for unbalanced tree
168166
private void delete(SplayTreeNode<T> node, T value)
169167
{
170168
while (true)
@@ -328,7 +326,6 @@ private SplayTreeNode<T> FindMin(SplayTreeNode<T> node)
328326

329327
//find the node with the given identifier among descendants of parent and parent
330328
//uses pre-order traversal
331-
//O(log(n)) worst O(n) for unbalanced tree
332329
private SplayTreeNode<T> find(SplayTreeNode<T> parent, T value)
333330
{
334331
while (true)
@@ -491,7 +488,6 @@ private SplayTreeNode<T> leftRotate(SplayTreeNode<T> currentRoot)
491488

492489
//find the node with the given identifier among descendants of parent and parent
493490
//uses pre-order traversal
494-
//O(log(n)) worst O(n) for unbalanced tree
495491
private BSTNodeBase<T> find(T value)
496492
{
497493
return Root.Find<T>(value).Item1 as BSTNodeBase<T>;

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

Lines changed: 0 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -50,7 +50,6 @@ internal int GetHeight()
5050
return getHeight(Root);
5151
}
5252

53-
//O(log(n)) worst O(n) for unbalanced tree
5453
private int getHeight(TreapTreeNode<T> node)
5554
{
5655
if (node == null)
@@ -167,7 +166,6 @@ public T RemoveAt(int index)
167166
return nodeToDelete.Value;
168167
}
169168

170-
//O(log(n)) worst O(n) for unbalanced tree
171169
private void delete(TreapTreeNode<T> node, T value)
172170
{
173171
while (true)
@@ -341,7 +339,6 @@ private TreapTreeNode<T> findMin(TreapTreeNode<T> node)
341339

342340
//find the node with the given identifier among descendants of parent and parent
343341
//uses pre-order traversal
344-
//O(log(n)) worst O(n) for unbalanced tree
345342
private TreapTreeNode<T> find(TreapTreeNode<T> parent, T value)
346343
{
347344
while (true)
@@ -486,7 +483,6 @@ private TreapTreeNode<T> leftRotate(TreapTreeNode<T> currentRoot)
486483

487484
//find the node with the given identifier among descendants of parent and parent
488485
//uses pre-order traversal
489-
//O(log(n)) worst O(n) for unbalanced tree
490486
private BSTNodeBase<T> find(T value)
491487
{
492488
return Root.Find<T>(value).Item1 as BSTNodeBase<T>;

‎src/Advanced.Algorithms/Geometry/BentleyOttmann.cs

Lines changed: 20 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -40,7 +40,7 @@ private void initialize(IEnumerable<Line> lineSegments)
4040
{
4141
SweepLine = new Line(new Point(0, 0), new Point(0, int.MaxValue), Tolerance);
4242

43-
currentlyTrackedLines = new RedBlackTree<Event>(pointComparer);
43+
currentlyTrackedLines = new RedBlackTree<Event>(true, pointComparer);
4444
intersectionEvents = new Dictionary<Point, HashSet<Tuple<Event, Event>>>(pointComparer);
4545

4646
verticalHorizontalLines = new HashSet<Event>();
@@ -151,7 +151,7 @@ public Dictionary<Point, List<Line>> FindIntersections(IEnumerable<Line> lineSeg
151151

152152
foreach (var item in intersectionLines)
153153
{
154-
currentlyTrackedLines.Swap(item.Item1, item.Item2);
154+
swapBstNodes(currentlyTrackedLines, item.Item1, item.Item2);
155155

156156
var upperLine = item.Item1;
157157
var upperUpper = currentlyTrackedLines.NextHigher(upperLine);
@@ -183,6 +183,24 @@ private void sweepTo(Event currentEvent)
183183
SweepLine = new Line(new Point(currentEvent.X, 0), new Point(currentEvent.X, int.MaxValue), Tolerance);
184184
}
185185

186+
internal void swapBstNodes(RedBlackTree<Event> currentlyTrackedLines, Event value1, Event value2)
187+
{
188+
var node1 = currentlyTrackedLines.Find(value1).Item1;
189+
var node2 = currentlyTrackedLines.Find(value2).Item1;
190+
191+
if (node1 == null || node2 == null)
192+
{
193+
throw new Exception("Value1, Value2 or both was not found in this BST.");
194+
}
195+
196+
var tmp = node1.Value;
197+
node1.Value = node2.Value;
198+
node2.Value = tmp;
199+
200+
currentlyTrackedLines.NodeLookUp[node1.Value] = node1;
201+
currentlyTrackedLines.NodeLookUp[node2.Value] = node2;
202+
}
203+
186204
private void enqueueIntersectionEvent(Event currentEvent, Point intersection)
187205
{
188206
if (intersection == null)

0 commit comments

Comments
 (0)