트리

트리의 정의는 노드끼리 전부 연결되어 있으면서 사이클이 존재하지 않는 그래프이다.

트리는 두 지점의 연결 관계로 구성되어 있는데, 계층관계가 존재한다는 것이 특징이다. 우리는 하나의 연결 관계에서 위쪽에 있는 점을 부모라고 부르며, 아래쪽에 있는 점을 자식이라고 부른다.

그 외에도 추가적인 용어들은 다음과 같다.

• 노드: 각 지점을 의미합니다. 정점이라 부르기도 한다.
• 간선: 두 노드를 연결하는 선을 의미합니다. 에지라고 부르기도 한다.
• 루트 노드: 트리에서 맨 꼭대기를 의미한다.
• 부모, 자식: 트리에서 연결된 두 노드의 관계를 의미하는데, 더 위쪽에 있는 노드를 부모 노드, 아래쪽에 있는 노드를 자식 노드라고 부른다.
• 차수: 특정 노드를 기준으로, 자식의 수가 얼마나 되는지 의미한다.
• 깊이: 루트 노드와 얼마나 떨어져 있는지를 가리킨다.
• 높이: 트리에서 깊이가 가장 깊은 노드의 깊이 혹은 1을 더한 값을 의미한다.
• 리프 노드: 자식을 갖고 있지 않은 노드를 의미한다.

---

이진트리

이진트리는 자식의 수를 최대 2개로 제한하는 것이다. 

 

이진트리는 배열로도 구현이 가능하다는 특성을 갖고 있다.

이진트리의 자식은 두개이기 때문에, 하나는 왼쪽에, 그리고 다른 하나는 오른쪽에 존재한다고 볼 수 있을 것이다. 우리는 왼쪽/오른쪽 자식이라고 구분하도록 하자.

배열의 0번 값을 비우고, 루트 노드를 1번에 넣어주도록 하자. 그리고 왼쪽 자식을 2번에, 오른쪽 자식을 3번에 넣어준다. 그 후 왼쪽 자식과 오른쪽 자식을 알맞게 넣어주면 된다.

이렇게 넣게 되면, 특정 노드의 위치가 i라고 한다면, 자연스럽게 왼쪽 자식의 위치는 i * 2, 오른쪽 자식의 위치는 i * 2 + 1이 되는걸 볼 수 있다. 즉, 이진트리는 배열로 구현이 가능하며 특정 노드 i의 자식 노드를 조회하기 위해서는 i * 2, i * 2 + 1을 하면 된다. 반대로 부모노드의 위치는 i / 2로 결정된다는 것을 어렵지 않게 알 수 있다.

 

이진트리는 재귀를 사용하면 탐색을 비교적 쉽게 구현할 수 있다. 이는 방문하는 순서에 따라 크게 세 가지로 나뉘게 된다. 

• 전위 탐색 : 부모 - 왼쪽 자식 - 오른쪽 자식순으로 탐색한다. 모든 노드에 대해 부모에 먼저 색칠을 진행한 후, 왼쪽 자식들을 전부 순회하고, 그 이후에 오른쪽 자식들을 방문함을 뜻한다.
• 중위 탐색 : 왼쪽 자식 - 부모 - 오른쪽 자식순으로 탐색한다. 이 뜻은 모든 노드에 대해 왼쪽 자식들을 먼저 전부 순회한 후, 부모에 색칠을 진행하고 그 이후에 오른쪽 자식들을 방문함을 뜻한다.
• 후위 탐색 : 왼쪽 자식 - 오른쪽 자식 - 부모순으로 탐색한다. 이 뜻은 모든 노드에 대해 왼쪽 자식들을 먼저 전부 순회한 후, 오른쪽 자식들을 전부 순회하고 그 이후에 마지막으로 부모에 색칠을 진행함을 뜻한다.

중요한 점은, 재귀적으로 진행되기 때문에 트리가 조금 복잡해지면 어떤식으로 방문했는지 알기 어려울 수도 있게 된다.

 

이진탐색트리란, 부모의 왼쪽 방향에 있는 노드들은 전부 부모보다 값이 작아야하고, 부모의 우측 방향에 있는 노드들은 전부 부모보다 값이 커야만 한다는 것이다. 

function bst.insert(x)
    set node = bst.root          // root에서 시작합니다.
    set parent = bst.root        // parent도 root로 설정하고 시작합니다.

    while node != null           // node가 null이 되기 전까지 반복합니다.
        parent = node            // parent는 항상 node가 움직이기 직전의 위치로 갱신해줍니다. 
        if node.value > x        // node에 적혀있는 값이 x보다 크다면
            node = node.left     // 왼쪽 자식으로 이동해야 합니다. 
        else                     // node에 적혀있는 값이 x보다 작다면
            node = node.right    // 오른쪽 자식으로 이동해야 합니다.
    
    if parent == null            // Case 1. 비어있는 tree라면
        bst.root = node(x)       // root를 node(x)로 설정해줍니다.
    else if parent.value > x     // Case 2. parent에 적혀있는 값이 추가하려는 값 x보다 크다면
        parent.left = node(x)    // parent의 왼쪽에 node(x)를 넣어줍니다.
    else                         // Case 3. parent에 적혀있는 값이 추가하려는 값 x보다 작다면
        parent.right = node(x)   // parent의 오른쪽에 node(x)를 넣어줍니다.

 

원소의 추가, 그리고 최댓값의 삭제가 빈번하게 일어나는 상황에서 현재 남아있는 원소들 중 최댓값을 빠르게 계속 얻고 싶은 경우에만 heap 자료구조가 유용하다는 사실을 꼭 이해하고 넘어가야 한다.