Tree

트리란?

부모-자식 관계로 정의하고, 부모에서 자식으로 간선이 이어져있는 유향 그래프를 의미합니다. 트리는 그래프에 속합니다.

 

용어

• 노드(node): 트리를 구성하는 기본 원소
• 루트 노드(root node/root): 트리에서 부모가 없는 최상위 노드, 트리의 시작점
• 부모 노드(parent node): 루트 노드 방향으로 직접 연결된 노드
• 자식 노드(child node): 루트 노드 반대방향으로 직접 연결된 노드
• 형제 노드(siblings node): 같은 부모 노드를 갖는 노드들
• 리프 노드(leaf node/leaf/terminal node): 자식이 없는 노드
• 경로(path): 한 노드에서 다른 한 노드에 이르는 길 사이에 있는 노드들의 순서
• 길이(length): 출발 노드에서 도착 노드까지 거치는 노드의 갯수
• 깊이(depth): 루트 경로의 길이
• 레벨(level): 루트 노드(1) 로 부터 노드까지 연결된 엣지의 수의 합
• 높이(height): 가장 긴 루트 경로의 길이
• 차수(degree): 각 노드의 자식의 갯수
• 트리의 차수(degree of tree): 트리의 최대 차수
• 크기(size): 노드의 개수
• 너비(width): 가장 많은 노드를 갖고 있는 레벨의 크기

출처 : 나무위키

 

구현 방법

• 객체 이용

  • 간략하게 나타내면 다음과 같습니다.

Node {
    int v;
    List<Node> children;
}

Tree {
    Node root;
}

• 배열 이용

  • 배열 인덱스를 이용하여 트리를 나타내게 할 수 있습니다.

이전에 Heap트리를 만들기 위해 고생한 적이 있는데요. 수업들을 때 든 생각은 형제노드를 참조하고 있었으면 좀 더 구현하기 수월하지 않았을까 생각합니다. 조건문이 좀 난잡하게 있었거든요.

 

종류

• 이진 트리(Binary Tree)

  • 이진 탐색 트리(Binary Search Tree)

    • AVL-tree
    • Red-black tree

  • Heap

• B-tree

• 트라이(Trie)

 

이진 트리

부모 노드 밑 자식 노드가 최대 2개 밖에 오지않는 트리를 의미합니다.

• 포화 이진 트리(full binary tree) : 모든 리프 노드의 높이가 같습니다.
• 완전 이진 트리(complete binary tree) : 모든 리프 노드의 높이가 최대 1차이가 나고, 자식 노드는 왼쪽부터 채워진 형태입니다.

 

이진 트리의 순회

• 전위 순회 : 자신 → 왼쪽 자식 → 오른쪽 자식
• 중위 순회 : 왼쪽 자식 → 자신 → 오른쪽 자식
• 후위 순회 : 왼쪽 자식 → 오른쪽 자식 → 자신
• 중위 순회는 이진 탐색 트리 순회시 정렬이 가능합니다. 그리고 후위 순회의 경우 보통 계산기 연산시에 유용하게 쓰입니다.

 

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

위의 이진 트리는 자식이 최대 2개 밖에 오지 않으면 됩니다. 하지만 이진 탐색 트리는 여기에 좀 더 조건이 붙습니다. 자식 중 작은 값은 왼쪽, 큰 값은 오른쪽에 두도록 하는 것입니다. 이 규칙은 어느 노드를 잡아도 똑같이 적용됩니다. 이런 구조에서 탐색/삽입/삭제시 O(log N)의 복잡도를 가지게 됩니다.

다만 최악의 상황이 있는데요. 예를들어 1, 2, 3, 4와 같은 수가 주어지고 루트가 1일때인 경우입니다. 이 때는 오른쪽으로 편향된 직선 형태의 그래프가 그려질 것입니다. 이때는 복잡도가 O(N)이 되는 것이죠. 이와 같은 상황을 보완하고자 등장한 것이 AVL tree입니다.

• AVL-tree

  • 위에 언급한 것과 같은 최악의 상황시 알아서 다시 균형잡힌 트리로 만들어줍니다.
  • 상용은 아닙니다.

• Red Black Tree

  • AVL-tree와 마찬가지로 불균형한 트리를 균형잡히게 만들어줍니다.
  • 노드의 Red 혹은 Black색이 붙어 정렬해줍니다.

 

B-tree

디스크 검색 트리라고도 하는데요. 자식이 엄청나게 많습니다. 그 이유는 디스크 검색에 최적화되었기 때문에 메모리에 빨리 찾아갈 수 있도록 하기 위함입니다. 기본적으로 모든 높이가 동일하게 균형잡혀 있습니다. 그리고 또 다른 특징으론 Clustered Index라는 점인데요. 이는 삽입된 순서에 관계없이 인덱스에 생성된 컬럼을 기준으로 정렬되어 삽입되는 것을 말합니다.

DB에서 PK검색은 왜 빠를까요?

그 이유는 PK가 B-tree구조로 따로 저장되어 있기 때문입니다. 이렇게 따로 저장되어 있다는 점 때문에 update시 시간이 더 소요되고 메모리 용량이 추가적으로 더 필요하다는 단점이 있습니다. 하지만 B-tree를 따라 PK를 찾으면 그것의 디스크주소(Record ID, 페이지-슬롯으로 구성)를 정말 빠르게 찾을 수 있기 때문에 쓰는 것이죠. 만약 PK가 아닌 NAME이라는 필드에 인덱스를 걸었다면 B-tree에 따라 NAME을 탐색하고 그 과정에서 PK를 다시 발견하는 구조 이루어져있습니다.