🧬 자료구조(2) - tree

Tree

그래프의 일종으로, 정점과 간선을 이용하여 데이터의 배치 형태를 추상화한 자료구조
서로 다른 두 노드를 연결하는 길이 하나뿐인 그래프를 트리 라고 칭한다.
트리 의 구조는 ‘데이터 저장’ 의 의미보다는 ‘저장된 데이터를 더 효율적으로 탐색’ 하기 위해서 사용된다.

트리 순회

트리의 각 노드를 체계적인 방법으로 탐색하는 과정을 의미한다. 노드를 탐색하는 순서에 따라 전위 순회, 중위 순회, 후위 순회 세 가지로 분류된다.

1. 전위 순회 (preorder)

   root → left → right 순서로 순회하는 방식이다. 깊이 우선 순회 라고도 불린다.

2. 중위 순회 (Inorder)

   left → root → right 순서로 순회하는 방식이다. 대칭 순회 라고도 불린다.

3. 후위 순회 (Postorder)

   right → left → root 순서로 순회하는 방식이다.

Binary Tree

여러 가지 유형의 트리 자료구조 중, 가장 기본이 되는 트리는 이진 트리 이다.
이진 트리는 2개 이하의 자식 노드를 가진다. (자식 노드 갯수: 0 or 1 or 2)

• 편향 이진 트리 (Skewed Binary Tree)
  
  편향 이진 트리 는 하나의 차수로만 이루어져 있는 경우를 의미한다. 이러한 구조는 배열(리스트)와 같은 선형 구조이므로 leaf node 탐색 시 모든 데이터를 탐색해야 한다는 단점이 있어 효율적이지 못하다.
  O(n)의 시간복잡도를 가진다.
  
  
• 포화 이진 트리 (Full Binary Tree)
  
  포화 이진 트리 는 leaf node를 제외한 모든 노드의 차수가 2개로 이루어져 있는 경우를 의미한다. 이 경우 해당 차수에 몇 개의 노드가 존재하는지 바로 알 수 있으므로 노드의 개수를 파악할 때 용이하다.
  
  
• 완전 이진 트리 (Complete Binary Tree)
  
  포화 이진 트리와 같은 개념으로 트리를 생성하지만, 완전 이진 트리 는 모든 노드가 왼쪽부터 차근차근 생성되는 이진 트리를 의미한다.
  * heap은 완전 이진 트리의 일종이다.

Expression Tree

수식을 표현하는 데 사용되는 트리

• 중위순회를 하게 되면 우리가 익히 알고 있는 중위 표기법이 탄생 a/b*c*d+e
• 후위순회를 하면 후위 표기법 ab/c*d*e+
• 전위순회를 하면 함수처럼 사용하는 전위 표기법 +**/abcde

Binary Search Tree

탐색을 위한 이진 트리 기반의 자료구조이다.

• left node에는 부모노드보다 작은 값이 저장된다.
• right node에는 부모노드보다 큰 값이 저장된다.
• 모든 노드는 중복된 값을 가지지 않는다.

왜 이진 탐색 트리가 생겼을까?

데이터를 효율적으로 탐색할 수 있기 때문이다.
원하는 값을 찾을 때까지 현재의 노드값보다 찾고자 하는 값이 작으면 왼쪽으로, 크면 오른쪽으로 움직인다.
이렇게 원하는 값을 전체 영역에서 탐색하지 않고, 반으로 나눠 탐색하므로 더 빠르게 찾을 수 있다.

O(logN)의 시간복잡도를 가진다.
각 단계에서 탐색 범위가 대략 절반으로 줄기 때문이다.
만약 이진 탐색 트리가 균형이 잡혀 있다면. 즉, 완전 이진 트리라면.. 트리의 높이는 logN이 되며, 이에 따라 탐색에 소요되는 시간 복잡도는 O(logN)이다.

왜 logN 일까?

운이 좋으면 찾고자 하는 값이 중간값과 동일해서 탐색이 끝나지만 최악의 경우 남은 데이터가 하나가 될 때까지 탐색을 반복한다. 이를 고려해 시간 복잡도를 계산해보자.

하지만 불균형 트리의 경우(최악), 높이가 N이 되어 시간 복잡도가 O(N)까지도 될 수 있다.

→ O(logN)의 성능 보장을 위해 AVL 트리, RB 트리 등장

스스로 균형을 잡는 Binary Search Tree

한쪽으로 치우진 편향 이진 트리가 되면 트리의 높이가 높아지기 때문에 이를 방지하고자 스스로 높이 균형을 유지하는 AVL, RB 트리를 사용하게 된다.

• Red-Black Tree
  정글에서 정리한 rb tree

• AVL Tree
  

  • Balance Factor(BF)를 통해 균형을 맞춘다.
  • 왼쪽, 오른쪽 서브 트리의 높이 차이가 최대 1이다.
  • 어떤 시점에서 높이 차이가 1보다 커지면 rotation을 통해 균형을 잡아 높이 차이를 줄인다.
  • AVL 트리는 높이를 logN으로 유지하기 때문에 삽입, 검색, 삭제의 시간 복잡도는 항상 O(logN)이다.

    Balance Factor(BF)
    Balance Factor (k) = height(left(k)) - height(right(k))
    왼쪽 서브트리의 높이에서 오른쪽 서브트리의 높이를 뺀 값

    • BF가 1이면 왼쪽 서브트리가 오른쪽 서브트리보다 한단계 높다.
    • BF가 0이면 왼쪽 서브트리의 높이 = 오른쪽 서브트리의 높이
    • BF가 -1이면 왼쪽 서브트리가 오른쪽 서브트리보다 한단계 낮다.

• Red-Black & AVL 차이점

  • AVL 트리는 더욱 엄격한 균형을 이루고 있기 때문에 rb tree보다 더 빠른 조회 제공

  • AVL 트리는 각 노드에 대해 BF를 저장하므로 노드 당 int 저장 필요

  • RB 트리는 상대적으로 느슨한 균형으로 인해 회전이 거의 이루어지지 않아 AVL tree 보다 빠르게 삽입, 삭제 작업을 수행

  • RB 트리는 색깔 정보를 저장하기 위해 노드당 1비트의 정보만 필요합니다. (red or black: 플래그 반전만 시키면 됨)

  • RB 트리는 맵, C++의 멀티맵, Java treeMap 등 대부분의 언어 라이브러리에서 사용, AVL 트리는 더 빠른 검색이 필요한 데이터베이스에서 사용

---

Q. BST(Binary Search Tree)와 Binary Tree 에 대해 설명해주세요.

Binary Tree는 자식 노드가 최대 두 개인 노드들로 구성된 트리이고,
Binary Search Tree는 이진 탐색과 연결 리스트를 결합한 트리 자료구조이다. 이진 탐색의 효율적인 탐색 능력을 유지하면서, 빈번한 자료 입력과 삭제가 가능하다는 장점이 있다.

이진 탐색 트리는 왼쪽 트리의 모든 값은 반드시 부모 노드보다 작아야 하고, 오른쪽 트리의 값은 부모 노드보다 커야 하는 특징이 있다.

이진 탐색 트리의 탐색 연산은 트리의 높이에 영향을 받아 높이가 h일 때 시간 복잡도는 O(h)이며, 트리의 균형이 한쪽으로 치우쳐진 경우 worst case가 된다. 이런 worst case를 막기 위해 나온 기법이 rb-tree 이다.

Q. Red-Black Tree에 대해 설명해주세요.

rb-tree는 bst를 기반으로 하는 트리 형식 자료구조이며, bst의 삽입, 삭제 연산 과정에서 발생할 수 있는 문제점을 해결하기 위해 만들어졌다.

bst를 기반으로 하기 때문에 당연히 bst의 특징을 모두 갖는다.

노드의 child가 없을 경우, child를 가리키는 포인터는 nil 값을 저장한다. 이러한 nil들을 leaf node로 간주한다.

💡
1. node color is red or black.
2. new node color is red.
3. root node color is black.
4. double red doesn’t exist.
5. the number of black nodes from the root node to the nil node is the same.

Q. Expression Tree

연산자 우선순위는 어떻게 되는가?
Q. duplicates를 처리하기 위해선 node_t에 count라는 속성을 추가해야 한다. 하지만 현재 프로젝트의 제약사항으로 "rbtree.c"만 수정해야 하는데, 정말로 node_t를 수정하지 않고 중복 원소를 처리하라는 것인가?

A. 가능하다. 정렬된 list를 [1,1, 2, 2, 2, 3]과 같이 구현할 수도 있고 {1: 2개, 2: 3개, 3: 1개} 로 구현할 수도 있습니다만, 앞의 방식으로 구현하라는 이야기이다.