Skip to content

Commit 9ffeab5

Browse files
justcoding121justcoding121
committed
set bst count
1 parent dcee2b6 commit 9ffeab5

File tree

9 files changed

+198
-46
lines changed

9 files changed

+198
-46
lines changed

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

Lines changed: 17 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -40,6 +40,7 @@ public AVLTree(IEnumerable<T> sortedKeys, bool enableNodeLookUp = false)
4040
var nodes = sortedKeys.Select(x => new AVLTreeNode<T>(null, x)).ToArray();
4141
Root = (AVLTreeNode<T>)ToBST(nodes);
4242
recomputeHeight(Root);
43+
assignCount(Root);
4344
Count = nodes.Length;
4445
}
4546

@@ -136,6 +137,7 @@ private void insert(AVLTreeNode<T> node, T value)
136137
updateHeight(node);
137138
balance(node);
138139

140+
node.UpdateCounts();
139141
}
140142

141143

@@ -173,6 +175,7 @@ private void delete(AVLTreeNode<T> node, T value)
173175
{
174176
throw new Exception("Item do not exist");
175177
}
178+
176179
delete(node.Right, value);
177180
}
178181
//node is less than the search value so move left to find the deletion node
@@ -204,8 +207,8 @@ private void delete(AVLTreeNode<T> node, T value)
204207
{
205208
node.Parent.Right = null;
206209
}
207-
baseCase = true;
208210

211+
baseCase = true;
209212
}
210213
else
211214
{
@@ -233,8 +236,8 @@ private void delete(AVLTreeNode<T> node, T value)
233236

234237
node.Left.Parent = node.Parent;
235238
}
236-
baseCase = true;
237239

240+
baseCase = true;
238241
}
239242
//case two - left tree is null (move sub tree up)
240243
else if (node.Right != null && node.Left == null)
@@ -257,11 +260,11 @@ private void delete(AVLTreeNode<T> node, T value)
257260
{
258261
node.Parent.Right = node.Right;
259262
}
260-
node.Right.Parent = node.Parent;
261263

264+
node.Right.Parent = node.Parent;
262265
}
263-
baseCase = true;
264266

267+
baseCase = true;
265268
}
266269
//case three - two child trees
267270
//replace the node value with maximum element of left subtree (left max node)
@@ -285,16 +288,17 @@ private void delete(AVLTreeNode<T> node, T value)
285288

286289
if (baseCase)
287290
{
291+
node.Parent.UpdateCounts();
288292
updateHeight(node.Parent);
289293
balance(node.Parent);
290294
}
291295
else
292296
{
297+
node.UpdateCounts();
293298
updateHeight(node);
294299
balance(node);
295300
}
296301

297-
298302
}
299303

300304
/// <summary>
@@ -482,6 +486,10 @@ private void rightRotate(AVLTreeNode<T> node)
482486

483487
updateHeight(newRoot);
484488

489+
newRoot.Left.UpdateCounts();
490+
newRoot.Right.UpdateCounts();
491+
newRoot.UpdateCounts();
492+
485493
if (prevRoot == Root)
486494
{
487495
Root = newRoot;
@@ -524,6 +532,10 @@ private void leftRotate(AVLTreeNode<T> node)
524532

525533
updateHeight(newRoot);
526534

535+
newRoot.Left.UpdateCounts();
536+
newRoot.Right.UpdateCounts();
537+
newRoot.UpdateCounts();
538+
527539
if (prevRoot == Root)
528540
{
529541
Root = newRoot;

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

Lines changed: 20 additions & 30 deletions
Original file line numberDiff line numberDiff line change
@@ -25,6 +25,7 @@ public BST(IEnumerable<T> sortedKeys) : this()
2525
ValidateCollection(sortedKeys);
2626
var nodes = sortedKeys.Select(x => new BSTNode<T>(null, x)).ToArray();
2727
Root = (BSTNode<T>)ToBST(nodes);
28+
assignCount(Root);
2829
Count = nodes.Length;
2930
}
3031

@@ -89,7 +90,8 @@ public void Insert(T value)
8990
return;
9091
}
9192

92-
insert(Root, value);
93+
var newNode = insert(Root, value);
94+
newNode.UpdateCounts(true);
9395
Count++;
9496
}
9597

@@ -144,22 +146,9 @@ public void Delete(T value)
144146
throw new Exception("Empty BST");
145147
}
146148

147-
delete(Root, value);
148-
Count--;
149-
}
150-
151-
internal BSTNode<T> DeleteAndReturnParent(T value)
152-
{
153-
if (Root == null)
154-
{
155-
throw new Exception("Empty BST");
156-
}
157-
158-
var parentNode = delete(Root, value);
159-
149+
var deleted = delete(Root, value);
150+
deleted.UpdateCounts(true);
160151
Count--;
161-
162-
return parentNode;
163152
}
164153

165154
//worst O(n) for unbalanced tree
@@ -177,44 +166,45 @@ private BSTNode<T> delete(BSTNode<T> node, T value)
177166
node = node.Right ?? throw new Exception("Item do not exist");
178167
continue;
179168
}
180-
//node is less than the search value so move left to find the deletion node
181169

170+
//node is less than the search value so move left to find the deletion node
182171
if (compareResult > 0)
183172
{
184173
node = node.Left ?? throw new Exception("Item do not exist");
185174
continue;
186175
}
187176
}
188177

178+
if (node == null)
179+
{
180+
return null;
181+
}
182+
183+
189184
//node is a leaf node
190-
if (node != null && node.IsLeaf)
185+
if (node.IsLeaf)
191186
{
192187
deleteLeaf(node);
193-
return node.Parent;
188+
return node;
194189
}
195190

196191
//case one - right tree is null (move sub tree up)
197-
if (node?.Left != null && node.Right == null)
192+
if (node.Left != null && node.Right == null)
198193
{
199194
deleteLeftNode(node);
200-
return node.Parent;
195+
return node;
201196
}
202-
//case two - left tree is null (move sub tree up)
203197

204-
if (node?.Right != null && node.Left == null)
198+
//case two - left tree is null (move sub tree up)
199+
if (node.Right != null && node.Left == null)
205200
{
206201
deleteRightNode(node);
207-
return node.Parent;
202+
return node;
208203
}
204+
209205
//case three - two child trees
210206
//replace the node value with maximum element of left subtree (left max node)
211207
//and then delete the left max node
212-
213-
if (node == null)
214-
{
215-
continue;
216-
}
217-
218208
var maxLeftNode = FindMax(node.Left);
219209

220210
node.Value = maxLeftNode.Value;

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

Lines changed: 13 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -26,6 +26,7 @@ public SplayTree(IEnumerable<T> collection) : this()
2626
ValidateCollection(collection);
2727
var nodes = collection.Select(x => new SplayTreeNode<T>(null, x)).ToArray();
2828
Root = (SplayTreeNode<T>)ToBST(nodes);
29+
assignCount(Root);
2930
Count = nodes.Length;
3031
}
3132

@@ -74,7 +75,6 @@ public void Insert(T value)
7475
}
7576

7677
var newNode = insert(Root, value);
77-
7878
splay(newNode);
7979
Count++;
8080
}
@@ -320,6 +320,8 @@ private SplayTreeNode<T> find(SplayTreeNode<T> parent, T value)
320320

321321
private void splay(SplayTreeNode<T> x)
322322
{
323+
x.UpdateCounts();
324+
323325
while (x.Parent != null)
324326
{
325327
if (x.Parent.Parent == null)
@@ -352,6 +354,8 @@ private void splay(SplayTreeNode<T> x)
352354
leftRotate(x.Parent);
353355
x = rightRotate(x.Parent);
354356
}
357+
358+
x.UpdateCounts();
355359
}
356360
}
357361

@@ -391,6 +395,10 @@ private SplayTreeNode<T> rightRotate(SplayTreeNode<T> currentRoot)
391395
newRoot.Right.Left.Parent = newRoot.Right;
392396
}
393397

398+
newRoot.Left.UpdateCounts();
399+
newRoot.Right.UpdateCounts();
400+
newRoot.UpdateCounts();
401+
394402
if (prevRoot == Root)
395403
{
396404
Root = newRoot;
@@ -436,6 +444,10 @@ private SplayTreeNode<T> leftRotate(SplayTreeNode<T> currentRoot)
436444
newRoot.Left.Right.Parent = newRoot.Left;
437445
}
438446

447+
newRoot.Left.UpdateCounts();
448+
newRoot.Right.UpdateCounts();
449+
newRoot.UpdateCounts();
450+
439451
if (prevRoot == Root)
440452
{
441453
Root = newRoot;

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

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -27,6 +27,7 @@ public TreapTree(IEnumerable<T> collection) : this()
2727
var nodes = collection.Select(x => new TreapTreeNode<T>(null, x, rndGenerator.Next())).ToArray();
2828
Root = (TreapTreeNode<T>)ToBST(nodes);
2929
Count = nodes.Length;
30+
assignCount(Root);
3031
heapify(Root);
3132
}
3233
/// <summary>
@@ -195,6 +196,8 @@ private void delete(TreapTreeNode<T> node, T value)
195196

196197
break;
197198
}
199+
200+
node.UpdateCounts(true);
198201
}
199202

200203
private void deleteLeaf(TreapTreeNode<T> node)
@@ -335,6 +338,7 @@ private void heapify(TreapTreeNode<T> node)
335338
{
336339
while (node.Parent != null)
337340
{
341+
node.UpdateCounts();
338342
if (node.Priority < node.Parent.Priority)
339343
{
340344
node = node.IsLeftChild ? rightRotate(node.Parent) : leftRotate(node.Parent);
@@ -345,6 +349,7 @@ private void heapify(TreapTreeNode<T> node)
345349
}
346350
}
347351

352+
node.UpdateCounts(true);
348353
}
349354

350355
/// <summary>
@@ -383,6 +388,10 @@ private TreapTreeNode<T> rightRotate(TreapTreeNode<T> currentRoot)
383388
newRoot.Right.Left.Parent = newRoot.Right;
384389
}
385390

391+
newRoot.Left.UpdateCounts();
392+
newRoot.Right.UpdateCounts();
393+
newRoot.UpdateCounts();
394+
386395
if (prevRoot == Root)
387396
{
388397
Root = newRoot;
@@ -429,6 +438,10 @@ private TreapTreeNode<T> leftRotate(TreapTreeNode<T> currentRoot)
429438
newRoot.Left.Right.Parent = newRoot.Left;
430439
}
431440

441+
newRoot.Left.UpdateCounts();
442+
newRoot.Right.UpdateCounts();
443+
newRoot.UpdateCounts();
444+
432445
if (prevRoot == Root)
433446
{
434447
Root = newRoot;

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

Lines changed: 7 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -94,7 +94,7 @@ public void AVLTree_Smoke_Test()
9494
}
9595

9696
[TestMethod]
97-
public void AVLTree_AccuracyTest()
97+
public void AVLTree_Accuracy_Test()
9898
{
9999
var nodeCount = 1000;
100100

@@ -110,8 +110,8 @@ public void AVLTree_AccuracyTest()
110110
tree.Insert(sortedNumbers[i]);
111111

112112
Assert.IsTrue(tree.HasItem(sortedNumbers[i]));
113-
114113
Assert.IsTrue(tree.Root.IsBinarySearchTree(int.MinValue, int.MaxValue));
114+
tree.Root.VerifyCount();
115115

116116
var actualHeight = tree.GetHeight();
117117

@@ -133,6 +133,7 @@ public void AVLTree_AccuracyTest()
133133
{
134134
tree.Delete(sortedNumbers[i]);
135135

136+
tree.Root.VerifyCount();
136137
Assert.IsTrue(tree.Root.IsBinarySearchTree(int.MinValue, int.MaxValue));
137138

138139
var actualHeight = tree.GetHeight();
@@ -159,10 +160,13 @@ public void AVLTree_BulkInit_Test()
159160
Assert.IsTrue(tree.Root.IsBinarySearchTree(int.MinValue, int.MaxValue));
160161
Assert.AreEqual(tree.Count, tree.Count());
161162

163+
tree.Root.VerifyCount();
164+
162165
for (int i = 0; i < nodeCount; i++)
163166
{
164167
tree.Delete(randomNumbers[i]);
165168

169+
tree.Root.VerifyCount();
166170
Assert.IsTrue(tree.Root.IsBinarySearchTree(int.MinValue, int.MaxValue));
167171

168172
var actualHeight = tree.GetHeight();
@@ -179,7 +183,7 @@ public void AVLTree_BulkInit_Test()
179183
}
180184

181185
[TestMethod]
182-
public void AVLTree_StressTest()
186+
public void AVLTree_Stress_Test()
183187
{
184188
var nodeCount = 1000 * 10;
185189

0 commit comments

Comments
 (0)