Skip to content

Commit 9cfc710

Browse files
justcoding121justcoding121
committed
eliminate bst base
1 parent 1f7a7cc commit 9cfc710

File tree

7 files changed

+33
-29
lines changed

7 files changed

+33
-29
lines changed

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

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@ namespace Advanced.Algorithms.DataStructures
88
/// <summary>
99
/// An AVL tree implementation.
1010
/// </summary>
11-
public class AVLTree<T> : BSTBase<T>, IEnumerable<T> where T : IComparable
11+
public class AVLTree<T> : IEnumerable<T> where T : IComparable
1212
{
1313
private readonly Dictionary<T, BSTNodeBase<T>> nodeLookUp;
1414

@@ -35,11 +35,11 @@ public AVLTree(bool enableNodeLookUp = false)
3535
/// at the cost of additional space.</param>
3636
public AVLTree(IEnumerable<T> sortedCollection, bool enableNodeLookUp = false)
3737
{
38-
ValidateSortedCollection(sortedCollection);
38+
BSTHelpers.ValidateSortedCollection(sortedCollection);
3939
var nodes = sortedCollection.Select(x => new AVLTreeNode<T>(null, x)).ToArray();
40-
Root = (AVLTreeNode<T>)ToBST(nodes);
40+
Root = (AVLTreeNode<T>)BSTHelpers.ToBST(nodes);
4141
recomputeHeight(Root);
42-
assignCount(Root);
42+
BSTHelpers.AssignCount(Root);
4343

4444
if (enableNodeLookUp)
4545
{

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

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@ namespace Advanced.Algorithms.DataStructures
88
/// <summary>
99
/// A binary search tree implementation.
1010
/// </summary>
11-
public class BST<T> : BSTBase<T>, IEnumerable<T> where T : IComparable
11+
public class BST<T> : IEnumerable<T> where T : IComparable
1212
{
1313
internal BSTNode<T> Root { get; set; }
1414

@@ -22,10 +22,10 @@ public BST() { }
2222
/// </summary>
2323
public BST(IEnumerable<T> sortedCollection) : this()
2424
{
25-
ValidateSortedCollection(sortedCollection);
25+
BSTHelpers.ValidateSortedCollection(sortedCollection);
2626
var nodes = sortedCollection.Select(x => new BSTNode<T>(null, x)).ToArray();
27-
Root = (BSTNode<T>)ToBST(nodes);
28-
assignCount(Root);
27+
Root = (BSTNode<T>)BSTHelpers.ToBST(nodes);
28+
BSTHelpers.AssignCount(Root);
2929
}
3030

3131
/// <summary>

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

Lines changed: 6 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@ namespace Advanced.Algorithms.DataStructures
88
/// <summary>
99
/// A red black tree implementation.
1010
/// </summary>
11-
public class RedBlackTree<T> : BSTBase<T>, IEnumerable<T> where T : IComparable
11+
public class RedBlackTree<T> : IEnumerable<T> where T : IComparable
1212
{
1313
//only used internally by Bentley-Ottmann sweepline algorithm for faster line swap operation.
1414
private readonly Dictionary<T, BSTNodeBase<T>> nodeLookUp;
@@ -36,11 +36,11 @@ public RedBlackTree(bool enableNodeLookUp = false)
3636
/// at the cost of additional space.</param>
3737
public RedBlackTree(IEnumerable<T> sortedCollection, bool enableNodeLookUp = false)
3838
{
39-
ValidateSortedCollection(sortedCollection);
39+
BSTHelpers.ValidateSortedCollection(sortedCollection);
4040
var nodes = sortedCollection.Select(x => new RedBlackTreeNode<T>(null, x)).ToArray();
41-
Root = (RedBlackTreeNode<T>)ToBST(nodes);
41+
Root = (RedBlackTreeNode<T>)BSTHelpers.ToBST(nodes);
4242
assignColors(Root);
43-
assignCount(Root);
43+
BSTHelpers.AssignCount(Root);
4444

4545
if (enableNodeLookUp)
4646
{
@@ -184,7 +184,7 @@ public int Insert(T value)
184184
return (Root, 0);
185185
}
186186

187-
var newNode = Insert(Root, value);
187+
var newNode = insert(Root, value);
188188

189189
if (nodeLookUp != null)
190190
{
@@ -195,7 +195,7 @@ public int Insert(T value)
195195
}
196196

197197
//O(log(n)) always
198-
private (RedBlackTreeNode<T>, int) Insert(RedBlackTreeNode<T> currentNode, T newNodeValue)
198+
private (RedBlackTreeNode<T>, int) insert(RedBlackTreeNode<T> currentNode, T newNodeValue)
199199
{
200200
var insertionPosition = 0;
201201

‎src/Advanced.Algorithms/DataStructures/Tree/Shared/BSTExtensions.cs

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -223,5 +223,6 @@ internal static int Position<T>(this BSTNodeBase<T> node, T item) where T : ICom
223223
return position < 0 ? position : position + leftCount + 1;
224224
}
225225

226+
226227
}
227228
}

‎src/Advanced.Algorithms/DataStructures/Tree/Shared/BSTBase.cs renamed to ‎src/Advanced.Algorithms/DataStructures/Tree/Shared/BSTHelpers.cs

Lines changed: 10 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -1,36 +1,39 @@
11
using System;
22
using System.Collections.Generic;
3+
using System.Linq;
4+
using System.Text;
5+
using System.Threading.Tasks;
36

47
namespace Advanced.Algorithms.DataStructures
58
{
6-
public class BSTBase<T> where T : IComparable
9+
internal class BSTHelpers
710
{
8-
internal void ValidateSortedCollection(IEnumerable<T> sortedCollection)
11+
internal static void ValidateSortedCollection<T>(IEnumerable<T> sortedCollection) where T : IComparable
912
{
1013
if (!isSorted(sortedCollection))
1114
{
1215
throw new ArgumentException("Initial collection should have unique keys and be in sorted order.");
1316
}
1417
}
1518

16-
internal BSTNodeBase<T> ToBST(BSTNodeBase<T>[] sortedNodes)
19+
internal static BSTNodeBase<T> ToBST<T>(BSTNodeBase<T>[] sortedNodes) where T : IComparable
1720
{
1821
return toBST(sortedNodes, 0, sortedNodes.Length - 1);
1922
}
2023

21-
internal int assignCount(BSTNodeBase<T> node)
24+
internal static int AssignCount<T>(BSTNodeBase<T> node) where T : IComparable
2225
{
2326
if (node == null)
2427
{
2528
return 0;
2629
}
2730

28-
node.Count = assignCount(node.Left) + assignCount(node.Right) + 1;
31+
node.Count = AssignCount(node.Left) + AssignCount(node.Right) + 1;
2932

3033
return node.Count;
3134
}
3235

33-
private BSTNodeBase<T> toBST(BSTNodeBase<T>[] sortedNodes, int start, int end)
36+
private static BSTNodeBase<T> toBST<T>(BSTNodeBase<T>[] sortedNodes, int start, int end) where T : IComparable
3437
{
3538
if (start > end)
3639
return null;
@@ -53,7 +56,7 @@ private BSTNodeBase<T> toBST(BSTNodeBase<T>[] sortedNodes, int start, int end)
5356
return root;
5457
}
5558

56-
private bool isSorted(IEnumerable<T> collection)
59+
private static bool isSorted<T>(IEnumerable<T> collection) where T : IComparable
5760
{
5861
var enumerator = collection.GetEnumerator();
5962
if (!enumerator.MoveNext())

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

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@ namespace Advanced.Algorithms.DataStructures
88
/// <summary>
99
/// A splay tree implementation.
1010
/// </summary>
11-
public class SplayTree<T> : BSTBase<T>, IEnumerable<T> where T : IComparable
11+
public class SplayTree<T> : IEnumerable<T> where T : IComparable
1212
{
1313
internal SplayTreeNode<T> Root { get; set; }
1414
public int Count => Root == null ? 0 : Root.Count;
@@ -21,10 +21,10 @@ public SplayTree() { }
2121
/// <param name="sortedCollection">The sorted collection.</param>
2222
public SplayTree(IEnumerable<T> sortedCollection) : this()
2323
{
24-
ValidateSortedCollection(sortedCollection);
24+
BSTHelpers.ValidateSortedCollection(sortedCollection);
2525
var nodes = sortedCollection.Select(x => new SplayTreeNode<T>(null, x)).ToArray();
26-
Root = (SplayTreeNode<T>)ToBST(nodes);
27-
assignCount(Root);
26+
Root = (SplayTreeNode<T>)BSTHelpers.ToBST(nodes);
27+
BSTHelpers.AssignCount(Root);
2828
}
2929

3030
/// <summary>

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

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@ namespace Advanced.Algorithms.DataStructures
88
/// <summary>
99
/// A treap tree implementation.
1010
/// </summary>
11-
public class TreapTree<T> : BSTBase<T>, IEnumerable<T> where T : IComparable
11+
public class TreapTree<T> : IEnumerable<T> where T : IComparable
1212
{
1313
private Random rndGenerator = new Random();
1414
internal TreapTreeNode<T> Root { get; set; }
@@ -23,10 +23,10 @@ public TreapTree() { }
2323
/// <param name="sortedCollection">The initial sorted collection.</param>
2424
public TreapTree(IEnumerable<T> sortedCollection) : this()
2525
{
26-
ValidateSortedCollection(sortedCollection);
26+
BSTHelpers.ValidateSortedCollection(sortedCollection);
2727
var nodes = sortedCollection.Select(x => new TreapTreeNode<T>(null, x, rndGenerator.Next())).ToArray();
28-
Root = (TreapTreeNode<T>)ToBST(nodes);
29-
assignCount(Root);
28+
Root = (TreapTreeNode<T>)BSTHelpers.ToBST(nodes);
29+
BSTHelpers.AssignCount(Root);
3030
heapify(Root);
3131
}
3232
/// <summary>

0 commit comments

Comments
 (0)