Является ли эта реализация 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, и это правило отображает изменение узлов на черный, не гарантируя, что другие пути в дереве имеют одинаковое количество черных узлов. (Я, возможно, неправильно понимаю, красно-черные деревья слишком сложны, чтобы делать это полностью в моей голове.)

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