Правильна ли эта реализация Red Black Tree C #?

Question

Пожалуйста, критикуйте мой код.Я заметил, что моя последняя ошибка завершилась со значением 277. Я ожидал, что значение 255 (1/2 500 + 10)Это действительный тест или я сделал что-то не так?

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace RedBlackTree
{
    public enum NodeColor
    { 
        Red,
        Black
    }

    public enum NodeSide
    { 
        Left,
        Right,
        None
    }


    public class RedBlackTreeNode<T>
        where T : IComparable<T>
    {
        public RedBlackTreeNode<T> Left { get; set; }
        public RedBlackTreeNode<T> Right { get; set; }
        public RedBlackTreeNode<T> Parent { get; set; }
        public T Data {get; set;}
        public NodeColor Color { get; set; }
        public RedBlackTreeNode<T> Uncle
        {
            get
            {
                if (WhichSideAmIOn() == NodeSide.Left)
                {
                    return this.Parent.Right;
                }
                else
                    return this.Parent.Left;
            }
        }

        public string ToString()
        {
            return String.Format("Me: {0} Left: {1} Right: {2}", Data, Left != null ? Left.Data.ToString() : "null", Right != null ? Right.Data.ToString() : "null");
        }
        public NodeSide WhichSideAmIOn()
        {
            if (this.Parent == null) return NodeSide.None;
            if (this.Parent.Left == this)
                return NodeSide.Left;
            if (this.Parent.Right == this)
                return NodeSide.Right;

            throw new Exception("Impossible - there can be only two sides. You must not be a child of your parent.");
        }

    }

    public class RedBlackTree<T>
        where T : IComparable<T>
    {
        private RedBlackTreeNode<T> Root { get; set; }

        public void InsertNode(T data)
        { 
            //make a node to hold the data - always red
            RedBlackTreeNode<T> newNode = new RedBlackTreeNode<T>();
            newNode.Data = data;
            newNode.Color = NodeColor.Red;

            //rule 1 - if the root is null, then hte new node is the root and roots can't be red.
            if (Root == null)
            {
                Root = newNode;
                Root.Color = NodeColor.Black;
                return;
            }

            //otherwise if we're not the first node, insert by walking.
            RedBlackTreeNode<T> walker = Root;
            while (walker != null)
            {
                if (newNode.Data.CompareTo(walker.Data)< 0) 
                { 
                    //walk left
                    if (walker.Left == null) 
                    {
                        walker.Left = newNode;
                        newNode.Parent = walker;
                        break;                     
                    }
                    else
                    {
                        walker = walker.Left;     
                    }
                }
                else if (newNode.Data.CompareTo(walker.Data) > 0)
                {
                    //walk right
                    if (walker.Right == null) 
                    {
                        walker.Right = newNode;
                        newNode.Parent = walker;
                        break;                     
                    }
                    else
                    {
                        walker = walker.Right;
                    }
                }
                else //todo: remove me
                { 
                    //we're equal, ignore this node in general
                    return;
                }
            }

            //rebalance - 
            //at this point we have the parent , we have the newnode and we need to implement some rules.
            Rebalance();


        }

        private void Rebalance()
        {
            RedBlackTreeNode<T> node = Root;
            Stack<RedBlackTreeNode<T>> stack = new Stack<RedBlackTreeNode<T>>();
            while (stack.Count !=0 || node !=null )
            {
                if (node != null)
                {
                    stack.Push(node);
                    node = node.Left;
                }
                else
                {
                    node = stack.Pop();
                    Rebalance(node);
                    node = node.Right;
                }


            }

        }

        private void Rebalance(RedBlackTreeNode<T> node)
        {
            if (node.Parent == null) return;

            if (node.Parent.Color == NodeColor.Red) //rule 2 or 3
            {
                if (node.Uncle != null) //the rule 2 - change him to black as well
                {
                    Rule2(node);
                }
                else //if my uncle doesn't exist, it's could be rule 3 or 4, which requires rotation
                {
                    //if my parent and I are on the same side, 
                    if (node.WhichSideAmIOn() == node.Parent.WhichSideAmIOn())
                    {
                        Rule3(node);
                    }
                    else
                    {
                        Rule4(node);
                    }
                }
            }



        }

        private void Rule2(RedBlackTreeNode<T> node)
        {
            //my parent + uncle needs to be black
            if (node.Parent == null) throw new Exception("um how?");
            node.Parent.Color = NodeColor.Black;
            node.Uncle.Color = NodeColor.Black;
        }

        //The rule of two red nodes to the same side
        //if the nodes of the tree are stacked in one direction and the two stacked nodes are red
        //the middle node comes up to the parent and the top node becomes the left or right hand child.
        private void Rule3(RedBlackTreeNode<T> node)
        { 
            //make my grand parent, my parents left|right
            //where am i?
            NodeSide ns = node.WhichSideAmIOn();

            if (node.Parent == null) throw new Exception("um how?");

            RedBlackTreeNode<T> parent = node.Parent;
            RedBlackTreeNode<T> grandParent = parent.Parent;
            RedBlackTreeNode<T> greatGrandParent = grandParent.Parent;

            //set my great, grand parent, to point at my parent
            NodeSide gpSide = grandParent.WhichSideAmIOn();
            if (gpSide == NodeSide.Left)
            {
                if (greatGrandParent !=null)
                    greatGrandParent.Left = parent;
            }
            else
            {
                if (greatGrandParent != null)
                    greatGrandParent.Right = parent;
            }

            //swap my grandparent into my parent's other child
            if (ns == NodeSide.Left)
            {
                //set my parents right to my grandParent
                parent.Right = grandParent;
                grandParent.Left = null;                             
            }
            else if (ns == NodeSide.Right)
            {
                //set my parents right to my grandParent
                parent.Left = grandParent;
                grandParent.Right = null;

            }

            //reset the parent, update the root
            parent.Parent = greatGrandParent;
            if (greatGrandParent == null)
            {
                Root = parent;
            }



            grandParent.Parent = parent;

            //swap colors
            parent.Color = NodeColor.Black;

            grandParent.Color = NodeColor.Red;


        }

        //The rule of two red nodes on different sides
        //if the nodes of a tree are both red and one goes to the left, but the other goes to the right
        //then the middle node becomes the parent and the top node becomes the left or right child
        private void Rule4(RedBlackTreeNode<T> node)
        {

            if (node.Parent == null) throw new Exception("um how?");

            RedBlackTreeNode<T> parent = node.Parent;
            RedBlackTreeNode<T> grandParent = parent.Parent;
            RedBlackTreeNode<T> greatGrandParent = grandParent.Parent;            

            //fix the reference that will be above me
            NodeSide ns;
            if (grandParent!= null)
            {
                ns = grandParent.WhichSideAmIOn();

                //replace the reference to my grand parent with me
                if (ns == NodeSide.Left)
                {
                    greatGrandParent.Left = node;
                }
                else if (ns == NodeSide.Right)
                {
                    greatGrandParent.Right = node;
                }                
            }


            //put my parent and my grand parent on the
            //correct side of me.
            ns = node.WhichSideAmIOn();
            NodeSide parentSide = parent.WhichSideAmIOn();
            if (ns == NodeSide.Left)
            {
                node.Left = grandParent;
                node.Right = parent;

                //I was the child of parent, wipe this refernce
                parent.Left = null;                                
            }
            else
            {
                node.Left = parent;
                node.Right = grandParent;

                //i was the child of parent, wipe this reference
                parent.Right = null;                
            }

            parent.Parent = node;
            grandParent.Parent = node;

            //parent was the child of grandparent, wipe this reference
            if (parentSide == NodeSide.Left) { grandParent.Left = null; }
            if (parentSide == NodeSide.Right) { grandParent.Right = null; }


            //reset my parent and root
            node.Parent = greatGrandParent;
            if (greatGrandParent == null)
            {
                Root = node;
            }

            //swap colors
            node.Color = NodeColor.Black;
            grandParent.Color = NodeColor.Red;
        }

        public void Print()
        {
            Stack<RedBlackTreeNode<T>> stack = new Stack<RedBlackTreeNode<T>>();
            RedBlackTreeNode<T> temp = Root;

            while (stack.Count != 0 || temp != null)
            {
                if (temp != null)
                {
                    stack.Push(temp);                    
                    temp = temp.Left;
                }
                else
                {                    
                    temp = stack.Pop();
                    Console.WriteLine(temp.Data.ToString());                    
                    temp = temp.Right;
                }

            }
        }

        public double Height 
        { 
            get
            {
                Stack<RedBlackTreeNode<T>> stack = new Stack<RedBlackTreeNode<T>>();
                RedBlackTreeNode<T> temp = Root;

                double currentHeight =0;
                while (stack.Count != 0 || temp != null)
                {
                    if (temp != null)
                    {
                        stack.Push(temp);
                        if (temp.Left != null || temp.Right != null)
                        {
                            currentHeight++;
                        }

                        temp = temp.Left;
                    }
                    else
                    {
                        temp = stack.Pop();
                        temp = temp.Right;
                    }

                }
                return currentHeight;
            }
        }

    }

    class Program
    {
        static void Main(string[] args)
        {
            RedBlackTree<int> rbt = new RedBlackTree<int>();
            rbt.InsertNode(1);
            rbt.InsertNode(2);
            rbt.InsertNode(3);
            rbt.InsertNode(4);
            rbt.InsertNode(5);
            rbt.InsertNode(6);
            rbt.InsertNode(7);
            rbt.InsertNode(8);
            rbt.InsertNode(9);
            rbt.InsertNode(10);
            rbt.Print();
            Assert.AreEqual(5, rbt.Height); //make sure sorted vals don't snake off to the left or right

            //inert 500 more random numbers, height should remain balanced
            Random random = new Random();

            for (int i = 0; i < 500; i++)
            { 
                rbt.InsertNode(random.Next(0, 10000)); 
            }

            Assert.AreEqual(255, rbt.Height);

        }
    }
}

Answer 1

Я думаю, что ваш тест неправильный, хотя я думаю, что у вашего кода есть другие проблемы, которые тест не улавливает.

Прежде всего, свойство Height на самом деле не возвращает высоту, а количество узлов с хотя бы одним дочерним элементом. Если вы хотите высоту самого глубокого узла, вы должны вместо этого делать что-то вроде currentHeight = Math.Max(currentHeight, stack.Count) на каждой итерации. Вы также можете захотеть вернуть int вместо double.

Количество узлов без потомков должно быть приблизительно половина из них, как вы хотите, но красно-черные деревья не идеально сбалансированы. У вас может быть правильное дерево, у одной трети узлов которого есть один дочерний элемент, у одной трети - два, а у одной трети нет ни одного: начните с идеально сбалансированного дерева со всеми черными узлами на последнем уровне и добавьте красный дочерний элемент к каждому. Это поддерживает инварианты красно-черного дерева, но у двух третей узлов будут дочерние элементы.

Точно так же, если бы вы проверяли глубину, она была бы между log(N) и 2 log(N).

Возможно, вы захотите написать тесты, которые напрямую проверяют инварианты дерева. Посетите каждый узел в дереве и убедитесь, что у каждого красного узла есть черный родитель и что каждый путь к листу содержит одинаковое количество черных узлов. Если вы запускаете эти тесты после каждой вставки в вашем наборе тестов, вы можете быть уверены, что дерево всегда сбалансировано.

Что касается самого кода, ваш метод Rebalance сканирует все дерево при каждой вставке. Это означает, что вставка потребует O(N) времени и сведет на нет преимущества использования самобалансирующегося дерева. Получение по-прежнему будет O(log N), но вы можете получить тот же результат, сохранив отсортированный список и вставив элементы в соответствующее место. Вам нужно только перебалансировать дерево вдоль вставляемого пути, который будет состоять только из O(log N) узлов.

Я думаю, что некоторые из ваших преобразований неверны. Вы не проверяете цвет текущего узла перед вызовом Rule2, и это правило, по-видимому, меняет узлы на черный, не гарантируя, что другие пути в дереве имеют такое же количество черных узлов. (Возможно, я неправильно читаю; красно-черные деревья слишком сложны, чтобы делать их целиком в моей голове.)

Если вы ищете эталонную реализацию, на странице Википедии Красно-черные деревья есть реализация на C, которую можно легко перевести на C #, и SortedSet<T> реализован с использованием красно-черного дерева, которое вы можете просмотреть с помощью Reflector.