Реализация Авл дерева на C#


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

Простой тест:

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();
  }


244
1
задан 12 марта 2018 в 03:03 Источник Поделиться
Комментарии
1 ответ

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



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

Это лишнее, чтобы явно упомянуть IEnumerable потому что IEnumerable<T> расширяет его.

Есть ли причина не делать ограничения where T : IComparable<T>?



        public sealed class Node : IEnumerable<T>

Почему это осуществить IEnumerable<T>? Я не могу видеть абстрактную причину, почему это необходимо, и если я закомментируйте : IEnumerable<T> и методы Node.GetEnumerator(Node) и Node.GetEnumerator() код все еще компилируется, в том числе образец использования.



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

Это только кажется, используемые для прямого назначения, такие как node.Height = node.ComputeHeight(). Почему бы не встроить назначение следующим образом?

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

ИМО это было бы более идиоматические использовать вычисляемое свойство:

            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(); }

Две вещи:


  1. При каких обстоятельствах parentArray == null? Я подозреваю, что это должны быть заявлены ложные, а не рассматриваются как особый случай.

  2. parentArray.reverse? Если сбор необходимо обрабатывать несколько заказов, возможно, вам стоит забыть все о IComparable/IComparable<T> и вместо того, чтобы использовать IComparer<T> чтобы определить заказ.



            internal void SetParentEdge(Node node)

Я не понял название. От реализации, это выглядит как SetParent.



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

и следующие Funcв таком же стиле, очень странный стиль. Они заставляют меня подозревать, что вы пришли из JavaScript. Простой рефакторинг дает обычный способ:

            private Node GetPreviousTopParent()
{
var node = this;
while (node.Parent != null && node.Parent.Left == node)
node = node.Parent;
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);

Это тоже довольно странно. Во-первых, почему эти преобразования полезны? Во-вторых, второй представляется единственным источником узлов, которые не имеют parentArray правильно установленные, и, следовательно, являются потенциальным источником ошибок.

Кажется, что главная ценность этих преобразований предоставляют внешний API, но ИМО, лучшее решение для изготовления внешнего API работать чисто с T можно было бы сделать Node частная и только предоставляют доступ к API, который явно использует T.



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

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


Да? Первый метод игнорирует свой аргумент, что это не из-парам, но перезаписывается без прочтения. Единственное абонента является второй способ. Почему не просто?

        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# синтаксис сахара для этого:

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

(Хотя см. мой предыдущий комментарий на устранение Reverse).

Однако, я бы очень волновалась насчет того, чтобы позволить случайным внешним изменением класса Count или Reverse: я бы по крайней мере сделать сеттеры internal если не private.

Не Count просто head == null ? 0 : head.Weight? Если это так, то он не должен быть отдельно, потому что это просто приглашение для создания ошибок в будущем. Это может быть заменен вычисляемого свойства.

2
ответ дан 12 марта 2018 в 12:03 Источник Поделиться