[자료구조] 트리

1. 개념

노드와 에지로 연결된 그래프의 특수한 형태.

 

2. 특징

• 순환 구조를 가지고 있지 않다.
• 1개의 루트 노드가 존재한다.
• 루트 노드를 제외한 노드는 단 1개의 부모 노드를 갖는다.
• 트리의 부분 트리도 트리의 모든 특징을 따른다.

 

3. 트리의 구성 요소

1) 루트 노드

2) 부모 노드

3) 자식 노드

4) 에지

5) 리프 노드

6) 서브 트리

 

4. 구현

1) 그래프 이용

그래프 구현을 이용해서 구현하면 된다. 인접 리스트 사용.

• 동적으로 크기 조정이 가능하다.
• 연결리스트로 구현되기 때문에 노드의 삽입과 삭제가 쉽다.
• 특정 위치의 노드에 접근하기 위해서 연결리스트를 순회해야 해서 접근 시간이 오래 걸린다.
• 다음 노드를 가리키는 정보를 저장해야 해서 메모리 사용량이 증가할 수 있다.

adjList = new ArrayList[N+1];
        for(int i = 1; i<=N; i++){
            adjList[i] = new ArrayList<>();
        }
        for(int i = 1; i<N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            adjList[s].add(e);
            adjList[e].add(s);
        }

 

2) 배열 이용

• 특정 위치의 노드에 상수 시간으로 접근할 수 있다.
• 배열 크기가 미리 정해져야 한다.
• 배열은 크기가 고정되어 있기 때문에 노드의 삽입이나 삭제가 일어날 경우 재배열이 필요하고 시간이 더 소요될 수 있다.
• 보통 코딩테스트에서는 배열을 많이 이용한다.
• 메모리를 효율적으로 사용할 수 있다. 포인터나 노드간의 연결 정보를 따로 저장하지 않아도 되기 때문이다.
• 하지만 트리의 크기가 커지면 비어있는 공간이 많이 생겨서 메모리 낭비가 생길 수도 있다.

1차원 배열

• 노드의 부모 자식 관계를 나타내기 위해 완전 이진 트리를 가정하고 배열의 크기를 결정해야 한다. 
• 완전 이진 트리나 포화 이진 트리에 사용하면 좋다.
• 완전 이진트리나 포화 이진 트리가 아니면 빈 공간이 많이 생겨 메모리 낭비가 발생할 수 있다.

 

2차원 배열

• 일반적으로 완전 이진 트리에 사용되는 방법이다.
• 최대 노드의 수가 행이되고, 왼쪽 자식 오른쪽 자식을 가지니 열은 2가 된다.

 

5. 관련 문제

백준 11725

GitHub - Lee-Min-Jung/coding_test_practice

백준 1068

GitHub - Lee-Min-Jung/coding_test_practice