A* path finding algorithm for a red-black tree

Question

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;
        }
    }        
}

Answer 1

I've made the classes more idiomatic for C# by using properties, recommended capitalization and an enum (as opposed to a bool for red-ness and black-ness). It also allowed for removal of extraneous code such as else-blocks that follow breaks or returns and simplification of to the ternary operator.

namespace RedBlackTree
{
    internal enum RedBlackIndicator
    {
        Red,

        Black
    }

    // 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.
    internal class RedBlackTree
    {
        private rbtNode root;

        public int Count { get; private set; }

        ////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)
        {
            var n = new rbtNode(value);

            if (this.root == null)
            {
                this.root = n;
            }
            else
            {
                var current = this.root;

                while (true)
                {
                    if (current.F == value.F)
                    {
                        return;
                    }

                    if (value.F < current.F)
                    {
                        if (n.Left == null)
                        {
                            current.Left = n;
                            break;
                        }

                        current = current.Left;
                    }
                    else if (value.F > current.F)
                    {
                        if (current.Right == null)
                        {
                            current.Right = n;
                            break;
                        }

                        current = current.Right;
                    }
                }

                n.Parent = current;
            }

            this.Count++;
            this.InsertCase1(n);
        }

        private static rbtNode Uncle(rbtNode node)
        {
            return node.Parent == null ? null : Sibling(node.Parent);
        }

        private static rbtNode Sibling(rbtNode node)
        {
            return node.Parent == null ? null : (node == node.Parent.Left ? node.Parent.Left : node.Parent.Right);
        }

        private static rbtNode Grandparent(rbtNode n)
        {
            return n == null || n.Parent == null ? null : n.Parent.Parent;
        }

        // Root node test, make it black
        private void InsertCase1(rbtNode node)
        {
            if (node.Parent == null)
            {
                node.Colour = RedBlackIndicator.Black;
            }
            else
            {
                this.InsertCase2(node);
            }
        }

        // Node has black parent == No problems!
        private void InsertCase2(rbtNode node)
        {
            if (node.Parent.Colour != RedBlackIndicator.Red)
            {
                this.InsertCase3(node);
            }
        }

        // 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 node)
        {
            if (Uncle(node).Colour == RedBlackIndicator.Red)
            {
                node.Parent.Colour = RedBlackIndicator.Black;
                Uncle(node).Colour = RedBlackIndicator.Black;
                Grandparent(node).Colour = RedBlackIndicator.Red;
                this.InsertCase1(Grandparent(node));
            }
            else
            {
                this.InsertCase4(node);
            }
        }

        // 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 node)
        {
            if (node == node.Parent.Right && node.Parent == Grandparent(node).Left)
            {
                this.RotateLeft(node.Parent);
                node = node.Left;
            }
            else if (node == node.Parent.Left && node.Parent == Grandparent(node).Right)
            {
                this.RotateRight(node.Parent);
                node = node.Right;
            }

            this.InsertCase5(node);
        }

        private void InsertCase5(rbtNode node)
        {
            node.Parent.Colour = RedBlackIndicator.Black;
            Grandparent(node).Colour = RedBlackIndicator.Red;
            if (node == node.Parent.Left && node.Parent == Grandparent(node).Left)
            {
                this.RotateRight(Grandparent(node));
            }
            else if (node == node.Parent.Right && node.Parent == Grandparent(node).Right)
            {
                this.RotateLeft(Grandparent(node));
            }
        }

        #endregion

        private void RotateRight(rbtNode node)
        {
            var temp = node.Left;

            this.ReplaceNode(node, temp);
            node.Left = temp.Right;
            if (temp.Right != null)
            {
                temp.Right.Parent = node;
            }

            temp.Right = node;
            node.Parent = temp;
        }

        private void RotateLeft(rbtNode node)
        {
            var temp = node.Right;

            this.ReplaceNode(node, temp);
            node.Right = temp.Left;
            if (temp.Left != null)
            {
                temp.Left.Parent = node;
            }

            temp.Left = node;
            node.Parent = temp;
        }

        private void ReplaceNode(rbtNode oldNode, rbtNode newNode)
        {
            // This function does a lot of the hard work when swapping nodes. Reassigns parents and children.
            if (oldNode.Parent == null)
            {
                this.root = newNode;
            }
            else
            {
                if (oldNode == oldNode.Parent.Left)
                {
                    oldNode.Parent.Left = newNode;
                }
                else
                {
                    oldNode.Parent.Right = newNode;
                }
            }

            if (newNode != null)
            {
                newNode.Parent = oldNode.Parent;
            }
        }

        private sealed class rbtNode
        {
            private readonly int key;

            private readonly int f;

            internal rbtNode(Node node)
            {
                this.key = node.Key;
                this.f = node.F;
                this.Colour = RedBlackIndicator.Red;
            }

            public int Key
            {
                get
                {
                    return this.key;
                }
            }

            public int F
            {
                get
                {
                    return this.f;
                }
            }

            internal RedBlackIndicator Colour { get; set; }

            internal rbtNode Parent { get; set; }

            internal rbtNode Left { get; set; }

            internal rbtNode Right { get; set; }
        }
    }
}

Answer 2

Edit / Update:

I noticed that you have a misplaced curly bracket (}) that makes it so that your last class is inside of your first class, meaning that this code shouldn't compile.

---

For some reason I don't like Else if at the end of an if..then..else block, that might just be personal style/opinion but I figured that I would throw that out there.

I also noticed that there were a couple of If...then...else blocks that end with an Else if like this one

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;
    }
}

I would probably rewrite it like

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 (current.right == null)
    {
        current.right = n;
        break;
    }
    else
    {
        current = current.right;
    }
}

Notice that I changed else if (value.F > current.F) to else, I didn't see how there could be another case after that, so showing that anything other then the first two cases would fall into this category.

your if...then...else blocks can really screw with an application, you can have all the right code in them but have them in totally the wrong order, I would be specific in the way that you form them and have a set pattern that you use, so that when you look back at it you can tell what is priority one, because the first one it hits is the only one it hits and then it ducks out of the if statement.

As far as the Delete() Method, add it and see if it works the way you intend it to.

Answer 3

I see code I can't quite believe true.
rbtNode Uncle(rbtNode n) has been competently condensed by Jesse C. Slicer, but

private static rbtNode Sibling(rbtNode node) {
    return node.Parent == null ? null
        : (node == node.Parent.Left ? node.Parent.Left : node.Parent.Right);
}

seems to just return node instead of its sibling just as the original.
In Insert(Node value), an rbtNode is instantiated unconditionally, to immediately fall into oblivion when "the F value" is found.
Nothing (much) wrong with that, but if n had not been defined beforehand,

if (value.F < current.F) {
    if (n.left == null) {
        current.left = n;
        break;
    }
    current = current.left;
} else if (value.F > current.F) {
    if (current.right == null) {
        current.right = n;
        break;
    }
    current = current.right;
}

would have been more eye-catching.