Tree

트리는 스택이나 큐와 같은 선형 구조가 아닌 비선형 구조이다. 트리는 계층적 관계를 표현하는 자료구조로 표현에 집중한다. 무엇인가를 저장하고 꺼내야 한다는 사고에서 벗어나 트리라는 자료구조를 바라보는 것이 좋다.

트리에서는 각 층별로 숫자를 매겨 이를 트리의 Level(레벨)이라고 한다. 레벨은 0부터 시작하고 루트 노드가 레벨 0이 된다. 그리고 트리의 최고 레벨을 가리켜 해당 트리의 Height(높이)라고 한다.

트리를 구성하는 요소

• Node(노드)
  트리를 구성하고 있는 각각의 요소를 의미
• Edge(간선)
  트리를 구성하기 위해 노드와 노드를 연결하는 선을 의미
• Root Node(루트 노드)
  트리 구조에서 최상위에 있는 노드를 의미
• Terminal Node(=Leaf Node, 단말 노드)
  하위 노드를 갖지 않는 노드를 의미
• Internal Node(내부 노드, 비단말 노드)
  단말 노드를 제외한 모든 노드(루트 노드도 포함)를 의미

Binary Tree (이진 트리)

루트 노드를 중심으로 두 개의 서브 트리로 나누어진다. 또한 두 서브 트리 모두 두 개의 서브 트리로 나눠지는 이진 트리어야 한다. 재귀적인 정의이기 때문에 이해가 어려울 수 있다. 이진 트리 표현 시 공집합 또한 이진 트리로 표현시켜야 한다. 그래야 재귀적으로 조건을 확인했을 때, 단말 노드에 도착했을 때, 정의가 만족하기 때문이다. 노드가 단 하나뿐인 트리도 이진 트리라고 할 수 있다.

이진 트리의 종류

Perfect Binary Tree (포화 이진 트리)

그림처럼 모든 레벨이 꽉 찬 이진 트리를 포화 이진 트리라고 한다.

Complete Binary Tree (완전 이진 트리)

그림처럼 위에서 아래로, 왼쪽에서 오른쪽으로 순서대로 차곡차곡 채워진 이진 트리를 가리켜 완전 이진 트리라고 한다.

이 그림은 왼쪽부터 채워지지 않았기 때문에 완전 이진 트리가 아니다.

Full Binary Tree (정 이진 트리)

그림처럼 모든 노드가 0개 또는 2개의 자식 노드만을 가지는 이진 트리를 정 이진 트리라고 한다.

배열로 구성된 Binary Tree는 노드의 개수가 n개이고, root가 0이 아닌 1에서 시작할 때, i번째 노드에 대해 parent(i) = i/2, left_child(i) = 2i, right_child(i) = 2i + 1의 인덱스를 각각 가진다.

BST (Binary Search Tree, 이진 탐색 트리)

효율적인 탐색을 위해서는 어떤 방식으로 찾을까에 대해서만 고민해서는 안된다. 효율적인 탐색을 위한 저장 방법이 무엇일까에 대한 고민이 우선적으로 필요하다. 이진 탐색 트리는 이진 트리의 일종이다. 이진 탐색 트리에는 데이터를 저장하는 규칙이 있고 그 규칙은 특정 데이터의 위치를 찾는데에 사용할 수 있다. 규칙은 다음과 같다.

1. 이진 탐색 트리의 노드에 저장된 키는 유일하다.
2. 부모의 키가 왼쪽 자식 노드의 키보다 크다.
3. 부모의 키가 오른쪽 자식 노드의 키보다 작다.
4. 왼쪽과 오른쪽 서브트리도 이진 탐색 트리이다.

이진 탐색 트리의 탐색 연산은 O(log n)의 시간 복잡도를 가진다. 정확히 말하면 O(h)라고 표현하는 것이 맞다. 여기서 h는 트리의 높이를 의미한다. 트리의 높이를 하나씩 더해갈수록 추가할 수 있는 노드의 수가 두 배씩 증가하기 때문이다. 하지만 이러한 이진 탐색 트리는 Skewed Tree(편향 트리)가 될 수 있다. 저장 순서에 따라 계속 한 쪽으로만 노드가 추가되는 경우가 발생하기 때문이다. 이럴 경우 성능에 영향을 미치게 되며 탐색의 Worst Case가 되고 시간 복잡도는 O(n)이 된다.

배열보다 많은 메모리를 사용하여 데이터를 저장했지만 탐색에 필요한 시간 복잡도가 같게 되는 비효율적인 상황이 초래된다. 이를 해결하기 위해서 Rebalancing 기법이 등장하였다. 균형을 잡기 위한 트리 구조의 재조정을 Rebalancing이라고 한다.

BST 구현하기

오늘 공부한 BST를 구상해보았다.

1. 루트 노드를 지정한다.
2. 다음으로 들어오는 수 a가 루트 노드보다 작다면 왼쪽 자식으로 내리고, 크다면 오른쪽 자식으로 내린다.
3. 만약 왼쪽 자식으로 내렸을 경우에 왼쪽 자식이 존재한다면 a와 왼쪽 자식을 비교한다. a가 더 작으면 왼쪽 자식의 왼쪽 자식이 되고, 더 크면 왼쪽 자식의 오른쪽 자식이 된다.
4. 만약 오른쪽 자식으로 내렸을 경우에 오른쪽 자식이 존재한다면 a와 오른쪽 자식을 비교한다. a가 더 작으면 오른쪽 자식의 왼쪽 자식이 되고, 더 크면 오른쪽 자식의 오른쪽 자식이 된다.
5. 2~4를 반복한다.

위 로직의 흐름을 테스트 데이터로 돌렸을 때를 작성해보았다. 테스트 데이터는 5, 4, 3, 6, 7로 이루어진 리스트이다.

1. 5를 루트 노드로 지정한다.

        5

2. 다음 수인 4가 5보다 큰지 작은지 비교한다. 4는 5보다 작으므로 왼쪽 자식이 된다.

        5
    4

3. 다음 수인 3이 5보다 큰지 작은지 비교한다. 3은 5보다 작으므로 왼쪽 자식으로 내려간다. 이미 왼쪽 자식이 형성되어 있기 때문에 5의 왼쪽 자식인 4와 3을 비교한다. 4보다 3이 작으므로 4의 왼쪽 자식으로 3이 배치된다.

        5
    4
3

4. 다음 수인 6을 5와 비교한다. 5보다 크므로 6은 5의 오른쪽 자식으로 들어간다.

        5
    4       6
3

5. 다음 수인 7을 5와 비교한다. 5보다 크므로 오른쪽으로 내려간다. 오른쪽에 6이 이미 존재하므로 6과 7을 비교한다. 7이 더 크므로 7은 6의 오른쪽 자식이 된다.

        5
    4       6
3              7