Is there a .NET data structure with the following characteristics of a Binary Search Tree?

Question

I know that SortedDictionary is a binary search tree (and it can almost do what I need to do!) but I can't figure out how to do everything I need in the correct complexity.

So here are the constraints (and the data structure which I know has it)

1. Inserting and Deletion in O(log n) (SortedDictionary)
2. Search in O(log n) (SortedDictionary & SortedList)
3. Iteration from one searched element to another in O(log n) + O(m) (where m is the number of elements in between) (SortedList)

As you can see, I don't know how to get SortedDictionary to do number 3. Basically what I need to do is get all the elements with a range without iterating the set.

Please tell me if my question isn't clear.

Answer 1

I don't think there is a collection in the framework that does what you describe, although I could be wrong.

What you are looking for is a linked list that is indexed with a binary tree. This would provide you
O(log n) insertion, deletion and search using the binary tree, with O(m) traversal using the
linked list.

You might want to have a look at the C5 Generic Collections Library. Although there doesn't appear to be a collection that fits your description there, you might be able to marry together their TreeSet<T> and LinkedList<T> objects, creating a new SortedLinkedList<T> object.

Answer 2

This seems to describe a B+ tree perfectly: http://en.wikipedia.org/wiki/B%2B_tree :

• Inserting a record requires O(log(n)) operations in the worst case
• Finding a record requires O(log(n)) operations in the worst case
• Performing a range query with k elements occurring within the range requires O(log(n) + k) operations in the worst case.

A C# implementation seems to exist here: http://bplusdotnet.sourceforge.net/

Answer 3

Check out System.Collections.ObjectModel.KeyedCollection<TKey, TItem> - it might not suit your requirements but it seems like a good fit, as it provides an internal lookup dictionary that enables O(1) retrieval of items by index and approaching O(1) by key.

The caveat is that it is intended to store objects where the key is defined as a property on the object, so unless you can mash your input data to fit, it won't be appropriate.

I would include some more information on what data you are intending to store and the volume, as this might help provide alternatives.

Answer 4

Some of the suggestions were pretty good, but I decided to implement the collection myself (it sounded fun). I started with the .NET implementation of SortedDictionary, and heavily modified it to do what I needed it to do

Just so other people can benefit from my work, here is the class:

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

and a quick unit test (which doesn't actually cover all the code, so there might still be some 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);
    }
}