트리
트리의 개념을 알고 코드를 구현하자
트리(tree)
계층적인 자료를 표현할 때 사용되는 자료구조
트리의 용어
- 노드(node): 트리의 구성요소에 해당
- 루트노드(root node): 가장 높은 곳에 위치한 노드
- 서브트리(subtree): 루트노드를 제외한 나머지 노드, 각 서브트리는 다시 그 서브트리의 루트노드와 다른 서브트리로 나눠질 수 있음
- 간선(edge): 루트와 서브트리를 연결한 선
- 단말노드(terminal node 또는 leaf node): 자식노드가 없는 노드
- 차수(degree): 어떤 노드가 가지고 있는 자식 노드의 개수
- 레벨(level): 트리의 각 층에 번호를 매기는 것, 루트부터 1레벨로 시작
- 높이(height): 트리가 가진 최대 레벨
- 포리스트(forest): 트리의 집합
이진트리(binary tree)
모든 노드가 2개의 서브트리를 갖는 트리로, 이때 서브트리는 공집합일 수도 있다.
따라서 모든 노드의 차수는 2이하이므로 최대 2개까지 자식노드를 가질 수 있다.
참고로 이진트리에는 서브트리 간의 순서가 존재하므로 왼쪽 서브트리와 오른쪽 서브트리는 반드시 구별되어야 한다.
이진트리의 조건
- 공집합이거나
- 루트의 왼쪽, 오른쪽 서브트리는 유한집합이고, 서브트리는 모두 이진트리여야 한다.
이진트리의 성질
- n개의 노드를 가지면 n - 1개의 간선을 가진다. -> 루트를 제외한 모든 노드가 하나의 부모를 가지기 때문이다.
- h 높이의 이진트리는 h개 이상, \(2^h - 1\)개 이하의 노드를 가진다.
이진트리의 분류
- 포화 이진트리(full binary tree): 각 레벨의 노드가 꽉 차있는 이진트리, 정확하게 노드가 \(2^h - 1\)개 이다. 각 노드에서 레벨 단위로 왼쪽에서 오른쪽으로 번호를 부여한다.
- 완전 이진트리(complete binary tree): 높이가 k인 트리에서 k - 1층까지 노드가 다 채워져 있고, 마지막 레벨에선 왼쪽에서 오른쪽으로 노드가 채워져 있는 트리이다. 즉, 노드가 꽉 차 있지 않아도 되지만, 빈 곳이 있으면 안 된다.
오른쪽에서 A, B, C, D, E 노드는 순서대로 1, 2, 3, 4, 5번의 인덱스를 가짐
이진트리의 표현
배열 표현법
\(2^h - 1\)개의 공간을 할당하고, 노드의 번호대로 공간을 할당한다. 주로 포화나 완전 이진트리를 구현할 때 사용된다.
- 노드 i의 부모 인덱스 = i / 2
- 노드 i의 왼쪽 자식 인덱스 = i * 2
- 노드 i의 오른쪽 자식 인덱스 = i * 2 + 1
배열로 표현한 이진트리
링크 표현법
각 노드는 두 개의 포인터를 가져서 왼쪽, 오른쪽 자식을 가리킨다.
링크된 리스트로 표현한 이진트리
이진트리의 순회
전위 순회(preorder traversal)
루트 -> 왼쪽 서브트리 -> 오른쪽 서브트리 순으로 방문한다.(VLR)
루트를 가장 먼저 방문해서 전위라고 부른다.
중위 순회(inoreder traversal)
왼쪽 서브트리 -> 루트 -> 오른쪽 서브트리 순으로 방문한다.(LVR)
루트를 중간에 방문해서 중위라고 부른다. 부모 노드를 처리한 다음에 자식 노드를 처리하는 트리의 레벨 계산의 경우 중위 순회를 쓴다.
후위 순회(postorder traversal)
왼쪽 서브트리 -> 오른쪽 서브트리 -> 루트 순으로 방문한다.(LRV)
루트를 가장 나중에 방문해서 후위라고 부른다. 자식 노드를 처리한 다음에 부모 노드를 처리하는 디렉토리 용량 계산의 경우 후위 순회를 쓴다.
트리를 순회할 때 미리 알아야 하는 것이, 전체를 하나의 루트노드와 왼쪽 서브트리, 오른쪽 서브트리로 보는 것이다. 트리는 여러 서브트리로 구성되어 있으므로 이를 알고 순회 순서를 따지면 더 이해하기 쉽다. 어떤 노드를 방문했을 때, 그 노드는 그 서브트리의 루트 노드라 생각하면 더 편하다.
이진트리는 아니지만 서브트리로 구성된 전체트리
레벨 순회(level traversal)
앞의 세 가지 경우는 내부적으로 스택을 사용해 순회를 했지만, 이 방법은 큐를 사용한다. 큐에서 노드를 하나 꺼내 방문하고 그 자식들을 큐에 삽입한다. 이때 왼쪽 자식을 먼저, 오른쪽 자식을 다음에 처리한다.
스레드 이진트리(threaded binary tree)
노드의 개수가 n이면 각 노드당 2개의 링크가 있으므로 전체 링크 수는 2n이다. 이들 중 루트를 제외한 n - 1개의 노드가 부모와 연결되어 있으므로 나머지 n + 1은 항상 NULL이다. 스레드 이진트리는 이 NULL에 연결된 링크를 활용하여 노드를 순회한다. 링크 값이 NULL을 갖는 대신 중위 선회자나 중위 후속자에 연결되게 한다.
- 중위 선회자: 중위 순회를 쓸 때 어떤 노드의 바로 앞에 방문되는 노드
- 중위 후속자: 중위 순회를 쓸 때 어떤 노드의 바로 뒤에 방문되는 노드
스레드 이진트리