스터디를 진행하면서 공부한 순서대로 블로깅을 하고있는데, 원래라면 힙에 대해서 작성을 해야하는데 힙을 공부하기 위해서 트리에 대한 사전 공부가 필요하다고 생각이 되어서 이렇게 임의로 순서를 바꿔서 트리!!!를 먼저 블로깅 하게 되었습니다 :)
목차
0. 트리
트리(tree)는 계층적인 자료를 표현할 때 사용하는 자료구조입니다.
우리가 일반적으로 생각하는 트리는 아래와 같죠?!
자료구조의 트리는 현실 세계에서의 트리와 완전 유사한 모습을 띠고 있습니다. 아마도 그래서 트리라는 이름이 붙지 않았을까 싶네요!
먼저 트리의 요소들을 하나하나 살펴보도록 하겠습니다!
가장 상위에 위치한 노드를 루트 노드라고 부릅니다.
나머지 노드들을 자식 노드들과 함께 묶어서 서브트리라고 부를 수 있습니다.
1개의 선으로 직접 연결된 관계를 부모와 자식 관계라고 표현하고, 2단계 이상으로 연결되어 있는 관계를 조상과 자손 관계라고 부릅니다.
자식 노드가 없는 노드를 단말 노드(leaf node)라고 부르고, 자식 노드가 있다면 비단말 노드(internal node)라고 부릅니다.
노드들을 연결하는 선을 간선이라고 부르고, 노드가 가지고 있는 자식 노드의 수를 차수라고 부릅니다.
레벨은 각 층에 번호를 매기는 것으로 0 혹은 1부터 시작해서 아래로 내려갈수록 커집니다. (저는 보통 1부터 내려가면서 세는 편입니다!)
트리의 높이는 해당 트리의 최대 레벨을 의미합니다.
트리를 설명하기 위해 정말 다양한 용어들을 쉼없이 적어보았는데, 이런 것들이 있구나 정도로만 넘어가셔도 나중에 계속 트리 구조를 보다보면 자동으로 머리에 입력되니 너무 외우려고 하시지 않아도 괜찮습니다!!
1. 이진 트리
트리 중에서 가장 흔하게 쓰이는 트리가 바로 이진 트리입니다.
이름처럼 0~2개의 자식노드만 존재합니다. 이 말은 모든 노드의 차수가 0~2 사이라는 말과 같겠죠?!
이진 트리의 서브트리들도 모두 이진트리로 구성됩니다.
또한 왼쪽과 오른쪽 두 가지만 존재하기 떄문에 서브트리간 순서 역시 의미가 있을 수 있습니다. (이것은 아래서 나올 순회와도 연관이 있습니다!)
n개의 노드를 가지는 이진 트리의 높이는 최대 n, 최소 ceil(log(n+1))이 됩니다.
이진트리는 형태에 따라 포화 이진 트리(full binary tree), 완전 이진 트리(complete binary tree)로 구분할 수 있습니다.
- 포화 이진 트리(full binary tree) : 각 레벨에 노드가 꽉 차있는 이진 트리입니다.
- 완전 이진 트리(complete binary tree) : 높이가 k라면 k-1레벨까지는 노드가 꽉 채워져있고, 마지막 레벨에서는 노드가 꽉 차있지 않아도 되지만 왼쪽부터 순서대로 차있어야 합니다.
포화 이진 트리 ⊂ 완전 이진 트리 ⊂ 일반 이진 트리 관계를 가지고 있습니다.
배열을 사용해서 이진 트리를 구현하는 경우 일반 이진 트리는 중간이 빌 수 있기 때문에 메모리 낭비가 있을 수 있습니다.
따라서 배열을 사용해서 이진트리를 구현하게 된다면 대부분 완전 이진 트리를 구현하는 경우가 많습니다.
완전 이진 트리를 구현한 배열의 경우 부모와 자식의 인덱스 사이에 관계가 존재합니다.
노드 i의 부모 노드 인덱스는 floor(i/2)입니다.
그리고 노드 i의 왼쪽 자식 노드 인덱스는 2*i 이고, 노드 i의 오른쪽 자식 노드 인덱스는 2*i+1가 됩니다.
2. 트리 순회(Tree Traversal)
이진 트리를 순회해야 하는 경우가 있을 수 있습니다.
트리 안의 모든 요소들을 검색한다거나 하는 일 말이죠.
보통은 이진 탐색 트리에서 자주 사용하게 됩니다. (이진 탐색 트리는 아래에서 설명합니다!)
스택이나 큐는 단방향으로 조사할 수밖에 없습니다만 트리는 보다 다양한 방법으로 자료구조 안에 있는 데이터들을 조사할 수 있습니다.
조사하는 순서에 따라 Preorder(전위 순회), Inorder(중위 순회), Postorder(후위 순회), Level-order(레벨 순회) 방식으로 나뉩니다. (항상 왼쪽 서브트리가 오른쪽 서브트리보다 먼저 방문됩니다.)
- Preorder(전위 순회) : 자기 자신, 왼쪽 서브트리, 오른쪽 서브트리 순으로 순회합니다.
- 이진 탐색 트리를 복사할 때 사용합니다.
- Inorder(중위 순회) : 왼쪽 서브트리, 자기 자신, 오른쪽 서브트리 순으로 순회합니다.
- 오름차순으로 무언가를 출력할 때 사용합니다.
- Postorder(후위 순회) : 왼쪽 서브트리, 오른쪽 서브트리, 자기 자신 순으로 순회합니다.
- 요소를 삭제할 때 사용합니다.
- Level-order(레벨 순회) : 모든 노드를 낮은 레벨부터 차례대로 순회합니다.
3. 이진 탐색 트리
이진 탐색 트리는 오름차순으로 정렬되어 있는 이진 트리를 의미합니다.
각각의 하위 트리들 역시 이진 탐색 트리여야 합니다.
또한 중복된 키는 허용되지 않습니다.
여기서 착각하면 안되는 것은 이진 탐색 트리는 완전 이진 트리가 아닐 수 있습니다!
이진 탐색 트리의 Find, Insert, Delete의 모든 과정은 루트 노드에서 시작하게 되고, 아래로 이동하면서 요소를 찾게 됩니다.
3.0. 탐색
루트 노드와 찾는 값을 비교합니다. 같다면 탐색을 마치고, 루트 노드보다 찾는 값이 작으면 왼쪽 서브트리로 내려가고, 루트 노드보다 찾는 값이 크면 오른쪽 서브트리로 내려갑니다.
이 작업을 각 서브트리로 내려가면서 반복합니다. 만약 단말 노드까지 내려가도 발견하지 못했다면 트리에 없는 요소라는 것을 파악할 수 있게 됩니다.
3.1. 삽입
탐색과 동일한 메커니즘으로 위치를 찾습니다.
다만 삽입의 특이한 점은 탐색에 실패하게 되면 그 자리에 새로운 요소가 들어가게 된다는 것입니다.
만약 탐색 중에 같은 이름의 요소를 찾으면 삽입하지 않고 작업이 멈춥니다.
이진 탐색 트리는 중복된 키를 허용하지 않기 때문입니다!
3.2. 삭제
삭제하려는 노드가 단말 노드인 경우, 하나의 서브트리를 가지는 경우, 두 개의 서브트리를 가지는 경우로 나눠서 생각할 수 있습니다.
삭제하려는 노드가 단말 노드인 경우 그냥 바로 삭제하면 끝입니다. (부모 노드의 Link Field를 변경하는 내용은 생략합니다!)
삭제하려는 노드가 하나의 서브트리를 가지는 경우에는 그 서브 트리를 옮겨다 붙이기만 하면 됩니다.
마지막으로 삭제하려는 노드가 두 개의 서브트리를 가지는 경우에는 왼쪽 서브트리에 있는 값 중에서 가장 큰 값이나, 오른쪽 서브트리에 있는 가장 작은 값을 가지고 있는 노드를 삭제하려는 노드의 위치로 옮겨주면 됩니다.
이 작업은 한 개의 노드를 삭제하고 한 개의 노드만 옮김으로써 트리의 변동성을 최소화하기 위해서입니다.
이진 탐색 트리의 탐색, 삽입, 삭제 연산의 시간복잡도는 O(logN)~O(N)까지 다양하게 나올 수 있습니다.
이것은 이진 탐색 트리가 완전 이진 트리가 아니기 때문에 한쪽으로 쏠려있는 형태의 트리가 나올 수 있기 때문입니다.
현실 세계에서는 이런 이진 탐색 트리의 단점을 없애기 위해 AVL트리, 혹은 red-black 트리 등의 균형 이진 탐색 트리를 사용합니다. (이런 균형 이진 탐색 트리에 대한 설명은 별도의 포스팅으로 분리하도록 하겠습니다!)
최근댓글