TIL [자료 구조 - Tree & Binary Search Tree]

dlrbwls0302·2021년 1월 22일
0

Tree의 개념

트리는 말 그대로 나무라는 뜻인데 나무처럼 root(뿌리)에서 시작해서 가지처럼 뻗어나가는 모양의 자료 구조를 의미한다.

여기서 살펴보아야 될 부분은 depth라는 것이다. 밑으로 내려 갈수록 depth가 깊어지는 것을 알 수 있다. 같은 부모 노드에서 나와 같은 depth에 있는 노드들을 형제 노드라고 한다. 또한 자식이 없는 노드(그림에서는 H, I, J)를 나뭇가지의 끝에 달린 나뭇잎 즉, leaf라고 부른다.


Depth와 Height의 차이

1. Depth

Depth는 root 노드에서 어떤 노드까지의 간선의 수이다. 기준은 root 노드(depth 0)이다.

2. Height

그래프의 height는 가장 멀리 떨어진 leaf 에서 root 노드까지의 간선의 수이다. 기준이 가장 멀리있는 leaf(height 0)일 경우 그 leaf를 기준으로 부모 노드로 한 칸씩 올라갈 때 마다 height도 1씩 증가한다.


Tree와 Graph의 차이

1. Tree

  1. 최소한으로 연결된 그래프이고 두 개의 정점사이에 한 방향의 간선 하나밖에 없다.
  2. 루프가 없다.
  3. 한 개의 root 노드가 존재하며 모든 자식 노드는 오직 한 개의 부모 노드를 가지고 있다.
  4. 부모-자식의 흐름을 갖고 있기때문에 위에서 아래로 흐른다.
  5. 간선의 수는 항상 (노드의 수-1)이다.
  6. 우리가 쓰는 DOM구조가 바로 tree이다.

2. Graph

  1. 노드들간에 한 방향이나 양 방향의 간선을 가질 수 있다.
  2. 루프를 만들 수 있고 셀프루프 또한 만들 수 있다.
  3. root 노드에 대한 개념이 없다.
  4. 부모-자식같은 흐름이 없다.
  5. 간선의 수는 그래프마다 다르다.

Binary Search Tree의 개념

Binary Search Tree란 이진 탐색(binary search)과 연결 리스트(linked list)를 결합한 자료 구조의 일종이다. BST는 각 노드의 왼쪽 서브트리에는 해당 노드의 값보다 작은 값이, 각 노드의 오른쪽에는 해당 노드보다 큰 값이 있다. 이때 중복된 노드가 없어야하고 BST를 순회할 때는


Binary Tree의 종류

1. 정 이진 트리 (Full Binary Tree)

정 이진 트리는 모든 레벨에서 노드들이 꽉 채워진(leaf를 제외한) 모습을 가지고 있다. 맨 밑에 leaf 노드들은 채워져 있지 않지만 그 위에 레벨의 노드들은 각각 두 개의 자식 노드들을 가지고 있는 것을 알 수 있다. 높이가 h인 정 이진 트리에서 보유할 수 있는 최대의 노드 수는 2^(h+1) - 1 이다.

2. 완전 이진 트리 (Complete Binary Tree)

왼쪽 노드부터 채워져있고 마지막 레벨을 제외하고 모두 자식 노드가 있으면 완전 이진 트리이다.

3. 포화 이진 트리 (Perfect Binary Tree)

포화 이진 트리는 모든 노드가 0이나 2개의 자식 노드를 가지고 있고 모든 leaf 노드가 똑같은 레벨에 있는 이진 트리이다.


Binary Tree의 순회

1. 중위 순회 (Inorder Traversal)

좌 -> 부모 -> 우 순으로 모든 노드들을 순회하는 방법이다. 위 그림의 경우 1 -> 3 -> 5 -> 6 -> 7 -> 9 -> 11 순이다. 좌부터 이길래 루트 노드(6)의 왼쪽 노드인 3에 가봤는데 거기에도 자식 노드가 있어서 3의 왼쪽인 1을 순회하고 그 다음 부모인 3, 오른쪽인 5를 순회하는 식으로 반복하고 있다. 이렇게 순회를 하니 오름차순으로 노드를 순회한 것을 알 수 있다.

2. 전위 순회 (Preorder Traversal)

부모 -> 좌 -> 우 순으로 모든 노드들을 순회하는 방법이다. 위 그림의 경우 6 -> 3 -> 1 -> 5 -> 9 -> 7 -> 11 순으로 중위 순회와 비교하였을때 좀 더 복잡한 구조인 것 같다. 처음 루트 노드(6)에서 시작하여 맨 밑의 노드에 닿을때 까지 계속 왼쪽으로 간다. 따라서 6에서 시작하여 왼쪽인 3, 또 거기서 왼쪽인 1로 가게된다. 그 다음 다시 부모 노드인 3으로 돌아와서 이번엔 오른쪽인 5로 가게된다. 이것이 다 끝나면 다시 3의 부모 노드이자 루트 노드인 6으로 간다. 그 다음 오른쪽 노드인 9로 가고 다시 왼쪽 노드인 7을 찍고 더 내려갈 곳이 없으면 다시 부모 노드 9로 돌아와서 나머지 오른쪽 노드인 11로 가게된다.

3. 후위 순회 (Postorder Traversal)

좌 -> 우 -> 부모 순으로 모든 노드들을 순회하는 방법이다. 위 그림의 경우 1 -> 5 -> 3 -> 7 -> 11 -> 9 -> 6 순이다. 시작은 루트 노드(6)의 좌인 3의 좌인 1이다. 그 다음 1의 형제 노드이며 부모(3)의 우인 5이다. 그 다음이 부모 노드인 3이고 루트 노드(6)의 좌는 모두 끝이 난다. 그 다음이 오른쪽 노드인 9인데 9에도 자식 노드가 있어서 먼저 9의 좌인 7, 우인 11이 들어가고 이 둘의 부모인 9가 그 다음에 나온다. 그리고 루트 노드(6)의 좌와 우가 모두 끝나 이들의 부모인 6이 순환되며 끝이난다.

profile
오늘의 공부가 쌓여서 내일의 나를 만들어낸다.

관심 있을 만한 포스트

0개의 댓글