So far I've implemented a way to add to my RedBlackTree
(will be used with A* pathfinding - hence the F value). I'm not entirely sure how to improve it further.
I want to add a remove function to this tree, but can't find anything online that suits my style of tree. Any help? I only need to delete the first node. Also, what could I improve in my current code?
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace RedBlackTree
{
//From Wiki:
//The performance of an AA tree is equivalent to the performance of a red-black tree.
//While an AA tree makes more rotations than a red-black tree, the simpler algorithms tend to be faster, and all of this balances out to result in similar performance.
//A red-black tree is more consistent in its performance than an AA tree, but an AA tree tends to be flatter, which results in slightly faster search times.
class RedBlackTree
{
private const bool red = false;
private const bool black = true;
private rbtNode root;
private int _count = 0;
public int count { get { return _count; } }
//public bool Contains(PNode Key)
//{
// Node current = root;
// while (current != null)
// {
// if (current.Key == Key)
// {
// return true;
// }
// else if (value < current.value)
// {
// current = current.left;
// }
// else
// {
// current = current.right;
// }
// }
// return false;
//}
#region Insert Methods
public void Insert(Node value)
{
rbtNode n = new rbtNode(value);
if (root == null)
{
root = n;
}
else
{
rbtNode current = root;
while (true)
{
if (current.F == value.F)
{
return;
}
else if (value.F < current.F)
{
if (n.left == null)
{
current.left = n;
break;
}
else
{
current = current.left;
}
}
else if (value.F > current.F)
{
if (current.right == null)
{
current.right = n;
break;
}
else
{
current = current.right;
}
}
}
n.parent = current;
}
_count++;
InsertCase1(n);
}
//Root node test, make it black
private void InsertCase1(rbtNode n)
{
if (n.parent == null)
{
n.colour = black;
}
else
{
InsertCase2(n);
}
}
//Node has black parent == No problems!
private void InsertCase2(rbtNode n)
{
if (n.parent.colour == black)
{
return;
}
else
{
InsertCase3(n);
}
}
// If Uncle is red, there is a certain error since we are red and parent is red
// Make g red, and u and p black. No more error. Red grandparent needs to be checked though
// If uncle isn't red and parent IS red then the fix is different, and we move to case 4
private void InsertCase3(rbtNode n)
{
if (Uncle(n).colour == red)
{
n.parent.colour = black;
Uncle(n).colour = black;
Grandparent(n).colour = red;
InsertCase1(Grandparent(n));
}
else
{
InsertCase4(n);
}
}
// This case tests if the tree is in one of 2 forms which
// need to be converted to other forms before they can be
// fixed in case 5 (conversion is by rotation, left or right)
// These are:
// n = left child of right child
// n = right child of left child
// Any forms not covered in case 4 are already fine for processing by case 5.
// e.g.
// n = left child of left child
// n = right child of right child
private void InsertCase4(rbtNode n)
{
if (n == n.parent.right && n.parent == Grandparent(n).left)
{
RotateLeft(n.parent);
n = n.left;
}
else if (n == n.parent.left && n.parent == Grandparent(n).right)
{
RotateRight(n.parent);
n = n.right;
}
InsertCase5(n);
}
private void InsertCase5(rbtNode n)
{
n.parent.colour = black;
Grandparent(n).colour = red;
if (n == n.parent.left && n.parent == Grandparent(n).left)
{
RotateRight(Grandparent(n));
}
else if (n == n.parent.right && n.parent == Grandparent(n).right)
{
RotateLeft(Grandparent(n));
}
}
#endregion
private void RotateRight(rbtNode n)
{
rbtNode temp = n.left;
ReplaceNode(n, temp);
n.left = temp.right;
if (temp.right != null)
{
temp.right.parent = n;
}
temp.right = n;
n.parent = temp;
}
private void RotateLeft(rbtNode n)
{
rbtNode temp = n.right;
ReplaceNode(n, temp);
n.right = temp.left;
if (temp.left != null)
{
temp.left.parent = n;
}
temp.left = n;
n.parent = temp;
}
private void ReplaceNode(rbtNode oldn, rbtNode newn)
{
//This function does a lot of the hard work when swapping nodes. Reassigns parents and children.
if (oldn.parent == null)
{
root = newn;
}
else
{
if (oldn == oldn.parent.left)
{
oldn.parent.left = newn;
}
else
{
oldn.parent.right = newn;
}
}
if (newn != null)
{
newn.parent = oldn.parent;
}
}
private rbtNode Uncle(rbtNode n)
{
if (n.parent != null)
{
return Sibling(n.parent);
}
else
{
return null;
}
}
private rbtNode Sibling(rbtNode n)
{
if (n.parent != null)
{
if (n == n.parent.left)
{
return n.parent.left;
}
else
{
return n.parent.right;
}
}
else
{
return null;
}
}
private rbtNode Grandparent(rbtNode n)
{
if (n != null && n.parent != null)
return n.parent.parent;
return null;
}
class rbtNode
{
public int Key;
public int F;
internal bool colour = false; //true = black, false = red
internal rbtNode parent;
internal rbtNode left;
internal rbtNode right;
internal rbtNode(Node Value)
{
this.Key = Value.Key;
this.F = Value.F;
left = null;
right = null;
}
}
}
void Insert()
, checking the noden
just createdif (n.left == null)
looks wrong: improve them. \$\endgroup\$ – greybeard Feb 4 '20 at 16:11