AVL Tree Implementation in C#

Question

I'm new to C# so any input would be very helpful. The implementation is about as lazy as you can get and still be log n; it's more about learning how this kind of thing is done properly in C#.

using System;
using System.Collections;
using System.Collections.Generic;
using System.Runtime.Serialization;
using System.Security.Permissions;

namespace Trees
{
    [Serializable()]
    public class Array_AVL<T> : IEnumerable<T>, IEnumerable, ISerializable, IDeserializationCallback where T : IComparable
    {
        public sealed class Node : IEnumerable<T>
        {
            internal Array_AVL<T> parentArray;
            internal T Data;
            internal Node Left = null, Right = null, Parent = null;
            internal int Weight = 0;
            internal int Height = 0;
            private Node(T data) { this.Data = data; }
            internal Node(Array_AVL<T> List, T data, Node parent = null, int weight = 1, sbyte height = 0)
            { this.parentArray = List; this.Data = data; this.Parent = parent; this.Weight = weight; this.Height = height; }

            internal int ComputeHeight() { return Math.Max((Left == null ? 0 : Left.Height), (Right == null ? 0 : Right.Height)) + 1; }
            internal int ComputeBalance { get { return (Right == null ? 0 : Right.Height) - (Left == null ? 0 : Left.Height); } }
            internal int ComputeWeight() { return (Left == null ? 0 : Left.Weight) + (Right == null ? 0 : Right.Weight) + 1; }
            public Node Next() { return parentArray == null ? GetNext() : parentArray.reverse ? GetPrevious() : GetNext(); }
            public Node Previous() { return parentArray == null ? GetPrevious() : parentArray.reverse ? GetNext() : GetPrevious(); }

            internal void SetParentEdge(Node node)
            {
                if (Parent != null)
                {
                    if (Parent.Right == this)
                        Parent.Right = node;
                    else
                        Parent.Left = node;
                }

                if (node != null)
                {
                    node.Parent = this.Parent;
                    this.Parent = node;
                }
            }

            private Node GetNext()
            {
                Node node = this;
                if (node.Right != null)
                    node = GetFirstNode(node.Right);
                else
                    node = GetNextTopParent(node).Parent;
                return node;
            }

            private Node GetPrevious()
            {
                Node node = this;
                if (node.Left != null)
                    node = GetLastNode(node.Left);
                else
                    node = GetPreviousTopParent(node).Parent;
                return node;
            }

            private Func<Node, Node> GetPreviousTopParent = (node) =>
            {
                while (node.Parent != null && node.Parent.Left == node)
                    node = node.Parent;
                return node;
            };

            private Func<Node, Node> GetNextTopParent = (node) =>
            {
                while (node.Parent != null && node.Parent.Right == node)
                    node = node.Parent;
                return node;
            };

            private Func<Node, Node> GetFirstNode = (node) =>
            {
                while (node.Left != null)
                    node = node.Left;
                return node;
            };

            private Func<Node, Node> GetLastNode = (node) =>
            {
                while (node.Right != null)
                    node = node.Right;
                return node;
            };

            public static implicit operator T(Node x) => (x == null) ? default(T) : x.Data;
            public static implicit operator Node(T x) => new Node(x);
            public static Node operator ++(Node n) => n?.Next();
            public static Node operator --(Node n) => n?.Previous();

            public IEnumerable<T> To(Node n2)
            {
                Node n1 = this;
                n2++;
                while (n1 != null && n1 != n2)
                    yield return n1++;
            }
            public IEnumerator<T> GetEnumerator(Node n)
            {
                while (n != null)
                    yield return n++;
            }
            public IEnumerator<T> GetEnumerator() => GetEnumerator(this);
            IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
        } // END Node

        private SerializationInfo siInfo = null; //Temp variable for deserialization.
        private bool reverse = false;
        private int count = 0;
        public Node head;
        public Array_AVL() { }
        protected Array_AVL(SerializationInfo info, StreamingContext context) { siInfo = info; }

        public int Count { get { return count; } set { count = value; } }
        public bool Reverse { get { return reverse; } set { reverse = value; } }

        public Node this[int i]
        {
            get { return GetNodeAtIndex(i); }
            set
            {
                Delete(GetNodeAtIndex(i));
                if (value != null)
                    Add(value);
            }
        }

        [SecurityPermissionAttribute(SecurityAction.LinkDemand, Flags = SecurityPermissionFlag.SerializationFormatter)]
        public virtual void GetObjectData(SerializationInfo info, StreamingContext context)
        {
            if (info == null)
                throw new ArgumentNullException("Null info");
            info.AddValue("Count", count);
            info.AddValue("Reverse", reverse);
            if (count != 0)
            {
                bool tmp = reverse;
                reverse = false;
                T[] array = new T[Count];
                array = this.ToArray();
                info.AddValue("Data", array, typeof(T[]));
                reverse = tmp;
            }
        }

        public virtual void OnDeserialization(Object sender)
        {  //Somebody had a dependency on this and fixed us up before the ObjectManager got to it.
            if (siInfo == null)
                return;
            if ((count = siInfo.GetInt32("Count")) == 0)
                head = null;
            else
            {
                reverse = siInfo.GetBoolean("Reverse");
                T[] array = (T[])siInfo.GetValue("Data", typeof(T[]));
                if (array == null)
                    throw new SerializationException("Serialization Missing Values");
                FromSortedArray(array);
            }
            siInfo = null;
        }

        public Node GetNodeAtIndex(int index)
        {
            if ((uint)index >= (uint)count)
                throw new IndexOutOfRangeException();

            if (reverse)
                index = (count - 1) - index;

            Node n = head;
            int curWeight = ((n.Left == null) ? 0 : n.Left.Weight);
            while (index != curWeight)
            {
                if (curWeight < index)
                {
                    n = n.Right;
                    curWeight += ((n.Left == null) ? 0 : n.Left.Weight) + 1;
                }
                else
                {
                    n = n.Left;
                    curWeight -= ((n.Right == null) ? 0 : n.Right.Weight) + 1;
                }
            }
            return n;
        }

        private Node Find(T data, Node node)
        {
            if (node == null)
                return node;
            else if (data.CompareTo(node.Data) == 0)
                return node;
            else if (data.CompareTo(node.Data) < 0)
                return Find(data, node.Left);
            else
                return Find(data, node.Right);
        }
        private Node Find(T data) => Find(data, head);
        public Node FindFirst(T data) => Find(data, head);
        public bool Remove(T data) => Delete(Find(data, head));

        private bool Delete(Node node)
        {
            Node swapNode;

            if (node == null)
                return false;
            else if (node.parentArray != this)
                return false;
            else if (count == 1)
                head = null;
            else if (node.Weight == 1)
                node.SetParentEdge(null);
            else if (node.Left == null)
                node.SetParentEdge(node.Right);
            else if (node.Right == null)
                node.SetParentEdge(node.Left);
            else
            {
                swapNode = node.Next();
                Node swapParent = swapNode.Parent;
                swapNode.SetParentEdge(swapNode.Right);
                node.SetParentEdge(swapNode);

                swapNode.Left = node.Left;
                swapNode.Right = node.Right;
                swapNode.Left.Parent = swapNode;

                if (swapNode.Right != null)
                    swapNode.Right.Parent = swapNode;
                node = swapParent;
            }

            if (head.Parent != null)
                head = head.Parent;

            count--;
            Balance(node);
            return true;
        }

        private bool Insert(Node newNode)
        {
            if (newNode == null)
                return false;
            else if (head == null)
                head = newNode;
            else
            {
                Node node = head;
                while (newNode.Parent == null)
                {
                    node.Weight++;
                    if (newNode.Data.CompareTo(node.Data) < 0)
                    {
                        if (node.Left != null)
                            node = node.Left;
                        else
                        {
                            node.Left = newNode;
                            newNode.Parent = node;
                        }
                    }
                    else
                    {
                        if (node.Right != null)
                            node = node.Right;
                        else
                        {
                            node.Right = newNode;
                            newNode.Parent = node;
                        }
                    }
                }
            }

            Balance(newNode);
            return true;
        }

        void Rotate(Node node)
        {
            Node newHead;

            if (node.ComputeBalance > 0)
            {
                newHead = node.Right;
                node.Right = newHead.Left;
                if (node.Right != null)
                    node.Right.Parent = node;
                newHead.Left = node;
            }
            else
            {
                newHead = node.Left;
                node.Left = newHead.Right;
                if (node.Left != null)
                    node.Left.Parent = node;
                newHead.Right = node;
            }

            node.SetParentEdge(newHead);
            if (newHead.Parent == null)
                head = newHead;

            node.Height = node.ComputeHeight();
            newHead.Height = newHead.ComputeHeight();

            node.Weight = node.ComputeWeight();
            newHead.Weight = newHead.ComputeWeight();
        }

        void Balance(Node node)
        {
            while (node != null)
            {
                node.Height = node.ComputeHeight();
                node.Weight = node.ComputeWeight();

                if (node.ComputeBalance == 2)
                {
                    if (node.Right.ComputeBalance < 0)
                        Rotate(node.Right);
                    Rotate(node);
                }
                else if (node.ComputeBalance == -2)
                {
                    if (node.Left.ComputeBalance > 0)
                        Rotate(node.Left);
                    Rotate(node);
                }

                node = node.Parent;
            }
        }

        public bool Add(T data)
        {
            if (!Insert(new Node(this, data)))
                return false;
            count++;
            return true;
        }

        public void Clear() => Clear(ref head);

        private void Clear(ref Node node)
        {
            if (node == null)
                return;
            Clear(ref node.Left);
            Clear(ref node.Right);
            node = null;
            count--;
        }

        public T[] ToArray()
        {
            T[] nodes = new T[count];
            int i = 0;
            foreach (T node in this)
                nodes[i++] = node;
            return nodes;
        }

        private void FromArray(T[] array, ref Node node, Node parent, int l, int r)
        {
            int pivot = (l + r) >> 1;
            if (pivot == l)
                return;
            node = new Node(this, array[pivot], parent, r - l - 1);
            FromArray(array, ref node.Left, node, l, pivot);
            FromArray(array, ref node.Right, node, pivot, r);
            node.Height = node.ComputeHeight();
        }

        public void FromSortedArray(T[] array)
        {
            this.Clear();
            FromArray(array, ref head, null, -1, array.Length);
            this.count = array.Length;
        }

        public void FromArray(T[] array)
        {
            this.Clear();
            Array.Sort<T>(array);
            FromArray(array, ref head, null, -1, array.Length);
            this.count = array.Length;
        }

        public IEnumerator<T> GetEnumerator(Node node)
        {
            node = this[0];
            while (node != null)
                yield return node++;
        }

        public IEnumerator<T> GetEnumerator() => GetEnumerator(head);
        IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
    }
}

Simple test:

private static void Main(string[] args)
{
    Array_AVL<int> tree = new Array_AVL<int> { 24, 11, 46, 77, 65, 43, 35, 94, 10, 94, 64};

    tree.Remove(43);
    tree.Remove(35);
    Console.WriteLine("----------------------------------------------------------");
    foreach (int i in tree)
        Console.WriteLine(i);

    tree[3] = 123;
    Console.WriteLine("----------------------------------------------------------");
    Array_AVL<int>.Node n = tree[0];
    while (n != null)
        Console.WriteLine(n++);

    Console.WriteLine("----------------------------------------------------------");
    n = tree.FindFirst(94);
    while (n != null)
        Console.WriteLine(n++);

    tree[5] = null;
    tree.Reverse = true;
    Console.WriteLine("----------------------------------------------------------");
    for (int i = 0; i < tree.Count; i++)
        Console.WriteLine(tree[i]);

    Console.WriteLine("----------------------------------------------------------");
    foreach (var i in tree[4].To(tree[6]))
        Console.WriteLine(i);

    Console.ReadKey();
  }

Answer 1

This is quite a big first project, so I'm definitely going to leave some points for other people to raise. I've only looked at about half of the code.

---

    public class Array_AVL<T> : IEnumerable<T>, IEnumerable, ISerializable, IDeserializationCallback where T : IComparable

It's unnecessary to explicitly mention IEnumerable because IEnumerable<T> extends it.

Is there any reason for not making the constraint be where T : IComparable<T>?

---

        public sealed class Node : IEnumerable<T>

Why does this implement IEnumerable<T>? I can't see an abstract reason why this should be necessary, and if I comment out : IEnumerable<T> and the methods Node.GetEnumerator(Node) and Node.GetEnumerator() the code still compiles, including the sample use cases.

---

            internal int ComputeHeight() { return Math.Max((Left == null ? 0 : Left.Height), (Right == null ? 0 : Right.Height)) + 1; }
            internal int ComputeWeight() { return (Left == null ? 0 : Left.Weight) + (Right == null ? 0 : Right.Weight) + 1; }

These only appear to be used in direct assignments such as node.Height = node.ComputeHeight(). Why not inline the assignment as follows?

            internal void UpdateHeight() { Height = Math.Max((Left == null ? 0 : Left.Height), (Right == null ? 0 : Right.Height)) + 1; }
            internal void UpdateWeight() { Weight = (Left == null ? 0 : Left.Weight) + (Right == null ? 0 : Right.Weight) + 1; }

---

            internal int ComputeBalance { get { return (Right == null ? 0 : Right.Height) - (Left == null ? 0 : Left.Height); } }

IMO it would be more idiomatic to use a computed property:

            internal int Balance => (Right == null ? 0 : Right.Height) - (Left == null ? 0 : Left.Height);

---

            public Node Next() { return parentArray == null ? GetNext() : parentArray.reverse ? GetPrevious() : GetNext(); }
            public Node Previous() { return parentArray == null ? GetPrevious() : parentArray.reverse ? GetNext() : GetPrevious(); }

Two things:

1. Under what circumstances would parentArray == null? I suspect that this should be asserted false rather than handled as a special case.

2. parentArray.reverse? If the collection needs to handle multiple orders, perhaps you should forget all about IComparable/IComparable<T> and instead use IComparer<T> to define the ordering.

---

            internal void SetParentEdge(Node node)

I don't understand the name. From the implementation, this looks like SetParent.

---

            private Func<Node, Node> GetPreviousTopParent = (node) =>
            {
                while (node.Parent != null && node.Parent.Left == node)
                    node = node.Parent;
                return node;
            };

and the following Funcs in the same style are very weird style. They make me suspect that you've come from JavaScript. A simple refactor gives a normal method:

            private Node GetPreviousTopParent()
            {
                var node = this;
                while (node.Parent != null && node.Parent.Left == node)
                    node = node.Parent;
                return node;
            }

but since it's only used in one place and is pretty simple, I'd inline it.

---

            public static implicit operator T(Node x) => (x == null) ? default(T) : x.Data;
            public static implicit operator Node(T x) => new Node(x);

This is also rather weird. Firstly, why are these conversions useful? Secondly, the second one seems to be the only source of nodes which don't have parentArray correctly set, and hence a potential source of bugs.

It seems that the main value these conversions provide is for the external API, but IMO the better solution to making the external API work cleanly with T would be to make Node private and only expose an API which explicitly uses T.

---

        public IEnumerator<T> GetEnumerator(Node node)
        {
            node = this[0];
            while (node != null)
                yield return node++;
        }

        public IEnumerator<T> GetEnumerator() => GetEnumerator(head);

Huh? The first method ignores its argument, which is not an out-param but is overwritten without being read. The only caller is the second method. Why not just have this?

        public IEnumerator<T> GetEnumerator()
        {
            var node = GetNodeAtIndex(0);
            while (node != null)
                yield return node++;
        }

---

        private bool reverse = false;
        private int count = 0;
        ...
        public int Count { get { return count; } set { count = value; } }
        public bool Reverse { get { return reverse; } set { reverse = value; } }

C# has syntax sugar for this:

        public int Count { get; set; }
        public bool Reverse { get; set; }

(Although see my previous comment on eliminating Reverse).

However, I'd be very worried about letting a random external class change Count or Reverse: I'd at the very least make the setters internal if not private.

Isn't Count just head == null ? 0 : head.Weight? If so, it shouldn't be maintained separately because that's just an invitation to create bugs in the future. It could be replaced with a computed property.