[3.31] 이진 트리

정의

• 자식 노드의 수가 2개 이하인 것을 이진트리 (Binary Tree)라고 한다.

구현방법

구현방법	장단점
링크드리스트	레퍼런스때문에 헷갈린다. 힙영역을 사용해 공간이 충분하다.
배열	쉽다, 공간복잡도가 높아진다. Heap 자료구조 구현방법.

작업 수행시간

연산	수행시간 (평균)	수행시간 (최악)
삽입	O(log n)	O(n)
삭제	O(log n)	O(n)
검색	O(log n)	O(n)

평균의 수행시간들은 모두 AVL 균형트리가 기준이다.

 

• 평균 수행시간 : 좌우 서브트리의 균형이 맞춰진 AVL 트리 or Red Black Tree
• 최악 수행시간 : 사향트리 (한쪽으로 쏠린 트리)
• ∵ 이진트리의 성능을 최대로 뽑을려면 양쪽 서브트리의 높이의 차가 2 이하로 유지되어야 한다.

수행시간 평균 계산과정

∵ 검색 시간 : 포화이진트리라고 가정할 때, 0층에는 1개, 1층에는 2개, 2층에는 4개, 3층에는 8개....h층에는 2^n개의 Leaf가 존재한다. 

그러므로 2^h = n 이라는 식이 나온다.

양변에 밑이 2인 로그를 취하면 h = log(2)n이 나온다. 빅오 표기법에 따라

O(h) = O(log n)이라는 식이 성립하게된다.

순회

• Preorder Traversal : 부모 노드먼저 순회한 후, 자식 노드로 넘어가는 순회방식 ( ∴ 부모먼저 처리가 됨 )
• Postorder Traversal : 자식 노드먼저 순회한 후, 부모노드를 처리

배열 이진트리 예제

(보통의 이진탐색트리는 포인터를 이용한 구현이 대부분이고 배열을 이용한 트리는 Heap, 즉 우선순위큐에 이용됨)

using System;

namespace Study02
{
    public class BinaryTreeArray
    {
        private string[] arr;
        public string Root
        {
            set
            {
                arr[0] = value;
            }
            get
            {
                return this.arr[0];
            }
        }

        public BinaryTreeArray(int capacity)
        {
            this.arr = new string[capacity];
        }

        public void SetLeft(int parentIndex, string data)
        {
            if(arr[parentIndex] == null || parentIndex >= arr.Length)
            {
                throw new IndexOutOfRangeException("데이터를 넣을 수 없습니다.");
            }
            arr[parentIndex * 2 + 1] = data;
        }

        public string GetLeft(int parentIndex)
        {
            return arr[parentIndex * 2 + 1];
        }

        public void SetRight(int parentIndex, string data)
        {
            if (arr[parentIndex] == null || parentIndex >= arr.Length)
            {
                throw new IndexOutOfRangeException("데이터를 넣을 수 없습니다.");
            }
            arr[parentIndex * 2 + 2] = data;
        }

        public string GetRight(int parentIndex)
        {
            return arr[parentIndex * 2 + 2];
        }

        public string GetParent(int childIndex)
        {
           if(childIndex == 0)
            {
                return null;
            }
            return arr[(childIndex - 1) / 2];
        }

        public void PrintTree()
        {
            for(int i = 0; i < arr.Length; i++)
            {
                Console.Write("{0} ",arr[i] ?? "-");
            }
            Console.WriteLine();
        }
    }
}

 

개인적으로는 루트 인덱스를 1로 하는게 더 나은거 같다 0으로 하면 좀 헷갈림