I'm trying to learn about the difference between red-black-trees, list and hashmaps and I havn't been able to get the red-black-tree that I found online to work. It keeps throwing a 'Object reference not set to an instance of an object error' and I can't find the reason why. This is my code.
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
namespace CSC510___HashMaps
{
struct UserInfo
{
public int userId;
public string userName;
public UserInfo(int id, string name)
{
userId = id;
userName = name;
}
}
class Program
{
static Hashtable userInfoHash;
static List<UserInfo> userInfoList;
static Stopwatch sw;
static void Main(string[] args)
{
userInfoHash = new Hashtable();
userInfoList = new List<UserInfo>();
RedBlackTree userInfoTree = new RedBlackTree();
sw = new Stopwatch();
//Adding
for (int i = 0; i < 4000000; i++)
{
userInfoHash.Add(i, "user" + i);
userInfoList.Add(new UserInfo(i, "user" + i));
userInfoTree.TreeInsert("user" + i);
}
//Removing
if (userInfoHash.ContainsKey(0))
{
userInfoHash.Remove(0);
}
//Setting
if (userInfoHash.ContainsKey(1))
{
userInfoHash[1] = "replacementName";
}
//Looping
/*foreach (DictionaryEntry entry in userInfoHash)
{
Console.WriteLine("Key: " + entry.Key + " / Value: " + entry.Value);
}*/
//Access
//Near Constant O(1) lookup times on massively scaled collections
//Using a stopwatch to show difference between list and hashmap
Random randomUserGen = new Random();
int randomUser = -1;
IComparable irandomUser = randomUser;
sw.Start();
float startTime = 0;
float endTime = 0;
float deltaTime = 0;
int cycles = 5;
int cycle = 0;
string userName = string.Empty;
while (cycle < cycles)
{
randomUser = randomUserGen.Next(3000000, 4000000);
startTime = sw.ElapsedMilliseconds;
//access from list
userName = GetUserFromList(randomUser);
endTime = sw.ElapsedMilliseconds;
deltaTime = endTime - startTime;
Console.WriteLine("Time taken to retrieve " + userName + "from list took " + string.Format("{0:0.##}", deltaTime) + "ms");
startTime = sw.ElapsedMilliseconds;
userName = (string)userInfoTree.Search(randomUser);
endTime = sw.ElapsedMilliseconds;
deltaTime = endTime - startTime;
Console.WriteLine("Time taken to retrieve " + userName + "from tree took " + string.Format("{0:0.##}", deltaTime) + "ms");
startTime = sw.ElapsedMilliseconds;
//access from hash
userName = (string)userInfoHash[randomUser];
endTime = sw.ElapsedMilliseconds;
deltaTime = endTime - startTime;
Console.WriteLine("Time taken to retrieve " + userName + "from hash took " + string.Format("{0:0.##}", deltaTime) + "ms");
Console.WriteLine();
cycle++;
}
}
static string GetUserFromList(int userId)
{
for (int i = 0; i < userInfoList.Count; i++)
{
if (userInfoList[i].userId == userId)
{
return userInfoList[i].userName;
}
}
return string.Empty;
}
//Tree stuff (Red-Black)
public enum Color
{
Red = 0, Black = 1
}
public enum Direction
{
Left,
Right
}
public class Node
{
public IComparable data;
public Node left;
public Node right;
public Color color = Color.Black;
public Node(IComparable data) : this(data, null, null) { }
public Node(IComparable data, Node left, Node right)
{
this.data = data;
this.left = left;
this.right = right;
}
}
public class Tree
{
protected Node root;
protected Node freshNode;
protected Node currentNode;
protected Tree()
{
freshNode = new Node(null);
freshNode.left = freshNode.right = freshNode;
root = new Node(null);
}
protected int Compare(IComparable item, Node node)
{
if (item != root) return item.CompareTo(node.data);
else return 1;
}
public IComparable Search(IComparable data)
{
freshNode.data = data;
currentNode = root.right;
while (true)
{
if (Compare(data, currentNode) < 0) currentNode = currentNode.left;
else if (Compare(data, currentNode) > 0) currentNode = currentNode.right;
else if (currentNode != freshNode) return currentNode.data;
else return null;
}
}
protected void Display()
{
this.Display(root.right);
}
protected void Display(Node temp)
{
if (temp != freshNode)
{
Display(temp.left);
Console.WriteLine(temp.data);
Display(temp.right);
}
}
}
public sealed class RedBlackTree: Tree
{
private Color Black = Color.Black;
private Color Red = Color.Red;
private Node parentNode;
private Node grandParentNode;
private Node tempNode;
public void TreeInsert(IComparable item)
{
currentNode = parentNode = grandParentNode = root;
freshNode.data = item;
int returnedValue = 0;
while(Compare(item, currentNode) != 0)
{
tempNode = grandParentNode;
grandParentNode = parentNode;
parentNode = currentNode;
returnedValue = Compare(item, currentNode);
if (returnedValue < 0) currentNode = currentNode.left;
else currentNode = currentNode.right;
if (currentNode.left.color == Color.Red && currentNode.right.color == Color.Red) ReArrange(item);
}
if(currentNode == freshNode)
{
currentNode = new Node(item, freshNode, freshNode);
if (Compare(item, parentNode) < 0) parentNode.left = currentNode;
else parentNode.right = currentNode;
ReArrange(item);
}
}
private void ReArrange(IComparable item)
{
currentNode.color = Red;
currentNode.left.color = Color.Black;
currentNode.right.color = Color.Black;
if (parentNode.color == Color.Red)
{
grandParentNode.color = Color.Red;
bool compareWithGrandParentNode = (Compare(item, parentNode) < 0);
bool compareWithParentNode = (Compare(item, parentNode) < 0);
if (compareWithGrandParentNode != compareWithParentNode) parentNode = Rotate(item, grandParentNode);
currentNode = Rotate(item, tempNode);
currentNode.color = Black;
}
root.right.color = Color.Black;
}
private Node Rotate(IComparable item, Node parentNode)
{
int value;
if (Compare(item, parentNode) < 0)
{
value = Compare(item, parentNode.left);
if (value < 0) parentNode.left = this.Rotate(parentNode.left, Direction.Left);
else parentNode.left = this.Rotate(parentNode.left, Direction.Right);
return parentNode.left;
}
else
{
value = Compare(item, parentNode.right);
if (value < 0) parentNode.right = this.Rotate(parentNode.right, Direction.Left);
else parentNode.right = this.Rotate(parentNode.right, Direction.Right);
return parentNode.right;
}
}
private Node Rotate(Node node, Direction direction)
{
Node tempNode;
if (direction == Direction.Left)
{
tempNode = node.left;
node.left = tempNode.right;
tempNode.right = node;
return tempNode;
}
else
{
tempNode = node.right;
node.right = tempNode.left;
tempNode.right = node;
return tempNode;
}
}
}
}
}
The problem is in this block of code:
public void TreeInsert(IComparable item)
{
currentNode = parentNode = grandParentNode = root;
freshNode.data = item;
int returnedValue = 0;
while(Compare(item, currentNode) != 0)
{
tempNode = grandParentNode;
grandParentNode = parentNode;
parentNode = currentNode;
returnedValue = Compare(item, currentNode);
if (returnedValue < 0) currentNode = currentNode.left;
else currentNode = currentNode.right;
if (currentNode.left.color == Color.Red && currentNode.right.color == Color.Red) ReArrange(item);
}
if(currentNode == freshNode)
{
currentNode = new Node(item, freshNode, freshNode);
if (Compare(item, parentNode) < 0) parentNode.left = currentNode;
else parentNode.right = currentNode;
ReArrange(item);
}
}
This line specifically:
if (currentNode.left.color == Color.Red && currentNode.right.color == Color.Red) ReArrange(item);
It keeps saying currentNode is null.
Thank you for your help!
