이 진 트 리 의 집합 총화 분석 에 대하 여 논 하 다.

우 리 는 모두 Dictionary 가 요 소 를 찾 는 것 이 매우 빠르다 는 것 을 알 고 있 습 니 다.그 실현 원 리 는 TKey 의 값 을 배열 의 지정 한 위치 에 분산 시 키 고 Tvalue 의 값 을 해당 하 는 위치 에 저장 하 는 것 입 니 다.같은 알고리즘 을 사용 하기 때문에 Tvalue 의 위 치 를 쉽게 찾 을 수 있 습 니 다.걸 리 는 시간 은 대체적으로 해시 알고리즘 을 실현 하 는 시간 입 니 다.그 중의 요소 의 개수 와 관계 가 없습니다.그러므로 값 을 얻 는 시간의 복잡 도 는 O(1)이다.집합 은 모두 가장 기본 적 인 문법 을 바탕 으로 하 는 배열[]이다.먼저 분 배 를 한 다음 에 요 소 를 추가 하고 용량 이 부족 하면 2 배 용량 의 배열 을 만 들 고 이전의 요 소 를 할당 하여 이전의 배열 을 회수 하 는 것 이다.그러나 해시 알고리즘 을 바탕 으로 하 는 집합 은 약간 다르다.그 는 매번 2 배 용량 의 배열 을 만 드 는 것 이 아니다.원 소 를 배열 에 고 르 게 분포 시 키 기 위해 배열 의 용량 은 이렇게 증가 했다.3,7,11,17,23,29,37,47,59,71,89,107,131,163,197,239,293,353,431,521,631,761,919,1103...질 수의 방식 으로 증가 했다.배열 을 확장 할 때마다 용량 이 적 기 때문에 많은 요 소 를 추가 하려 면 프로그래머 가 미리 메모 리 를 할당 하지 않 으 면 여러 배열 의 생 성,복사,회수 가 발생 합 니 다.유용 한 것 을 만들어 서 사용 하고 싶 은 사람 이 사용 하고 연습 도 할 수 있 도록 하려 고 했 습 니 다.그래서 이번 에는 이 진 트 리 를 바탕 으로 나 무 를 찾 는 집합 을 만 들 었 습 니 다.우 리 는 이 진 트 리 에서 요 소 를 조회 하 는 가장 좋 은 시간 복잡 도 는 O(logN)인 것 을 알 고 있 습 니 다.즉,최 악의 시간 복잡 도 는 O(n)입 니 다.즉,잎 노드 를 제외 하고 모든 노드 는 하나의 키 노드 만 있 습 니 다.요 소 를 찾 는 것 도 빠 릅 니 다.그리고 찾 을 때 모두 Int 형 비교 만 합 니 다.Dictionary는 해시 알고리즘 을 기반 으로 합 니 다.물론 이 삽입 검색 트 리 의 집합 을 바탕 으로 하 는 것 도 단점 이 있 습 니 다.1:요 소 는 인터페이스 IBinary Tree 를 실현 해 야 합 니 다.그 속 성 Compare Value 는 주로 이 진 트 리 를 비교 생 성 하 는 데 사 용 됩 니 다.2:요 소 는 new 가 있어 야 합 니 다.즉,기본 유형 int,char,string 등 3 은 지원 되 지 않 습 니 다.모든 노드 는 좌우 두 개의 키 노드 가 있 습 니 다.그들 은 포인터 역할 을 할 뿐 이 노드 의 하위 노드 를 가리 키 고 추가 적 인 소량의 메모리 만 차지 합 니 다.4:기본적으로 재 귀 를 바탕 으로 이 루어 집 니 다.요소 가 너무 많 으 면 스 택 에 넘 치 는 장점 은 자주 사용 하 는 기능 이 있 습 니 다.기능 은 다음 과 같 습 니 다.연습 하 시 겠 습 니까?계속 최적화 할 거 야

public class BinaryTree<T> : IDisposable, IEnumerable<T>, IEnumerable where T :IBinaryTree, new()
    {
        public BinaryTree();
        public BinaryTree(IEnumerable<T> list);//
        public BinaryTree(T root); //
        public int Count { get; }//
        public T this[IBinaryTree iBinaryTree] { get; }//
        public void Add(T t);//
        public void Clear();//
        public bool Contains(T iBinaryTree);//
        public void Dispose();// , using
        public T Find(IBinaryTree iBinaryTree);//
        public T Find(IBinaryTree iBinaryTree, TreeNode<T> node);//
        public T FindMax();//
        public T FindMin();//
        public T FindMin(TreeNode<T> node);//
        public IEnumerator<T> GetEnumerator();// , foreach
        public TreeNode<T> Remove(T t);//
        public TreeNode<T> Remove(IBinaryTree iBinaryTree, TreeNode<T> node);//
        public IEnumerable<T> Sort();// ( )
        public IEnumerable<T> ToList();//
    }


namespace Utils
{
    /// <summary>
    ///
    /// </summary>
    public interface IBinaryTree
    {
        /// <summary>
        ///
        /// </summary>
        int CompareValue
        {
            get;
            set;
        }
    }
    public class TreeNode<T> where T : IBinaryTree, new()
    {
        public TreeNode<T> Left
        {
            get;
            set;
        }
        public TreeNode<T> Right
        {
            set;
            get;
        }
        public T Data
        {
            get;
            set;
        }
        public TreeNode(T t)
        {
            this.Data = t;
        }
        public TreeNode()
            : this(default(T))
        {
        }
    }
    /// <summary>
    ///
    /// </summary>
    public class BinaryTree<T> : IDisposable,IEnumerable<T> where T : IBinaryTree, new()
    {
        public BinaryTree()
        {

        }
        public BinaryTree(T root)
        {
            if (root == null)
            {
                throw new NullReferenceException("Parameter is null");
            }
            Add(root);
        }
        public BinaryTree(IEnumerable<T> list)
        {
            if (list == null)
            {
                throw new NullReferenceException("Parameter is null");
            }
            foreach (var item in list)
            {
                Add(item);
            }
        }
        //
        private TreeNode<T> root;
        // ( , private)
        private void Add(T t, TreeNode<T> root)
        {
            if (t == null)
            {
                return;
            }
            if (t.CompareValue < root.Data.CompareValue)
            {
                if (root.Left == null)
                {
                    root.Left = new TreeNode<T>(t);
                    ++Count;
                }
                else
                {
                    Add(t, root.Left);
                }
            }
            else if (t.CompareValue > root.Data.CompareValue)
            {
                if (root.Right == null)
                {
                    root.Right = new TreeNode<T>(t);
                    ++Count;
                }
                else
                {
                    Add(t, root.Right);
                }
            }
            else
            {
                root.Data = t;
            }
        }
        //
        public void Add(T t)
        {
            if (t == null)
            {
                return;
            }
            if (this.root == null)
            {
                this.root = new TreeNode<T>(t);
                ++Count;
            }
            else
            {
                Add(t, this.root);
            }
        }
        //
        public T FindMin(TreeNode<T> node)
        {
            if (node == null)
            {
                return default(T);
            }
            if (node.Left == null)
            {
                return node.Data;
            }
            else
            {
                return FindMin(node.Left);
            }
        }
        //
        public T FindMin()
        {
            return FindMin(this.root);
        }
        //
        private T FindMax(TreeNode<T> node)
        {
            if (node.Right == null)
            {
                return node.Data;
            }
            else
            {
                return FindMax(node.Right);
            }
        }
        //
        public T FindMax()
        {
            return FindMax(this.root);
        }
        //
        public TreeNode<T> Remove(IBinaryTree iBinaryTree, TreeNode<T> node)
        {
            if (node == null)
            {
                return null;
            }
            if (iBinaryTree == null)
            {
                return node;
            }
            if (iBinaryTree.CompareValue < node.Data.CompareValue)
            {
                node.Left = Remove(iBinaryTree, node.Left);
            }
            else if (iBinaryTree.CompareValue > node.Data.CompareValue)
            {
                node.Right = Remove(iBinaryTree, node.Right);
            }
            else
            {
                if (node.Left != null && node.Right != null)
                {
                    T tmpNode = FindMin(node.Right);//
                    node.Data.CompareValue = tmpNode.CompareValue;//
                    node.Right = Remove(tmpNode, node.Right);// ,
                }
                else
                {
                    if (node.Left == null)
                    {
                        node = node.Right;
                    }
                    else if (node.Right == null)
                    {
                        node = node.Left;
                    }
                    else
                    {
                        node = null;
                    }
                    if (this.root.Data.CompareValue == iBinaryTree.CompareValue)//
                    {
                        this.root = node;
                    }
                }
                --Count;
            }
            return node;
        }
        //
        public TreeNode<T> Remove(T t)
        {
            if (this.root == null || t==null)
            {
                return null;
            }
            return Remove(t, this.root);
        }
        //
        public T Find(IBinaryTree iBinaryTree, TreeNode<T> node)
        {
            if (node == null || iBinaryTree == null)
            {
                return default(T);
            }
            if (iBinaryTree.CompareValue < node.Data.CompareValue)
            {
                return Find(iBinaryTree, node.Left);
            }
            else if (iBinaryTree.CompareValue > node.Data.CompareValue)
            {
                return Find(iBinaryTree, node.Right);
            }
            return node.Data;
        }
        //
        public T Find(IBinaryTree iBinaryTree)
        {
            return Find(iBinaryTree, this.root);
        }
        //
        private bool Contains(IBinaryTree iBinaryTree, TreeNode<T> node)
        {
            if (node == null || iBinaryTree == null)
            {
                return false; ;
            }
            if (iBinaryTree.CompareValue < node.Data.CompareValue)
            {
                return Contains(iBinaryTree, node.Left);
            }
            else if (iBinaryTree.CompareValue > node.Data.CompareValue)
            {
                return Contains(iBinaryTree, node.Right);
            }
            return iBinaryTree.Equals(node.Data);
        }
        //
        public bool Contains(T iBinaryTree)
        {
            return Contains(iBinaryTree, this.root);
        }
        //
        public void Clear()
        {
            while (this.Count > 0)
            {
                Remove(this.root.Data);
            }
            this.root = new TreeNode<T>();
        }
        //
        public void Dispose()
        {
            while (this.Count > 0)
            {
                Remove(this.root.Data);
            }
            this.root = null;
        }
        //
        public int Count
        {
            private set;
            get;
        }
        //
        public IEnumerable<T> ToList()
        {
            IList<T> list = new List<T>(Count);
            LCR(this.root,list);
            return list;
        }
        // , ,
        private void LCR(TreeNode<T> node, IList<T> list)
        {
            if (node == null)
            {
                return;
            }
            if (node.Left != null)
            {
                LCR(node.Left, list);
            }
            list.Add(node.Data);//
            if (node.Right != null)
            {
                LCR(node.Right, list);
            }
        }
        //
        public IEnumerable<T> Sort()
        {
            return ToList();
        }
        //
        public IEnumerator<T> GetEnumerator()
        {
            return this.ToList().GetEnumerator();
        }
        //
        IEnumerator IEnumerable.GetEnumerator()
        {
            return this.GetEnumerator();
        }
        public T this[IBinaryTree iBinaryTree]
        {
            get {
                return this.Find(iBinaryTree);
            }
        }

    }
    public class Node : IBinaryTree
    {
        /// <summary>
        ///
        /// </summary>
        public int CompareValue
        {
            get;
            set;
        }
        public string Name
        {
            get;
            set;
        }
        public override string ToString()
        {
            return string.Format("CompareValue:{0},Name:{1}", this.CompareValue, this.Name);
        }
    }
}

좋은 웹페이지 즐겨찾기