1. Tree
트리는 루트 값과 부모-자식 관계의 서브트리로 구성되며, 서로 연결된 노드의 집합이다. 아래 그림은 트리의 구조이다.
트리는 항상 루트 노드에서부터 시작된다. 루트 노드는 자식 노드를 가지며 각각은 간선(edge)으로 연결되어 있다. 자식 노드의 개수는 차수(degree)라고 하며, 자신을 포함한 모든 자식 노드의 개수가 크기(size) 이다 (size는 간단히 노드의 총 개수라고 생각하면 된다). 높이 (height)는 현재 위치에서부터 리프(leaf)까지의 거리, 깊이(depth)는 루트에서부터 현재 노드까지의 거리이다. 서브트리(subtree)는 어떤 노드와 그 자손으로 구성된 트리이다. 레벨(level)은 0에서 부터시작하여 루트에서 얼마나 멀리 떨어져 있는지를 나타낸다. 트리는 항상 단방향이기 때문에 간선의 화살표는 생략했다.
2. Graph vs Tree
여기서 그래프와 트리의 차이점이 뭘까. 트리는 순환 구조를 갖지 않는 그래프이다. 다시말해 트리는 특수한 형태의 그래프의 일종으로 그래의 범주에 포함된다. 이외에도 단방향, 양방향을 모두 가리킬 수 있는 그래프와 달리, 트리는 부모 노드에서 자식 노드를 가리키는 단방향뿐이다. 또한, 트리는 하나의 부모 노드를 갖는다는 차이점이 있으며 루트도 하나여야 한다.
아래 그림들은 모두 트리가 아닌데, 1)은 순환 구조이기 때문에 트리의 정의에 어긋난다. 2)는 C노드의 부모 노드가 두개이다. 3)은 루트가 두 개이며 A,B와 C,D,E는 서로 연결되어 있지 않다.
3. 이진 트리 (Binary Tree)
트리 중에서도 가장 널리 사용되는 트리 자료구조는 이진 트리(Binary Tree)와 이진 탐색 트리(Binary Search Tree)이다. 먼저 각 노드가 m개 이하의 자식을 갖고 있으면 m-ary 트리라고 한다. 여기서 m=2이면 모든 노드의 차수가 2이하라는 말로 특별히 이진트리라고 부른다. 이진 트리는 왼쪽, 오른쪽 최대 2개의 자식을 갖는 매우 단순한 형태로 다진 트리에 비해 훨씬 간결하여 여러 가지 알고리즘을 구현할 수 있다.
이진트리는 왼쪽 자식과 오른쪽 자식을 구분한다.
정 이진 트리 (Full Binary Tree)
모든 노드가 0개 또는 2개의 자식 노드를 갖는다.
완전 이진 트리 (Complete Binary Tree)
마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 모든 노드는 가장 외쪽부터 채워져 있다.
포화 이진 트리 (Perfect Binary Tree)
모든 노드가 2개의 자식을 갖고 있으며 모든 리프 노드가 동일한 깊이 또는 레벨을 갖는다.
4. 이진 탐색 트리(Binary Search Tree)
이진 트리는 정렬 여부와 관계 없이 모든 노드가 둘 이하의 자식을 갖는 단순한 트리 형태라고 했다. 이진 탐색 트리(BST)는 정렬된 트리를 말하는데, 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이루어여 있고, 노드의 오른쪽 서브트리에는 그 노드의 값과 같거나 큰 값들을 지닌 노드들로 이루어져 있는 트리를 뜻한다.
탐색: O(h)
이진탐색트리에서 탐색연산의 시간복잡도는 트리의 높이인 O(h)가 된다. 최악의 경우 Leaf노드까지 탐색하게 되기 때문이다. 아래는 이진 탐색 트리를 이용해 원하는 값을 찾는 방식이다.
루트는 15이며 8은 15보다 작다. 따라서 왼쪽 자식 노드를 탐색한다. 10보다도 8이 작으므로 외쪽을 택한다. 이번에는 5보다 크므로 오른쪽을 선택한다. 다음은 7보다 크므로 오른쪽을 탐색해 정답을 찾아낸다.
삽입: O(h)
이진 탐색 트리의 삽입은 탐색으로 통해 데이터가 들어갈 자리를 먼저 찾은 후에 삽입된다. 따라서 탐색과 마찬가리조 O(h)의 시간 복잡도를 가진다. 또한 삽입은 항상 리프 노드에서 이루어지며 트리의 최소값과 최대값은 트리의 가장 왼쪽, 오른쪽이 된다.
삭제
이진 탐색 트리의 삭제는 원하는 노드를 탐색한 뒤 해당 노드를 삭제한다. 삭제한 후에는 남은 노드들을 이진탐색트리의 조건에 맞게 조정해야 한다. 삭제 연산은 크게 세가지로 나뉜다.
- 삭제하려는 노드의 자식노드가 존재하지 않는 경우
이때는 노드를 삭제하고 부모 노드의 포인터를 None으로 만들면 된다.
- 삭제하려는 노드의 자식노드가 1개만 있는 경우
이때는 노드를 삭제하고 자식 노드를 삭제된 노드 위치로 올리면 된다.
- 삭제하려는 노드의 자식노드가 2개인 경우
이때는 노드를 삭제하고 삭제된 노드의 왼쪽 서브트리에서 값이 가장 큰 노드를 올린 후에 다시 이진 탐색 트리 형태를 맞춰주면 된다.
5. 자가 균형 이진 탐색 트리 (Self-Balancing Binary Search Tree)
BST는 운이 나쁘면 트리의 모양이 균형을 제대로 이루지 못할 수 있다. 아래 그림은 비효율적으로 구성된 균형이 깨진 이진 탐색 트리이다. 균형이 깨지면 탐색시에 O(logn)이 아니라 O(n)에 근접한 시간이 소요될 수 있다.
이렇게 되면 연결 리스트와 다르지 않고, 7을 찾기 위해서는 루트부터 맨 끝까지 차례대로 모두 탐색해야 하므로 전혀 효율적이지 않다. 이런 트리는 균형을 맞춰줄 필요가 있는데, 그래서 고안해낸 것이 바로 자가 균형 이진 탐색 트리이다.
자가 균형 이진 탐색트리는 삽입, 삭제 시 자동으로 높이를 작게 유지하는 이진 탐색 트리이다. 이진 균형 검색 트리로는 AVL 트리와 레드.블랙 트리가 있다. 아래 그림에서 균이 깨진 1)에서는 7을 찾기 위해 7번의 연산이 필요핟지만 균형이 잘 잡힌 2)의 경우 2번 만에 7을 칮는다. 따라서 트리의 균형을 맞추는 작업을 매우 중요하다.
6. 신장 트리 (Spanning Tree)
신장트리는 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다.
아래 그림에서 왼쪽은 그래프가 노드1을 포함하고 있지 않기 때문에 신장 트리에 해당하지 않는다. 오른쪽은 사이클이 존재하므로 신장 트리가 아니다.
