[Algorithm] 트리

Tree 의 이해와 표현

트리는 비선형 구조로 원소들 간에 1:n 관계를 가지는 자료구조이다. 원소들 간에 계층관계를 가지는 계층형 자료구조이며 상위 원소에서 하위 원소로 내려가면서 확장되는 Tree 모양이다. 트리는 한 개 이상의 노드로 이루어진 유한 집합이다. 최상위 노드는 루트라 부른다. 나머지 노드들은 분리 집합으로 분리될 수 있으며 각각 하나의 트리가 될 수 있다.

트리는 노드와 간선으로 이루어져있다.

노드 : 트리의 원소를 뜻한다.
간선 : 부모 노드와 자식 노드를 연결하는 선이다.
루트 노드 : 트리의 시작 노드.
형제 노드 : 같은 부모 노드의 자식 노드들이다.
조상 노드 : 간선을 따라 루트 노드까지 이르는 경로에 있는 모든 노드들이다.
부트리 : 부모 노드와 연결된 간선을 끊었을 때 생성되는 트리이다.
자손 노드 : 부트리에 있는 하위 레벨의 노드들이다.
차수 : 노드에 연결된 자식 노드의 수
- 트리의 차수는 트리가 있는 노드의 차수 중 가장 큰 값이다.
- 차수가 없는, 자식 노드가 없는 노드를 단말 노드 (리프 노드) 라 한다.
노드의 높이 : 루트에서 노드에 이르는 간선의 수, 노드의 레벨

Binary Tree

모든 노드들이 2개의 부트리를 갖는 특별한 형태의 Tree
노드가 자식 노드를 최대 2개까지만 가질 수 있다
- 왼쪽 자식 노드, 오른쪽 자식 노드
레벨 i 에서의 노드의 최대 개수는 2^i개
높이가 h 인 B-Tree 에서 가질 수 있는 노드의 최소 개수는 (h+1) 개, 최대 개수는 (2^(h+1) - 1)개

포화 이진 트리, Full Binary Tree

모든 레벨에 노드가 포화상태로 차 있는 B-Tree
최대 노드 개수인 (2^(h+1) - 1)개 를 가진 B-Tree
루트를 1번으로 하여 2^(h+1) - 1 까지 정해진 위치에 대한 노드 번호를 가진다

완전 이진 트리, Complete Binary Tree

높이가 h 이고 노드 수가 n개 일 때, 노드 1번부터 n번까지 빈 자리가 없는 B-Tree

편향 이진 트리, Skewed Binary Tree

높이 h에 대한 최소 개수의 노드를 가지면서 한쪽 방향의 자식 노드만을 가진 B-Tree

순회

트리의 각 노드를 중복되지 않게 전부 방문하는 것
트리는 비선형 구조이기 때문에 선형구조처럼 선후 연결 관계를 알 수 없다

전위 순회, Preorder traversal

자손 노드보다 루트 노드를 먼저 방문

preorder_traverse(T)
  if (T is not null)
  {
    visit(T);
    preorder_traverse(T.left);
    preorder_traverse(T.right);
  }
End preorder_traverse

중위 순회, Inorder traversal

왼쪽 자손, 루트, 오른쪽 자손 순으로 방문

inorder_traverse(T)
  if (T is not null)
  {
    inorder_traverse(T.left);
    visit(T);
    inorder_traverse(T.right);
  }
End inorder_traverse

후위 순회, Postorder traversal

루트 노드보다 자손 노드를 먼저 방문

postorder_traverse(T)
  if (T is not null)
  {
    postorder_traverse(T.left);
    postorder_traverse(T.right);
    visit(T);
  }
End postorder_traverse

B-Tree 표현

트리의 각 노드 번호를 다음과 같이 부여한다
루트 번호를 1로 하고 각 레벨에 대하여 왼쪽부터 오른쪽으로 번호를 부여한다.
노드 번호가 i 인 노드의 부모 노드 번호는 [i/2]
노드 번호가 i 인 노드의 왼쪽 자식 노드 번호는 2*i
노드 번호가 i 인 노드의 오른쪽 자식 노드 번호는 2*i + 1

Array

노드 번호를 Array의 인덱스로 사용한다
Array의 크기는 높이가 h인 B-Tree의 최대 노드 수로 할당할 수 있다.
단점
- 포화 이진트리가 아니라면 사용하지 않는 Array 공간에 대한 메모리 낭비가 있다
- 노드를 생성, 삭제 하는 경우 Array의 크기가 고정되어있어 문제가 발생한다

연결 List

Array를 이용한 트리 표현의 단점을 보완한다.
일정한 구조의 단순 연결 List 노드를 사용하여 구현할 수 있다.
- left 링크, data, right 링크 를 가진 노드

Expression Tree

B-Tree 를 응용한 트리로 수식을 표현하는 B-Tree
연산자는 루트 노드이거나 가지 노드이며 피 연산자는 모두 단말 노드
순회의 방식에 따라 표기법이 다르게 생성된다

Binart Search Tree

탐색 작업을 효율적으로 하기 위한 자료구조
모든 원소는 서로 다른 키를 가짐
key(왼쪽) < key(루트) < key(오른쪽)
중위 순회하면 오름차순으로 정렬된 값을 얻을 수 있다

탐색 연산

루트에서 시작
탐색할 키 값 x와 루트 노드의 키 값을 비교
- x == key(노드) : 원소 탐색 성공
- x > key(노드) : 오른쪽 부트리에 대해 탐색 연산 수행
- x < key(노드) : 왼쪽 부트리에 대해 탐색 연산 수행

삽입 연산

삽입할 원소와 같은 원소가 있으면 삽입할 수 없으므로 먼저 탐색 연산을 수행
탐색에서 탐색 실패가 결정되는 위치가 삽입 위치가 된다

탐색, 삽입, 삭제 시간은 Tree의 높이에 좌우된다

Twitter Facebook LinkedIn

Min Gyu