트리(Tree)
그래프의 일종으로 여러 노드가 한 노드를 가리킬 수 없는 구조.
서로 다른 두 노드를 잇는 길이 하나뿐인 그래프.
간단한 부연 설명을 해보자면..
루트노드 : 트리의 시작 노드
간선 : 노드와 노드를 잇는 선
차수 : 해당 트리의 최대 자식노드의 수
리프노드 : 아무런 자식이 없는 노드.
자식노드 : 위로 간선이 연결되어 부모를 가진 노드.
부모노드 : 아래로 간선이 연결되어 자식을 가진 노드.
형제노드 : 같은 부모를 가진 노드
조상노드 : 해당 노드의 부모 + 부모의 부모 + ... 대손을 거쳐 올라간다.
높이 : 간선의 수
서브트리 : 자식노드가 루트노드가 되어 새로 생성된 트리.
트리의 벤다이어그램은 대충 이렇다.
이제 이진 트리부터 한 번 살펴보자.
아주 기본적인 이진 트리.
이진 트리의 정의는
트리의 차수 <= 2.
즉 최대로 자식을 둘 이하만 가지면 된다는 것이다.
말 그대로 한 쪽으로 트리의 방향이 '편향' 되었지 않은가?
그래서 편향 이진 트리다.
리프 노드를 제외하고, 모든 부모 노드가 자식을 둘 씩 가진 트리이다.
꽉꽉 다 찼다고 해서
포화 이진 트리.
끝 부분(마지막 노드)를 제외하고 모두 채워진 상태.
마지막 레벨의 노드들은 왼쪽으로 채워져 있음.
마지막 레벨이 다 채워질 수도 있다. (포화 이진 트리)
<일반 트리에서 이진 트리로 변환하기>
1. 맨 왼쪽 간선을 제외하고 삭제.
2. 형제 노드를 서로 연결.
3. 시계 방향으로 45도 회전.
이제 트리를 배열과 리스트로 구현이 가능하다.
아래의 트리를 사용하겠다.
아래는 배열 인덱스로 구현을 한 상태.
왼 -> 오 -> 왼 -> 오 순서대로 차례대로 넣어준다.
다만, 주의 할 점은 빈 공간이 있으면 그 다음 인덱스에 다음 노드를 넣어준다.
아래는 리스트 방식으로, 구조체 하나의 정보가 되겠다.
왼쪽 자식노드와 오른쪽 자식노드를 가리키는 포인터
Left, Right가 있으며
값을 가지고있는 Data 부분이 존재함.
이제 순회에 대해서 살펴보자.
(순회 과정은 재귀적으로 이루어진다.)
아래의 트리가 주어질 때,
A
B C
1. 전위 순회(PreOrder)
A - B - C
2. 중위 순회(InOrder)
B - A - C
3. 후위 순회(PostOrder)
B - C - A
4. 레벨 순회(LevelOrder)
이 순회는 한 레벨을 다 흝어 본 후에
다음 레벨로 넘어가는 식이다.
제일 쉬운 순회.
A - B - C
이제 배열, 리스트에서의 순회 방법을 알아보자.
부모의 인덱스(x) * 2 = 왼쪽 자식. (L)
부모의 인덱스(x) * 2 + 1 = 오른쪽 자식. (R)
현재 노드를 방문 처리(출력) (D)
아래의 그림에서도 이를 확인 할 수 있다.
작업 D : 현재 노드를 방문 처리(출력)
작업 L : 현재 노드의 왼쪽 서브트리로 이동
작업 R : 현재 노드의 오른쪽 서브트리로 이동
배열, 리스트로 된 트리에도
아까 보았던 전위, 중위, 후위, 레벨 순회를 똑같이 적용시키면 된다.
수식 표기법(TIP)
식을 표기하는데 3가지 방법이 있지 않은가.
전위, 중위, 후위 표기법.
여기서 인간이 사용하는 표기법은 중위 표기법이다.
이 표기법을 변환 하는데 골머리를 앓았다면, 이 트리로서 단번에 해결할 수 있다.
2 + 3 이라는 중위 표기식이 있을 때,
전위 표기법으로 바꾼다 하면은 위의 트리를 전위 순회한 결과를 쓰면 된다.
전위 표기법(전위 순회) : + 2 3
중위 표기법(중위 순회) : 2 + 3
후위 표기법(후위 순회) : 2 3 +
정말 쉽다.
<이진 탐색 트리>
이진 트리가 있다면, 탐색하는 것도 당연히 존재하겠지?.
<이진 탐색의 정의>
- 모든 원소는 서로 다른 유일한 키(값)을 가진다.
- 왼쪽 서브 트리에 있는 원소들의 키는 그 루트의 키보다 작다.
- 오른쪽 서브트리에 있는 원소들의 키는 그 루트의 키보다 크다.
- 왼쪽 서브 트리와 오른쪽 서브 트리도 이진 탐색 트리이다.
삽입과 삭제의 행동이 있는데,
삽입의 경우 아래의 규칙을 따른다.
- 키가 있는지 탐색 -> 탐색을 실패한 자리에 원소를 삽입.
이진 탐색 트리의 조건에 맞춰 값을 노드와 비교해간다.
그러다 탐색을 실패(노드가 없음)한 자리에 그 값을 넣어주는 것.
아래는 삭제의 과정이다.
삭제 시 중요한 과정이 있는데, 이를 후속 처리라 한다.
노드를 삭제한 후 이진 탐색 트리의 성질을 깨뜨리면 안되기에,
노드의 위치를 조정하는 과정이 필요.
앞서 이진 트리들을 둘러보았는데, 이런 구조이면
리프 노드들의 NULL 링크가 남아돌아 낭비가 발생함.
이를 방지하기 위해 아래와 같은 트리가 등장하였다.
왜 이런 트리를 사용하는가?.
- 트리 순회를 재귀로 구현시 트리가 커질수록 비효율적.
- 사용하지 않는 NULL 링크까지 효율적 사용을 위함.
- 재귀 구조없이 트리순회를 위함.
(여기서 스레드(Thread)란 OS에서의 그 스레드가 아니라
단순한 실의 의미로서 사용 됨.)
남아도는 NULL링크를 사용하기 위해
루트 노드(헤드 노드)를 생성하여 가리키게 함.
왼쪽의 스레드는 중위 선행자.
오른쪽의 스레드는 중위 후속자라고 한다.
여기서 중위 선행자의 개념은
중위 순회시 현재 노드의 앞에 있는 노드를 가리키는 것.
후속자의 개념은
중위 순회시 현재 노드의 다음 노드를 가리키는 것.
(중위가 붙는 이유는
스레드 이진 트리가 중위 순회를 기반으로 하기 때문임.)
또한 아래와 같은 특징을 발견할 수 있음.
- 노드의 개수는 n개.
- NULL이 아닌 링크의 갯수는 n-1
- NULL링크의 수는 n+1
- 모든 링크의 수는 2n.
<힙>
메모리 구조에서의 그 힙(Heap)영역이 아니다.
최댓값, 최솟값을 찾아내는 연산을 빠르게 하기 위한
완전 이진 트리 기반의 자료구조.
즉, 루트 노드에 최소힙, 최대힙이냐에 따라서
최솟값, 최댓값이 들어가게 되는 구조이다.
삽입, 삭제는 링크를..
'자료구조' 카테고리의 다른 글
| 그래프, DFS, BFS (0) | 2017.10.03 |
|---|
