Tree

이전에 보았던 stack, queue와는 다르게 비선형적인(nonlinear) 자료구조이며 나무를 뒤집어 놓은 모습과 유사하여 tree라는 이름이 붙여졌다.

Tree 용어

다음은 트리에서 자주 사용되는 용어들의 일부이다.
이 정도는 알아야 할 것 같은(이 정도만 알면 큰 지장 없는?) 것들만 적어 놓았다.

노드(Node): 트리를 구성하는 기본 요소 (8, 7, 22, 1, 10, 4, 13, 21, 27)
간선(Edge): 노드간의 연결
루트(Root Node): 트리에서 부모가 없는 최상위 노드, 트리의 시작점 (8)
리프(Leaf Node): 자식이 없는 노드 (13, 21, 10, 27)
내부(Internal Node): 자식 노드 하나 이상 가진 노드 (8, 7, 22, 1, 4)
부모(Parent Node): 간선으로 연결되었을 때 위쪽에 있는 노드 (ex) 1의 부모 =7, 13의 부모 = 1)
(root 노드를 제외한 다른 모든 노드의 부모는 하나, root 노드는 부모 노드 존재 x)
자식(Child Node): 간선으로 연결되었을 때 아래에 있는 노드 (ex) 7의 자식 = 1, 10)
형제(Siblings Node): 같은 부모 노드를 갖는 노드들 (ex) 7과 22, 1과 10)
조상(Ancestor Node) : 부모 노드들의 총 집합 (ex) 13의 조상 = 1, 7, 8)
자손(Descendant Node) : 서브트리에 있는 모든 노드들 (ex) 7의 자손 = 1, 10, 13, 21)
경로(Path): 한 노드에서 다른 한 노드 사이에 있는 노드들의 순서
깊이(Depth): 루트에서 어떤 노드까지의 간선(Edge) 수 (ex) root의 depth = 0, 1의 depth=2)

Tree 특징

tree는 다음과 같은 특징을 갖는다.

1. 단 하나의 루트 노드를 가진다.
2. 루트 노드는 0개 이상의 자식 노드를 갖는다.
3. 자식 노드 또한 0개 이상의 자식 노드를 갖는다.
4. 그래프의 한 종류이며, cycle이 존재하지 않는다.
5. 노드가 N개인 트리는 항상 N-1개의 간선을 가진다.

Tree 순회

tree의 모든 노드들을 방문하는 방법에는 크게 3가지가 존재한다.
나를 언제 방문하는지로 기억하면 쉽게 기억할 수 있다.

1. Preorder

binary tree에서의 preorder 함수이다. (나를 먼저 방문)
preorder 결과: 8 - 7 - 1 - 13 - 21 - 10 - 22 - 4 - 27

void preorder(int n){
    if(n==-1) return;
    cout << n << ' '; // 나를 방문
    preorder(tree[n][0]); // 왼쪽 child 방문
    preorder(tree[n][1]); // 오른쪽 child 방문
}

2. Inoredr

binary tree에서의 inorder 함수이다. (나를 중간에 방문)
inorder 결과: 13 - 1 - 21 - 7 - 10 - 8 - 22 - 27 - 4

void inorder(int n){
    if(n==-1) return;
    inorder(tree[n][0]); // 왼쪽 child 방문
    cout << n << ' '; // 나를 방문
    inorder(tree[n][1]);  // 오른쪽 child 방문
}

3. Postorder

binary tree에서의 postorder 함수이다. (나를 마지막에 방문)
postorder 결과: 13 - 21- 1 - 10 - 7 - 27 - 4 - 22 - 8

void postorder(int n){
    if(n==-1) return;
    postorder(tree[n][0]); // 왼쪽 child 방문
    postorder(tree[n][1]); // 오른쪽 child 방문
    cout << n << ' '; // 나를 방문
}

풀어보면 좋은 문제 - 백준 1991번: 트리 순회

Tree 종류

1. Binary Tree

각 노드가 최대 두개의 자식노드(left child, right child)를 갖는 트리이다.

2. Binary Search Tree (BST)

Binary Tree의 일종으로 데이터의 효율적인 탐색을 위해 사용한다.

BST가 되기 위해서는 아래 조건들을 만족해야한다.

1. Binary Search Tree의 node에 저장된 값(키)은 유일하다.
2. left child의 값이 parent의 값보다 작다.
3. right child의 값이 parent의 값보다 크다.
4. left subtree와 right subtree도 Binary Search Tree이다.

Binary Search Tree 탐색 시간은 O(H)로 편향트리(Skewed Tree)가 되는 경우, H=N이 되어 worst cas에는 O(N)이 된다. 이러한 점을 개선하기 위해 아래와 같은 tree들이 등장했다!

풀어보면 좋은 문제 - 백준 5639번: 이진 검색 트리

3. AVL Tree

Binary Search Tree를 기반으로하는 트리로 스스로 균형을 잡아 편향트리가 되는 것을 피하는 Tree이다.

AVL 트리가 되기 위해서는 Binary Search Tree에서 추가적으로 아래 조건을 만족해야한다.

1. 왼쪽, 오른쪽 서브 트리의 높이 차이가 최대 1 이다.
2. 어떤 시점에서 높이 차이가 1보다 커지면 다음과 같이 회전(rotation)을 통해 균형을 잡아 높이 차이를 줄인다.
   rotaion할 node들의 형태에 따라 rotation에는 다음 2가지 종류가 있다.
   (z: 처음으로 문제가 생긴 노드, y: z의 child, x: y의 child)
   1) single rotation
   
   2) double rotation
   

AVL 트리는 높이를 log N으로 유지하기 때문에 삽입, 검색, 삭제의 시간 복잡도가 O(logN) 이다

4. Splay Tree

Binary Search Tree를 기반으로하는 트리로 마지막에 동작한 노드를 root로 가져온다는 차이점이 있다. 때문에 자주 사용하는 Data에 접근하는 속도가 빨라진다는 장점이 있다.

편향트리(Skewed Tree)가 되는 경우, H=N이 되어 worst cas에는 O(N)이 된다.

5. Red-Black Tree

Binary Search Tree를 기반으로하는 트리로 노드에 색상(Red, Black)을 추가하여 균형을 맞춘 트리이다.

Red-Black Tree가 되기 위해서는 아래 조건들을 만족해야한다.

1. 각 노드는 Red or Black의 색깔을 갖는다.
2. 루트 노드는 Black이다.
3. 리프 노드는 Black이다.
4. Red 노드의 child는 Black이다.
5. 모든 리프 노드에서의 Black depth는 같다.
   (Black-depth : 특정 노드 X에서 부터 리프 노드까지 X를 포함하지 않는 simple path에 포함되는 black 노드의 개수)
6. 노드의 child가 없을 경우 포인터는 NULL을 갖는다.

1) Insertion
삽입 시 Double Red 문제가 발생할 수 있다. (삽입하는 node의 색상은 Red)
=> Restructuring(새로 추가한 node의 sibling이 black인 경우)
Recoloring(새로 추가한 node의 sibling이 red인 경우)

2) Deletion
삭제 시 Double Black, Depth Property 문제가 발생할 수 있다.
=> Restructuring(double black문제가 생긴 노드의 sibling이 black이고 red child를 가진 경우)
Recoloring(double black문제가 생긴 노드의 sibling이 black이고 black child를 가진 경우)
adjustment(앞의 두가지 경우가 아닌 경우 앞의 두가지 경우 중 하나로 바꿔서 문제 해결)

노드에 색상을 추가하여 균형을 맞추었으므로 삽입, 검색, 삭제의 시간 복잡도가 O(logN) 이다