Algorithm 12장 - tree

Algorithm

정의

• 나무를 거꾸로 뒤집어 놓은 듯한 모습을 갖고 있는 단방향 그래프로, 하나의 뿌리로부터 가지가 뻗은 형태이다.
• 데이터가 바로 아래에 있는 하나 이상의 데이터에 한 개의 경로와 하나의 방향으로만 연결된 계층적 자료구조이다.
• 하나의 데이터 아래에 여러 개의 데이터가 존재할 수 있는 비선현 구조이다.
• 트리 구조는 아래로만 뻗어나가기 때문에 사이클이 없는데, 사이클은 다른 노드를 거쳐 시작 노드로 돌아올 수 있는 것을 말한다.

특징

• 루트라는 하나의 꼭짓점 데이터를 시작으로 여러 개의 데이터를 간선으로 연결한다.
• 각 데이터를 노드라고 부르며, 두 개의 노드가 상하 계층으로 연결되면 부모/자식 관계를 맺는다.
• 루트로부터 하위 계층의 특정 노드까지의 깊이를 표현할 수 있다.
• 같은 깊이를 가지고 있는 노드를 묶어서 레벨이라고 표현하며, 같은 레벨에 나란히 있는 노드를 형제 노드(Sibling Node)라고 한다.
• 리프 노드를 기준으로 루트까지의 높이를 표현하는데, 리프 노드와 직간접적으로 연결된 노드의 높이를 표현하며 부모 노드는 자식 노드의 가장 높은 높이 값에 +1한 값을 높이로 가진다.
• 트리 구조를 갖춘 작은 트리를 서브 트리라고 부른다.

이진 트리

• 자식 노드가 최대 두 개인 노드로 구성된 트리를 말한다.
• 자료의 삽입, 삭제 방법에 따라 정 이진 트리(Full binary tree), 완전 이진 트리(Complete binary tree), 포화 이진 트리(Perfect binary tree)로 나뉜다.

이진 트리 특징

• 정 이진 트리 : 각 노드가 0개 혹은 2개의 자식 노드를 갖는다.
• 포화 이진 트리 : 정 이진 트리면서 완전 이진 트리인 경우인데, 모든 리프 노드의 레벨이 동일하고, 모든 레벨이 가득 채워져 있는 트리이다.
• 완전 이진 트리 : 마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하고, 마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽이 채워져야 한다.

이진 탐색 트리(Binary Search Tree)

• 정렬된 데이터 중에서 특정한 값을 찾기 위한 탐색 알고리즘 중 하나이다.
• 오름차순으로 정렬된 정수의 배열을 이등분으로 나눈 후, 두 부분 중 탐색이 필요한 부분에서만 탐색하도록 탐색 범위를 제한하는 것을 말한다.
• 루트노드의 왼편으로는 루트노드보다 작은 값을 가진 노드들이 있고, 오른편 노드들은 루트노드의 값보다 큰 값들이 자리 잡고 있다.
• 각 노드에는 중복되지 않는 키를 가지고 있으며, 좌우 서브 트리도 모드 이진 탐색 트리여야 한다.
• 모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가지는 특징이 있다.

이진 탐색 트리 특징

• 이진 탐색 트리는 기존 이진 트리보다 탐색이 빠르다는 장점이 있다.
• 이진 탐색 트리의 연산은 트리의 높이가 h(height)라면 o(h)의 복잡도를 가지게 된다.
• 과정
  1. 루트 노드의 키와 찾고자 하는 값을 비교한다.
     1. 만약 찾고자 하는 값이라면 탐색을 종료한다.
  2. 찾고자 하는 값이 루트 노드의 키보다 작다면 왼쪽 서브 트리로 탐색한다.
  3. 찾고자 하는 값이 루트 노드의 키보다 크다면 오른쪽 서브 트리로 탐색한다.

트리 순회

• 특정 목적을 위해 트리의 모든 노드를 한 번씩 방문하는 것을 말한다.

전위 순회 (preorder traverse)

• 루트에서 시작해 왼쪽의 노드들을 순차적으로 둘러본다.
• 왼쪽의 노드 탐색이 끝나면 오른쪽 노드를 탐색한다.
• 부모가 제일 먼저 방문 되는 순회 방식이며, 주로 트리를 복사할 때 사용한다.

중위 순회 (inorder traverse)

• 제일 왼쪽 끝에 있는 노드부터 순회하기 시작하여, 루트를 기준으로 왼쪽에 있는 노드의 순회가 끝나면 루트를 거쳐 오른쪽에 있는 노드로 이동하여 마저 탐색한다.
• 이진 탐색 트리의 오름차순으로 값을 가져올 때 쓰인다.

후위 순회 (postorder traverse)

• 루트를 가장 마지막으로 순회한다.
• 제일 왼쪽 끝에 있는 노드부터 순회하기 시작하여, 루트를 거치지 않고 오른쪽으로 이동해 순회한 뒤, 제일 마지막에 루트를 방문한다.
• 트리를 삭제할 때 사용한다.
• 자식 노드가 먼저 삭제되어야 상위 노드를 삭제할 수 있기 때문이다.

레벨 순회 (levelorder traverse)

• 루트를 방문하는 기준으로 순회하는 것이 아닌 트리의 레벨을 기준으로 노드들을 방문하는 순회 방법이다.
• 루트 노드를 시작으로 아래로 뻗어나가며 노드들을 방문하며 루트 노드의 레벨이 1레벨이라고 했을 때 아래로 내려갈수록 레벨은 증가하는 특징을 보인다.
• 동일한 레벨에 여러 노드가 존재할 경우 왼쪽에서 오른쪽 순서로 노드를 방문한다.

순회 방식을 나누는 이유

모든 노드를 방문하기 위해서는 일정한 조건이 필요하고, 트리 구조를 유지보수하거나 특정 목적을 위해서도 순회 방법에 대한 정의는 필수적으로 필요하다.