Existe-t-il une structure de données .NET avec les caractéristiques suivantes d'un arbre de recherche binaire?

Question

Je sais que SortedDictionary est un arbre de recherche binaire (et il peut presque faire ce que je dois faire!) Mais je ne peux pas comprendre comment faire tout ce dont j'ai besoin dans la bonne complexité.

Voici donc les contraintes (et la structure de données que je connais l'a)

1. Insertion et suppression dans O(log n)(SortedDictionary)
2. Rechercher dans O(log n)(SortedDictionary & SortedList)
3. Itération d'un élément recherché à un autre dans O(log n) + O(m) (où m est le nombre d'éléments entre les deux) (SortedList)

Comme vous pouvez le voir, je ne sais pas comment faire SortedDictionary numéro 3. En fait ce que je dois faire est d'obtenir tous les éléments avec une gamme sans itération de l'ensemble.

Dites-moi si ma question n'est pas claire.

Answer 1

Cela semble décrire un arbre B + parfaitement: http://en.wikipedia.org/wiki/B%2B_tree:

• insertion d'un enregistrement nécessite des opérations O (log (n)) dans le pire des cas
• Trouver un enregistrement nécessite O (log (n) Opérations dans le pire des cas
• L'exécution d'un range query avec k éléments se produisant dans la plage nécessite des opérations O (log (n) + k) dans le pire des cas.

mise en œuvre AC# semble exister ici: http://bplusdotnet.sourceforge.net/

Answer 2

Je ne pense pas qu'il existe une collection dans le framework qui fasse ce que vous décrivez, bien que je puisse me tromper.

Ce que vous cherchez est une liste liée qui est indexée avec un arbre binaire. Cela vous permet d'insérer, de supprimer et de rechercher à l'aide de l'arborescence binaire
O(log n) traversée O(m) en utilisant la liste chaînée
. Vous pouvez jeter un oeil à la C5 Generic Collections Library. Bien qu'il ne semble pas y avoir de collection correspondant à votre description, vous pourrez peut-être marier leurs objets TreeSet<T> et LinkedList<T>, créant ainsi un nouvel objet SortedLinkedList<T>.

Answer 3

Check out System.Collections.ObjectModel.KeyedCollection<TKey, TItem> - il pourrait ne pas répondre à vos besoins, mais il semble comme un bon ajustement, car il fournit un dictionnaire de recherche interne qui permet O (1) récupération d'éléments par index et approche O (1) par clé. L'inconvénient est qu'il est prévu pour stocker des objets où la clé est définie comme une propriété sur l'objet, donc à moins que vous pouvez écraser vos données d'entrée pour s'adapter, il ne sera pas approprié.

Je voudrais inclure plus d'informations sur les données que vous avez l'intention de stocker et le volume, car cela pourrait aider à fournir des alternatives.

Answer 4

Certaines des suggestions étaient assez bonnes, mais j'ai décidé d'implémenter la collection moi-même (cela semblait amusant). J'ai commencé avec la mise en œuvre .NET de SortedDictionary, et fortement modifié pour faire ce que j'avais besoin de faire

Juste pour que d'autres personnes peuvent profiter de mon travail, voici la classe:

internal delegate void TreeWalkAction<Key, Value>(BinaryTreeSearch<Key, Value>.Node node); 
internal delegate bool TreeWalkTerminationPredicate<Key, Value>(BinaryTreeSearch<Key, Value>.Node node); 
internal class BinaryTreeSearch<Key, Value> 
{ 
    // Fields 
    private IComparer<Key> comparer; 
    private int count; 
    private Node root; 
    private int version; 

    // Methods 
    public BinaryTreeSearch(IComparer<Key> comparer) 
    { 
     if (comparer == null) 
     { 
      this.comparer = Comparer<Key>.Default; 
     } 
     else 
     { 
      this.comparer = comparer; 
     } 
    } 

    private Node First 
    { 
     get 
     { 
      if (root == null) return null; 
      Node n = root; 
      while (n.Left != null) 
      { 
       n = n.Left; 
      } 
      return n; 
     } 
    } 

    public Key Min 
    { 
     get 
     { 
      Node first = First; 
      return first == null ? default(Key) : first.Key; 
     } 
    } 

    public Key Max 
    { 
     get 
     { 
      if (root == null) return default(Key); 
      Node n = root; 
      while (n.Right != null) 
      { 
       n = n.Right; 
      } 
      return n.Key; 
     } 
    } 

    public List<Value> this[Key key] 
    { 
     get 
     { 
      Node n = FindNode(key); 
      return n == null ? new List<Value>() : n.Values; 
     } 
    } 

    public List<Value> GetRange(Key start, Key end) 
    { 
     Node node = FindNextNode(start); 
     List<Value> ret = new List<Value>(); 
     InOrderTreeWalk(node, 
      aNode => ret.AddRange(aNode.Values), 
      aNode => comparer.Compare(end, aNode.Key) < 0); 
     return ret; 
    } 

    public void Add(Key key, Value value) 
    { 
     if (this.root == null) 
     { 
      this.root = new Node(null, key, value, false); 
      this.count = 1; 
     } 
     else 
     { 
      Node root = this.root; 
      Node node = null; 
      Node grandParent = null; 
      Node greatGrandParent = null; 
      int num = 0; 
      while (root != null) 
      { 
       num = this.comparer.Compare(key, root.Key); 
       if (num == 0) 
       { 
        root.Values.Add(value); 
        count++; 
        return; 
       } 
       if (Is4Node(root)) 
       { 
        Split4Node(root); 
        if (IsRed(node)) 
        { 
         this.InsertionBalance(root, ref node, grandParent, greatGrandParent); 
        } 
       } 
       greatGrandParent = grandParent; 
       grandParent = node; 
       node = root; 
       root = (num < 0) ? root.Left : root.Right; 
      } 
      Node current = new Node(node, key, value); 
      if (num > 0) 
      { 
       node.Right = current; 
      } 
      else 
      { 
       node.Left = current; 
      } 
      if (node.IsRed) 
      { 
       this.InsertionBalance(current, ref node, grandParent, greatGrandParent); 
      } 
      this.root.IsRed = false; 
      this.count++; 
      this.version++; 
     } 
    } 

    public void Clear() 
    { 
     this.root = null; 
     this.count = 0; 
     this.version++; 
    } 

    public bool Contains(Key key) 
    { 
     return (this.FindNode(key) != null); 
    } 

    internal Node FindNode(Key item) 
    { 
     int num; 
     for (Node node = this.root; node != null; node = (num < 0) ? node.Left : node.Right) 
     { 
      num = this.comparer.Compare(item, node.Key); 
      if (num == 0) 
      { 
       return node; 
      } 
     } 
     return null; 
    } 

    internal Node FindNextNode(Key key) 
    { 
     int num; 
     Node node = root; 
     while (true) 
     { 
      num = comparer.Compare(key, node.Key); 
      if (num == 0) 
      { 
       return node; 
      } 
      else if (num < 0) 
      { 
       if (node.Left == null) return node; 
       node = node.Left; 
      } 
      else 
      { 
       node = node.Right; 
      } 
     } 
    } 

    private static Node GetSibling(Node node, Node parent) 
    { 
     if (parent.Left == node) 
     { 
      return parent.Right; 
     } 
     return parent.Left; 
    } 

    internal void InOrderTreeWalk(Node start, TreeWalkAction<Key, Value> action, TreeWalkTerminationPredicate<Key, Value> terminationPredicate) 
    { 
     Node node = start; 
     while (node != null && !terminationPredicate(node)) 
     { 
      action(node); 
      node = node.Next; 
     } 
    } 


    private void InsertionBalance(Node current, ref Node parent, Node grandParent, Node greatGrandParent) 
    { 
     Node node; 
     bool flag = grandParent.Right == parent; 
     bool flag2 = parent.Right == current; 
     if (flag == flag2) 
     { 
      node = flag2 ? RotateLeft(grandParent) : RotateRight(grandParent); 
     } 
     else 
     { 
      node = flag2 ? RotateLeftRight(grandParent) : RotateRightLeft(grandParent); 
      parent = greatGrandParent; 
     } 
     grandParent.IsRed = true; 
     node.IsRed = false; 
     this.ReplaceChildOfNodeOrRoot(greatGrandParent, grandParent, node); 
    } 

    private static bool Is2Node(Node node) 
    { 
     return ((IsBlack(node) && IsNullOrBlack(node.Left)) && IsNullOrBlack(node.Right)); 
    } 

    private static bool Is4Node(Node node) 
    { 
     return (IsRed(node.Left) && IsRed(node.Right)); 
    } 

    private static bool IsBlack(Node node) 
    { 
     return ((node != null) && !node.IsRed); 
    } 

    private static bool IsNullOrBlack(Node node) 
    { 
     if (node != null) 
     { 
      return !node.IsRed; 
     } 
     return true; 
    } 

    private static bool IsRed(Node node) 
    { 
     return ((node != null) && node.IsRed); 
    } 

    private static void Merge2Nodes(Node parent, Node child1, Node child2) 
    { 
     parent.IsRed = false; 
     child1.IsRed = true; 
     child2.IsRed = true; 
    } 

    public bool Remove(Key key, Value value) 
    { 
     if (this.root == null) 
     { 
      return false; 
     } 
     Node root = this.root; 
     Node parent = null; 
     Node node3 = null; 
     Node match = null; 
     Node parentOfMatch = null; 
     bool flag = false; 
     while (root != null) 
     { 
      if (Is2Node(root)) 
      { 
       if (parent == null) 
       { 
        root.IsRed = true; 
       } 
       else 
       { 
        Node sibling = GetSibling(root, parent); 
        if (sibling.IsRed) 
        { 
         if (parent.Right == sibling) 
         { 
          RotateLeft(parent); 
         } 
         else 
         { 
          RotateRight(parent); 
         } 
         parent.IsRed = true; 
         sibling.IsRed = false; 
         this.ReplaceChildOfNodeOrRoot(node3, parent, sibling); 
         node3 = sibling; 
         if (parent == match) 
         { 
          parentOfMatch = sibling; 
         } 
         sibling = (parent.Left == root) ? parent.Right : parent.Left; 
        } 
        if (Is2Node(sibling)) 
        { 
         Merge2Nodes(parent, root, sibling); 
        } 
        else 
        { 
         TreeRotation rotation = RotationNeeded(parent, root, sibling); 
         Node newChild = null; 
         switch (rotation) 
         { 
          case TreeRotation.LeftRotation: 
           sibling.Right.IsRed = false; 
           newChild = RotateLeft(parent); 
           break; 

          case TreeRotation.RightRotation: 
           sibling.Left.IsRed = false; 
           newChild = RotateRight(parent); 
           break; 

          case TreeRotation.RightLeftRotation: 
           newChild = RotateRightLeft(parent); 
           break; 

          case TreeRotation.LeftRightRotation: 
           newChild = RotateLeftRight(parent); 
           break; 
         } 
         newChild.IsRed = parent.IsRed; 
         parent.IsRed = false; 
         root.IsRed = true; 
         this.ReplaceChildOfNodeOrRoot(node3, parent, newChild); 
         if (parent == match) 
         { 
          parentOfMatch = newChild; 
         } 
         node3 = newChild; 
        } 
       } 
      } 
      int num = flag ? -1 : this.comparer.Compare(key, root.Key); 
      if (num == 0) 
      { 
       flag = true; 
       match = root; 
       parentOfMatch = parent; 
      } 
      node3 = parent; 
      parent = root; 
      if (num < 0) 
      { 
       root = root.Left; 
      } 
      else 
      { 
       root = root.Right; 
      } 
     } 
     if (match != null) 
     { 
      if (match.Values.Remove(value)) 
      { 
       this.count--; 
      } 
      if (match.Values.Count == 0) 
      { 
       this.ReplaceNode(match, parentOfMatch, parent, node3); 
      } 

     } 
     if (this.root != null) 
     { 
      this.root.IsRed = false; 
     } 
     this.version++; 
     return flag; 
    } 

    private void ReplaceChildOfNodeOrRoot(Node parent, Node child, Node newChild) 
    { 
     if (parent != null) 
     { 
      if (parent.Left == child) 
      { 
       parent.Left = newChild; 
      } 
      else 
      { 
       parent.Right = newChild; 
      } 
      if (newChild != null) newChild.Parent = parent; 
     } 
     else 
     { 
      this.root = newChild; 
     } 
    } 

    private void ReplaceNode(Node match, Node parentOfMatch, Node succesor, Node parentOfSuccesor) 
    { 
     if (succesor == match) 
     { 
      succesor = match.Left; 
     } 
     else 
     { 
      if (succesor.Right != null) 
      { 
       succesor.Right.IsRed = false; 
      } 
      if (parentOfSuccesor != match) 
      { 
       parentOfSuccesor.Left = succesor.Right; if (succesor.Right != null) succesor.Right.Parent = parentOfSuccesor; 
       succesor.Right = match.Right; if (match.Right != null) match.Right.Parent = succesor; 
      } 
      succesor.Left = match.Left; if (match.Left != null) match.Left.Parent = succesor; 
     } 
     if (succesor != null) 
     { 
      succesor.IsRed = match.IsRed; 
     } 
     this.ReplaceChildOfNodeOrRoot(parentOfMatch, match, succesor); 
    } 

    private static Node RotateLeft(Node node) 
    { 
     Node right = node.Right; 
     node.Right = right.Left; if (right.Left != null) right.Left.Parent = node; 
     right.Left = node; if (node != null) node.Parent = right; 
     return right; 
    } 

    private static Node RotateLeftRight(Node node) 
    { 
     Node left = node.Left; 
     Node right = left.Right; 
     node.Left = right.Right; if (right.Right != null) right.Right.Parent = node; 
     right.Right = node; if (node != null) node.Parent = right; 
     left.Right = right.Left; if (right.Left != null) right.Left.Parent = left; 
     right.Left = left; if (left != null) left.Parent = right; 
     return right; 
    } 

    private static Node RotateRight(Node node) 
    { 
     Node left = node.Left; 
     node.Left = left.Right; if (left.Right != null) left.Right.Parent = node; 
     left.Right = node; if (node != null) node.Parent = left; 
     return left; 
    } 

    private static Node RotateRightLeft(Node node) 
    { 
     Node right = node.Right; 
     Node left = right.Left; 
     node.Right = left.Left; if (left.Left != null) left.Left.Parent = node; 
     left.Left = node; if (node != null) node.Parent = left; 
     right.Left = left.Right; if (left.Right != null) left.Right.Parent = right; 
     left.Right = right; if (right != null) right.Parent = left; 
     return left; 
    } 

    private static TreeRotation RotationNeeded(Node parent, Node current, Node sibling) 
    { 
     if (IsRed(sibling.Left)) 
     { 
      if (parent.Left == current) 
      { 
       return TreeRotation.RightLeftRotation; 
      } 
      return TreeRotation.RightRotation; 
     } 
     if (parent.Left == current) 
     { 
      return TreeRotation.LeftRotation; 
     } 
     return TreeRotation.LeftRightRotation; 
    } 

    private static void Split4Node(Node node) 
    { 
     node.IsRed = true; 
     node.Left.IsRed = false; 
     node.Right.IsRed = false; 
    } 

    // Properties 
    public IComparer<Key> Comparer 
    { 
     get 
     { 
      return this.comparer; 
     } 
    } 

    public int Count 
    { 
     get 
     { 
      return this.count; 
     } 
    } 

    internal class Node 
    { 
     // Fields 
     private bool isRed; 
     private Node left, right, parent; 
     private Key key; 
     private List<Value> values; 

     // Methods 
     public Node(Node parent, Key item, Value value) : this(parent, item, value, true) 
     { 
     } 

     public Node(Node parent, Key key, Value value, bool isRed) 
     { 
      this.key = key; 
      this.parent = parent; 
      this.values = new List<Value>(new Value[] { value }); 
      this.isRed = isRed; 
     } 

     // Properties 
     public bool IsRed 
     { 
      get 
      { 
       return this.isRed; 
      } 
      set 
      { 
       this.isRed = value; 
      } 
     } 

     public Key Key 
     { 
      get 
      { 
       return this.key; 
      } 
      set 
      { 
       this.key = value; 
      } 
     } 

     public List<Value> Values { get { return values; } } 

     public Node Left 
     { 
      get 
      { 
       return this.left; 
      } 
      set 
      { 
       this.left = value; 
      } 
     } 

     public Node Right 
     { 
      get 
      { 
       return this.right; 
      } 
      set 
      { 
       this.right = value; 
      } 
     } 

     public Node Parent 
     { 
      get 
      { 
       return this.parent; 
      } 
      set 
      { 
       this.parent = value; 
      } 
     } 

     public Node Next 
     { 
      get 
      { 
       if (right == null) 
       { 
        if (parent == null) 
        { 
         return null; // this puppy must be lonely 
        } 
        else if (parent.Left == this) // this is a left child 
        { 
         return parent; 
        } 
        else 
        { 
         //this is a right child, we need to go up the tree 
         //until we find a left child. Then the parent will be the next 
         Node n = this; 
         do 
         { 
          n = n.parent; 
          if (n.parent == null) 
          { 
           return null; // this must have been a node along the right edge of the tree 
          } 
         } while (n.parent.right == n); 
         return n.parent; 
        } 
       } 
       else // there is a right child. 
       { 
        Node go = right; 
        while (go.left != null) 
        { 
         go = go.left; 
        } 
        return go; 
       } 
      } 
     } 

     public override string ToString() 
     { 
      return key.ToString() + " - [" + string.Join(", ", new List<string>(values.Select<Value, string>(o => o.ToString())).ToArray()) + "]"; 
     } 
    } 
    internal enum TreeRotation 
    { 
     LeftRightRotation = 4, 
     LeftRotation = 1, 
     RightLeftRotation = 3, 
     RightRotation = 2 
    } 
} 

et test unitaire rapide (qui ne couvre en fait tout le code, donc il pourrait y avoir encore quelques bugs):

[TestFixture] 
public class BTSTest 
{ 
    private class iC : IComparer<int>{public int Compare(int x, int y){return x.CompareTo(y);}} 

    [Test] 
    public void Test() 
    { 
     BinaryTreeSearch<int, int> bts = new BinaryTreeSearch<int, int>(new iC()); 
     bts.Add(5, 1); 
     bts.Add(5, 2); 
     bts.Add(6, 2); 
     bts.Add(2, 3); 
     bts.Add(8, 2); 
     bts.Add(10, 11); 
     bts.Add(9, 4); 
     bts.Add(3, 32); 
     bts.Add(12, 32); 
     bts.Add(8, 32); 
     bts.Add(9, 32); 

     Assert.AreEqual(11, bts.Count); 
     Assert.AreEqual(2, bts.Min); 
     Assert.AreEqual(12, bts.Max); 

     List<int> val = bts[5]; 
     Assert.AreEqual(2, val.Count); 
     Assert.IsTrue(val.Contains(1)); 
     Assert.IsTrue(val.Contains(2)); 

     val = bts[6]; 
     Assert.AreEqual(1, val.Count); 
     Assert.IsTrue(val.Contains(2)); 

     Assert.IsTrue(bts.Contains(5)); 
     Assert.IsFalse(bts.Contains(-1)); 

     val = bts.GetRange(5, 8); 

     Assert.AreEqual(5, val.Count); 
     Assert.IsTrue(val.Contains(1)); 
     Assert.IsTrue(val.Contains(32)); 
     Assert.AreEqual(3, val.Count<int>(num => num == 2)); 

     bts.Remove(8, 32); 
     bts.Remove(5, 2); 

     Assert.AreEqual(9, bts.Count); 
     val = bts.GetRange(5, 8); 
     Assert.AreEqual(3, val.Count); 
     Assert.IsTrue(val.Contains(1)); 
     Assert.AreEqual(2, val.Count<int>(num => num == 2)); 

     bts.Remove(2, 3); 
     Assert.IsNull(bts.FindNode(2)); 

     bts.Remove(12, 32); 
     Assert.IsNull(bts.FindNode(12)); 
     Assert.AreEqual(3, bts.Min); 
     Assert.AreEqual(10, bts.Max); 

     bts.Remove(9, 4); 
     bts.Remove(5, 1); 
     bts.Remove(6, 2); 
    } 
}